Олимпиадные задачи по теме «Принцип Дирихле» для 11 класса - сложность 3 с решениями
Принцип Дирихле
НазадЧичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число <i>N</i> от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно <i>N</i> орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?
Банк обслуживает миллион клиентов, список которых известен Остапу Бендеру. У каждого есть свой PIN-код из шести цифр, у разных клиентов коды разные. Остап Бендер за один ход может выбрать любого клиента, которого он еще не выбирал, и подсмотреть у него цифры кода на любых <i>N</i> позициях (у разных клиентов он может выбирать разные позиции). Остап хочет узнать код миллионера Корейко. При каком наименьшем <i>N</i> он гарантированно сможет это сделать?
В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.
На новом сайте зарегистрировалось 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>.
Какое наименьшее количество трехклеточных уголков можно разместить в квадрате8<i>× </i>8так, чтобы в этот квадрат больше нельзя было поместить ни одного такого уголка?
По кругу стоят 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре напёрстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?
В некоторых клетках доски 10×10 поставили <i>k</i> ладей, и затем отметили все клетки, которые бьёт хотя бы одна ладья (ладья бьёт и клетку, на которой стоит). При каком наибольшем <i>k</i> может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?
а) Все вершины пирамиды лежат на гранях куба, но не на его ребрах, причем на каждой грани лежит хотя бы одна вершина. Какое наибольшее количество вершин может иметь пирамида?
б) Все вершины пирамиды лежат в плоскостях граней куба, но не на прямых, содержащих его ребра, причем в плоскости каждой грани лежит хотя бы одна вершина. Какое наибольшее количество вершин может иметь пирамида?
В каждой клетке шахматной доски сидят по два таракана. В некоторый момент времени каждый таракан переползает на соседнюю (по стороне) клетку, причём тараканы, сидевшие в одной клетке, переползают в разные клетки. Какое наибольшее количество клеток доски может после этого остаться свободным?
Куб с ребром2<i>n+</i>1разрезают на кубики с ребром 1 и бруски размера2<i>x </i>2<i>x </i>1. Какое наименьшее количество единичных кубиков может при этом получиться?
В языке жителей Банановой Республики количество слов превышает количество букв в их алфавите. Докажите, что найдется такое натуральное<i> k </i>, для которого можно выбрать<i> k </i>различных слов, в записи которых используется ровно<i> k </i>различных букв.
Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.
Имеется таблица <i>n×n</i>, в <i>n</i> – 1 клетках которой записаны единицы, а в остальных клетках – нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?
Все вершины треугольника<i> ABC </i>лежат внутри квадрата<i> K </i>. Докажите, что если все их отразить симметрично относительно точки пересечения медиан треугольника<i> ABC </i>, то хотя бы одна из полученных трех точек окажется внутри<i> K </i>.
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
В стране 1993 города, и из каждого выходит не менее 93 дорог. Известно, что из каждого города можно проехать по дорогам в любой другой.
Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)
Даны таблица 100×100 клеток и <i>N</i> фишек. Рассматриваются все такие расстановки фишек в клетки таблицы, что никакие две фишки не стоят в соседних клетках. При каком наибольшем <i>N</i> в каждой из этих расстановок можно найти хотя бы одну фишку, от перемещения которой в соседнюю клетку заданное условие не нарушится? (Соседними считаются клетки, имеющие общую сторону.)
Попав в новую компанию, Чичиков узнавал, кто с кем знаком. А чтобы запомнить это, он рисовал окружность и изображал каждого члена компании хордой, причём хорды знакомых между собой пересекались, а незнакомых – нет. Чичиков уверен, что такой набор хорд есть для любой компании. Прав ли он? (Совпадение концов хорд считается пересечением.)
Рассмотрим степени пятерки: 1, 5, 25, 125, 625, ... Образуем последовательность их первых цифр: 1, 5, 2, 1, 6, ...
Докажите, что любой кусок этой последовательности, записанный в обратном порядке, встретится в последовательности первых цифр степеней двойки (1, 2, 4, 8, 1, 3, 6, 1, ...).
Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса – угадать масть как можно большее число раз. Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом. Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем
a) 19 карт;
б) 23 карт?
Рассмотрим последовательность, первые два члена которой равны 1 и 2 соответственно, а каждый следующий член – это наименьшее натуральное число, которое еще не встретилось в последовательности и которое не взаимно просто с предыдущим членом последовательности. Докажите, что каждое натуральное число входит в эту последовательность.
Имеется много карточек, на каждой из которых записано натуральное число от 1 до <i>n</i>. Известно, что сумма чисел на всех карточках равна <i>n</i>!·<i>k</i>, где <i>k</i> – целое число. Докажите, что карточки можно разложить на <i>k</i> групп так, чтобы в каждой группе сумма чисел, записанных на карточках, равнялась <i>n</i>!.
Несколько прямых, никакие две из которых не параллельны, разрезают плоскость на части. Внутри одной из этих частей отметили точку <i>A</i>.
Докажите, что точка, лежащая с <i>A</i> по разные стороны от всех данных прямых, существует тогда и только тогда, когда часть, содержащая <i>A</i>, неограничена.
а) В классе была дана контрольная. Известно, что по крайней мере ⅔ задач этой контрольной оказались <i>трудными</i>: каждую такую задачу не решили по крайней мере ⅔ школьников. Известно также, что по крайней мере ⅔ школьников класса написали контрольную <i>хорошо</i>: каждый такой школьник решил по крайней мере ⅔ задач контрольной. Могло ли такое быть? Изменится ли ответ, если везде в условии заменить ⅔ на б) ¾; в) <sup>7</sup>/<sub>10</sub>?