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

Кружок 5 класса

Руководители Евгений Александрович Асташов и Ирина Сергеевна Засыпкина
2011/2012 учебный год

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

Основные задачи

Комментарий. Все задачи этого занятия решаются аналогично задачам 0 и 1. Прочитайте решения к этим задачам, а затем решите остальные самостоятельно, применяя похожие рассуждения. Задача 0 решается методом доказательства «от противного». На нем же основан принцип решения задачи 1 и всех последующих. Этот принцип и называется принципом Дирихле (более точную его формулировку мы здесь приводить не будем).

0.

В коробке лежат шарики двух цветов. Сколько шариков достаточно наугад вынуть из коробки, чтобы среди них заведомо нашлись два одноцветных?

Ответ Решение

Ответ. Достаточно взять три шарика.

Решение.

Ясно, что двух шариков будет недостаточно: может оказаться, что они разных цветов. Поэтому нужно взять не меньше трех шариков.

Докажем, что трех шариков достаточно. Предположим противное (то есть противоположное), а именно, что трех шариков недостаточно (то есть что среди трех шариков может и не найтись двух одноцветных). Если три все шарика разноцветные, то они покрашены в три цвета. Но в коробке есть шарики только двух цветов. Это противоречие означает, что наше предположение было неверным. А стало быть, среди трех шариков всегда найдутся два одноцветных

1.

а): Семерых кроликов посадили в шесть клеток. Докажите, что есть клетка, в которой оказалось хотя бы два кролика.
б): Семерых кроликов посадили в три клетки. Докажите, что есть клетка, в которой оказалось хотя бы три кролика.

Решение

Решение.

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

б) Предположим, что это не так, то есть что в каждой клетке оказалось не больше двух кроликов. Тогда всего кроликов могло быть не больше 3·2=6. Но по условию задачи их было 7. Полученное противоречие показывает, что наше предположение было неверным. Стало быть, на самом деле найдется клетка, в которой оказалось хотя бы три кролика.

Замечание. При решении следующих задач полезно каждый раз понимать, кто (или что) выполняет роль «клеток», а кто (или что) роль кроликов. Однако, выяснив это, не ссылайтесь на решения предыдущих задач, а проводите аналогичные рассуждения заново.

2.

В лесу растет миллион лиственниц. Известно, что на каждой из них не более 400 000 иголок. Докажите, что в лесу найдутся по крайней мере три лиственницы с одинаковым числом иголок.

3.

За победу в математической регате команда из четырех человек получила 10 конфет. Дети поделили конфеты между собой, не разламывая их. Определите, всегда ли верны ли следующие утверждения:

а): «кому-то досталось по крайней мере 2 конфеты»;
б): «кому-то досталось по крайней мере 3 конфеты»;
в): «по крайней мере двум людям досталось по крайней мере по две конфеты»;
г): «каждому досталась хотя бы одна конфета»;
д): «кому-то досталась ровно две конфеты»;
е): «кому-то досталась ровно одна конфета».

4.

В ящике лежат шары: 5 красных, 7 синих и 1 зеленый. Сколько шаров надо вынуть, не глядя, чтобы среди них наверняка оказалось 2 шара одного цвета?

5.

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

6.

а): В школе 400 учеников. Верно ли, что хотя бы двое их них родились в один день года?
б): Верно ли, что в группе из 10 человек всегда найдутся двое, родившиеся в один день недели?
в): Верно ли, что в классе из 25 человек всегда найдутся трое, родившиеся в одном и том же месяце (не обязательно в один год)?

7.

В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки только одного сорта. Найдутся ли 9 ящиков с яблоками одного и того же сорта?

8.

В классе 30 человек. Андрей сделал в диктанте 13 ошибок, а остальные — меньше. Докажите, что по крайней мере три ученика сделали равное количество ошибок.

Дополнительные задачи

9.

Плоскость раскрашена в два цвета. Докажите, что найдутся две точки на расстоянии 1 м друг от друга, раскрашенные в один и тот же цвет.

10.

У человека на голове не более 400 000 волос, в Москве более 8 миллионов жителей. Докажите, что найдутся 20 москвичей с одинаковым числом волос на голове.

11.

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

12.

Каждая клетка таблицы размером 2011×2011 покрашена в один из 2010 цветов. За один ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Всегда ли можно за несколько ходов покрасить всю таблицу в один цвет?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!