Олимпиадные задачи по теме «Комбинаторика» - сложность 2 с решениями

Резидент одной иностранной разведки сообщил в центр о готовящемся подписании ряда двусторонних соглашений между пятнадцатью бывшими республиками СССР. Согласно его донесению, каждая из них заключит договор ровно с тремя другими. Заслуживает ли резидент доверия?

Как, не отрывая карандаша от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4&times4?

Метро города Урюпинска состоит из трёх линий и имеет по крайней мере две конечные станции и по крайней мере два пересадочных узла, причём ни одна из конечных станций не является пересадочной. С каждой линии на любую из остальных можно перейти по крайней мере в двух местах. Нарисуйте пример такой схемы метро, если известно, что это можно сделать, не отрывая карандаша от бумаги и не проводя два раза один и тот же отрезок.

На шахматной доске 8×8 расставлено наибольшее возможное число слонов так, что никакие два слона не угрожают друг другу.

Доказать, что число всех таких расстановок есть точный квадрат.

У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось.

Докажите, что число марсиан, у которых нечётное число рук, чётно.

Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?

Рассматривается доска 8×8, клетки которой пока не окрашены. Сколькими способами можно раскрасить доску в чёрный и белый цвета так, чтобы чёрных клеток было 31 и никакие две чёрные клетки не имели общей стороны? (Два способа раскраски считаются различными, если найдётся клетка, которая при одном из этих способах раскраски белая, а при другом – чёрная.)

Можно ли расставить в вершинах куба натуральные числа так, чтобы в каждой паре чисел, связанных ребром, одно из них делилось на другое, а во всех других парах такого не было?

В основании призмы лежит <i>n</i>-угольник. Требуется раскрасить все 2<i>n</i> её вершин тремя красками так, чтобы каждая вершина была связана рёбрами с вершинами всех трёх цветов.

  а) Докажите, что если <i>n</i> делится на 3, то такая раскраска возможна.

  б) Докажите, что если если такая раскраска возможна, то <i>n</i> делится на 3.

Куб со стороной 20 разбит на 8000 единичных кубиков, и в каждом кубике записано число. Известно, что в каждом столбике из 20 кубиков, параллельном ребру куба, сумма чисел равна 1 (рассматриваются столбики всех трёх направлений). В некотором кубике записано число 10. Через этот кубик проходит три <i>слоя</i> 1×20×20, параллельных граням куба. Найдите сумму всех чисел вне этих слоёв.

а) Для каждого трёхзначного числа берём произведение его цифр, а затем эти произведения, вычисленные для всех трёхзначных чисел, складываем. Сколько получится? б) Тот же вопрос для четырёхзначных чисел.

Сколько целых чисел от 1 до 1997 имеют сумму цифр, делящуюся на 5?

При каком  <i>n</i> > 1  может случиться так, что в компании из  <i>n</i> + 1  девочек и <i>n</i> мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?

а) Может ли случиться, что в компании из 10 девочек и 9 мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?

б) А если девочек 11, а мальчиков 10?

На плоскости дан квадрат 8×8, разбитый на клеточки 1×1. Его покрывают прямоугольными равнобедренными треугольниками (два треугольника закрывают одну клетку). Имеется 64 черных и 64 белых треугольника. Рассматриваются "правильные" покрытия – такие, что каждые два треугольника, имеющие общую сторону, разного цвета. Сколько существует правильных покрытий?

Каждый из 450 депутатов парламента дал пощёчину ровно одному своему коллеге.

Докажите, что можно избрать парламентскую комиссию из 150 человек, среди членов которой никто никого не бил.

В каждой клетке квадрата  8×8  клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть

  а) больше 15?

  б) больше 20?

Рассматривается числовой треугольник: <div align="center"><img src="/storage/problem-media/98176/problem_98176_img_2.gif"></div>(первая строчка задана, а каждый элемент остальных строчек вычисляется как разность двух элементов, которые стоят над ним). В 1993-й строчке – один элемент. Найдите его.

Муравей ползает по проволочному каркасу куба, при этом он никогда не поворачивает назад.

Может ли случиться, что в одной вершине он побывал 25 раз, а в каждой из остальных – по 20 раз?

В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, причём сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четырёх вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях?

(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)

В ряд стоят 30 сапог: 15 левых и 15 правых. Докажите, что среди некоторых десяти подряд стоящих сапог левых и правых поровну.

Найти число решений в натуральных числах уравнения   [^<i>x</i>/₁₀] = [^<i>x</i>/₁₁] + 1.

Можно ли провести в каждом квадратике на поверхности кубика Рубика диагональ так, чтобы получился несамопересекающийся путь?

Можно ли нарисовать на поверхности кубика Рубика такой замкнутый путь, который проходит через каждый квадратик ровно один раз (через вершины квадратиков путь не проходит)?

Тетрадный лист раскрасили в 23 цвета по клеткам. Пара цветов называется хорошей, если существует две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?