МАЛЫЙ МЕХМАТ МГУ

Занятие 2. Принцип Дирихле

Начнём с решения четвёртой задачи письменной работы. Напомним условие:

Каждый из 65 школьников написал по три контрольные работы и получил за каждую из них одну из оценок 2, 3, 4 или 5. Докажите, что существуют по крайней мере два школьника, оценки которых неотличимы.

Выясним прежде всего, сколько существует различных наборов оценок, которые может получить школьник за три контрольные работы. За первую контрольную работу можно получить одну из четырёх оценок. В каждом из этих случаев за вторую работу можно получить одну из четырёх оценок. Значит, оценки за две работы можно получить 4 · 4 = 16 способами. В каждом из этих 16 случаев можно получить одну из четырёх оценок за третью работу. Итого: 16 · 4 = 64 вариантов оценок за три работы.

Поэтому если бы все школьники получили различные наборы оценок, то общее число школьников не превышало бы 64. А по условию их 65. Полученное противоречие показывает, что предположение было неверным, значит, какие-то два школьника получили одинаковые наборы оценок.

Приведённое рассуждение использует принцип Дирихле, одна из возможных формулировок которого следующая: «Если в n клетках сидят более чем n кроликов, то хотя бы в одной из клеток находится не менее двух кроликов.» Несмотря на очевидность этого утверждения, его применение позволяет решать и более сложные задачи.

1.	Докажите, что если в классе 25 учеников, то непременно найдутся трое, которые отмечают свои дни рождения в одном месяце.
2.	В мешке лежат шарики трёх цветов: чёрные, белые и синие. Какое наименьшее число шариков нужно вынуть из мешка, чтобы среди них заведомо оказалось три одноцветных?
3.	В каждую клетку таблицы 3×3 записали одно из чисел –1, 0 или 1, а затем нашли суммы чисел в каждой строке, в каждом столбце и на каждой диагонали. Докажите, что среди полученных чисел имеются равные.
4.	В футбольном турнире в один круг (это значит, что каждая команда играет с каждой по одному разу) принимают участие 16 команд. Докажите, что в любой момент турнира найдутся две команды, сыгравшие одинаковое число матчей.
5.	В классе 25 учеников. Известно, что среди любых трёх из них двое дружат между собой. Докажите, что есть ученик, у которого не менее 12 друзей.
6.	Аня, Боря, Вася, Галя, Даша и Егор собирали грибы. Больше всех грибов собрала Аня, а меньше всех — не Галя и не Даша. Верно ли, что девочки собрали грибов не меньше, чем мальчики?
7.	Числа от 1 до 64 расставили в клетках таблицы 8×8 (по одному в каждую клетку). Докажите, что найдутся две соседние (имеющих общую сторону) клетки, разность чисел в которых не менее 5.
8.	На квадратном столе со стороной 70 см лежит 100 квадратных салфеток со стороной 10 см. Докажите, что в стол можно вбить гвоздь, который проткнёт не менее трёх салфеток.
9.	Докажите, что из любых ста натуральных чисел можно выбрать несколько, сумма которых делится на 100.
10.	В ряд стоят 30 сапог: 15 правых и 15 левых. Обязательно ли среди них найдутся а) 20; б) 10 подряд стоящих сапог, среди которых правых и левых поровну?

Занятие 2. Письменная работа (для новичков)

1.	Аня, Боря, Вася, Галя, Даша и Егор собирали грибы. Больше всех грибов собрала Аня, а меньше всех — не Галя и не Даша. Верно ли, что девочки собрали грибов не меньше, чем мальчики?
2.	Является ли точным квадратом число, десятичная запись которого состоит из 1999 троек?
3.	Даны две окружности и точка. Постройте отрезок, концы которого лежат на данных окружностях, а середина — в данной точке.
4.	В каждую клетку таблицы 3×3 записали одно из чисел -1, 0 или 1, а затем нашли суммы чисел в каждой строке, в каждом столбце и на каждой диагонали. Докажите, что среди полученных чисел имеются равные.
5.	Вася сказал, что поедет в воскресенье в лес, если не будет дождя и хотя бы один из его друзей — Петя или Коля — тоже поедет. Сформулируйте, в каком случае Вася не поедет в воскресенье в лес.
6.	Может ли прямая, нарисованная на клетчатой бумаге, проходить ровно через два центра клеток?
7.	Может ли тень куба быть шестиугольной?