Олимпиадные задачи по теме «Принцип Дирихле» для 4-10 класса - сложность 3 с решениями

В классе 27 учеников. Каждый из учеников класса занимается не более чем в двух кружках, причём для каждых двух учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимаются не менее 18 учеников.

Каждый из учеников класса занимается не более чем в двух кружках, причём для любой пары учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимается не менее ⅔ всего класса.

Даны  <i>n</i> + 1  попарно различных натуральных чисел, меньших 2<i>n</i>  (<i>n</i> > 1).

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

Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число <i>N</i> от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно <i>N</i> орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?

Банк обслуживает миллион клиентов, список которых известен Остапу Бендеру. У каждого есть свой PIN-код из шести цифр, у разных клиентов коды разные. Остап Бендер за один ход может выбрать любого клиента, которого он еще не выбирал, и подсмотреть у него цифры кода на любых <i>N</i> позициях (у разных клиентов он может выбирать разные позиции). Остап хочет узнать код миллионера Корейко. При каком наименьшем <i>N</i> он гарантированно сможет это сделать?

В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.

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

Какое наименьшее количество нулей может быть среди этих чисел?

Прямую палку длиной 2 метра распилили на <i>N</i> палочек, длина каждой из которых выражается целым числом сантиметров. При каком наименьшем <i>N</i> можно гарантировать, что, использовав все получившиеся палочки, можно, не ломая их, сложить контур некоторого прямоугольника?

Вершины правильного 45-угольника раскрашены в три цвета, причём вершин каждого цвета поровну. Докажите, что можно выбрать по три вершины каждого цвета так, чтобы три треугольника, образованные выбранными одноцветными вершинами, были равны.

В квадрате со стороной, равной 1, произвольно берут 101 точку (не обязательно внутри квадрата, возможно, часть на сторонах), причём никакие три из них не лежат на одной прямой. Докажите, что существует треугольник с вершинами в этих точках, площадь которого не больше 0,01.

Два муравья проползли каждый по своему замкнутому маршруту на доске 7×7. Каждый полз только по сторонам клеток доски и побывал в каждой из 64 вершин клеток ровно один раз. Каково наименьшее возможное число таких сторон, по которым проползали и первый, и второй муравьи?

На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека <i>объявляются</i> друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?

В каждой клетке квадратной таблицы написано по действительному числу. Известно, что в каждой строке таблицы сумма <i>k</i> наибольших чисел равна <i>a</i>, а в каждом столбце таблицы сумма <i>k</i> наибольших чисел равна <i>b</i>.

  а) Докажите, что если  <i>k</i> = 2,  то  <i>a = b</i>.

  б) В случае  <i>k</i> = 3  приведите пример такой таблицы, для которой  <i>a ≠ b</i>.

В каждой клетке квадратной таблицы написано по числу. Известно, что в каждой строке таблицы сумма двух наибольших чисел равна <i>a</i>, а в каждом столбце сумма двух наибольших чисел равна <i>b</i>. Докажите, что  <i>a = b</i>.

В школе решили провести турнир по настольному теннису между математическими и гуманитарными классами. Команда гуманитарных классов состоит из <i>n</i> человек, команда математических – из <i>m</i>, причём  <i>n</i> ≠ <i>m</i>.  Так как стол для игры всего один, было решено играть следующим образом. Сначала какие-то два ученика из разных команд начинают играть между собой, а все остальные участники выстраиваются в одну общую очередь. После каждой игры человек, стоящий в очереди первым, заменяет за столом члена своей команды, который становится в конец очереди. Докажите, что рано или поздно каждый математик сыграет с каждым гуманитарием.

На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.

Докажите, что у семи из них есть общий дедушка.

В течение92дней авиакомпания ежедневно выполняла по десять рейсов. За день каждый самолет выполнял не более одного рейса. Известно, что для любой пары дней найдется один и только один самолет, летавший в оба эти дня. Докажите, что есть самолет, летавший каждый день.

Какое наименьшее количество трехклеточных уголков можно разместить в квадрате8<i>× </i>8так, чтобы в этот квадрат больше нельзя было поместить ни одного такого уголка?

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

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

В бесконечной возрастающей последовательности натуральных чисел каждое делится хотя бы на одно из чисел 1005 и 1006, но ни одно не делится на 97. Кроме того, каждые два соседних числа отличаются не более чем на <i>k</i>. При каком наименьшем <i>k</i> такое возможно?

В некоторых клетках доски 10×10 поставили <i>k</i> ладей, и затем отметили все клетки, которые бьёт хотя бы одна ладья (ладья бьёт и клетку, на которой стоит). При каком наибольшем <i>k</i> может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?

Легко разместить комплект кораблей для игры в "Морской бой" на доске 10× 10 (см. рис.). А на какой наименьшей квадратной доске можно разместить этот комплект? (Напомним, что согласно правилам корабли не должны соприкасаться даже углами.)

<center><i> <img align="absmiddle" src="/storage/problem-media/115384/problem_115384_img_2.gif"> </i></center>

300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.

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

б) Все вершины пирамиды лежат в плоскостях граней куба, но не на прямых, содержащих его ребра, причем в плоскости каждой грани лежит хотя бы одна вершина. Какое наибольшее количество вершин может иметь пирамида?