| Предыдущее занятие | | В начало | | Следующее занятие |
|---|
Принцип Дирихле гласит:
Пусть в клетках сидит не меньше, чем N+1 кроликов. Тогда найдется клетка, в которой сидит не меньше двух кроликов.
Оказывается, что это простое утверждение помогает в решении самых разных задач. Главное √ понять, что в данной задаче √ клетки, а что √ кролики.
Иногда используют обобщенный принцип Дирихле: Пусть в N клетках сидит k кроликов. Тогда найдется клетка, в которой сидит не меньше k/N кроликов, и найдется клетка, в которой сидит не больше k/N кроликов.
Попробуйте применить эти принципы в следующих задачах.
Вводные задачи
3.1. Шесть школьников съели семь конфет.
а) Докажите, что один из них съел не менее двух конфет.
б) Верно ли, что кто-то съел ровно две конфеты?
3.2. У человека на голове не более 400000 волос, в Москве более 8 млн жителей. Докажите, что найдутся 20 москвичей с одинаковым числом волос.
3.3. В классе 15 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем два ученика этого класса ?
3.4. Петя хочет написать на доске 55 различных двузначных чисел так, чтобы среди них не было двух чисел, дающих в сумме 100. Сможет ли он это сделать?
3.5. В ковре размером 4 х 4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1 х 1 метр, не содержащий внутри себя дырок. (Дырки считаются точечными).
Задачи для самостоятельного решения
3.6. Докажите, что среди любых трех целых чисел можно найти два, сумма которых четна.
3.7. В некотором классе учится 30 не очень грамотных учеников. Во время диктанта один ученик сделал 14 ошибок, но зато остальные меньше. Докажите, что в классе имеются но крайней мере три ученика, сделавшие в диктанте одинаковое количество ошибок.
3.8*. Докажите, что в Вашем классе найдутся два человека, имеющие одинаковое число друзей среди своих одноклассников.
3.9. В клетках шахматной доски 8 х 8 записаны числа 1, 2, 3, ..., 62, 63, 64. Докажите, что найдутся две такие соседние клетки, что числа, записанные в них, отличаются не меньше, чем на 9. (Соседними считаются клетки, имеющие общую сторону или вершину).
3.10. На далекой планете Зям-лям, имеющей форму шара, суша занимает более половины поверхности планеты. Докажите, что можно прорыть прямой туннель, проходящий через центр планеты и соединяющий сушу с сушей.
Ответы и указания
3.1. а) Указание: примените принцип Дирихле, считая, что, "клетки" √ это школьники, а "кролики" √ это конфеты.
б) Не обязательно: например, все семь конфет мог съесть один школьник.
3.2. По условию на голове у каждого из москвичей может быть от 0 до 400000 волос √ имеем всего 400001 возможность. Предположим, что утверждение задачи неверно. Тогда лысых москвичей найдется не более 19, имеющих 1 волос √ тоже не более 19, ..., имеющих 400000 волос √ тоже не более 19. Но тогда всего москвичей не более 19 ╧ 400001 = 7600019, что меньше 8 миллионов √ противоречие.
3.3. Да, найдется: всего месяцев 12, а учеников 15 ) 12. Здесь "кролики" √ это ученики, а "клетки" √ это месяцы.
3.4. Ответ: нет, не сможет. Разобьем все числа от 10 до 90 (кроме 50) на пары (10, 90), (11, 89), ..., (49, 51). В каждой паре сумма чисел равна 100. Таких пар 40, и еще есть 10 чисел без пары: это числа 50, 91, 92, ..., 99 √ всего 50 "клеток". Так как Петя хочет написать 55 чисел, а 55 ) 50, то он обязательно напишет два числа из одной пары √ их сумма и будет равна 100.
3.5. Разрежем ковер тремя вертикальными и тремя горизонтальными разрезами на 16 одинаковых ковриков размером 1 х 1 метр. Поскольку 16 ) 15, то один из ковриков будет без дыр.
3.6. Рассмотрим на плоскости треугольник, все три стороны которого равны 1 метру. По принципу Дирихле, из трех его вершин какие-то две будут окрашены одинаково.
ПРИНЦИП ДИРИХЛЕ (Задачи внекласной работы)
1. В классе 30 человек. В диктанте Витя Малеев сделал 12 ошибок, а каждый из остальных √ не больше. Докажите, что по крайней мере трое учеников сделали одинаковое количество (быть может, и ноль) ошибок.
2. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?
3. В шкафу лежат вперемешку 5 пар светлых ботинок и 5 пар темных ботинок одинаковых размера и фасона. Какое наименьшее количество ботинок надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?
4. Принесли 5 чемоданов и 5 ключей от этих чемоданов, но неизвестно, какой ключ от какого чемодана. Сколько проб придется сделать в самом худшем случае, чтобы подобрать к каждому чемодану свой ключ?
5. В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько надо взять карандашей, чтобы среди них было не меньше 2-х красных и не меньше 3-х синих?
4. В ящике лежат цветные карандаши: 10 красных, 8 синих и 4 желтых. В темноте берем из ящика карандаши. Какое наименьшее число карандашей надо взять, чтобы среди них заведомо было:
а) не менее 4-х карандашей одного цвета?
б) не менее 6-ти карандашей одного цвета?
в) хотя бы 1 карандаш каждого цвета?
г) не менее 6-ти синих карандашей?
7. В погребе стоит 20 одинаковых банок с вареньем. В 8-ми банках клубничное варенье, в 7-ми √ малиновое, в 5-ти √ вишневое. Каково наибольшее число банок, которые можно в темноте вынести из погреба с уверенностью, что там осталось еще хотя бы 4 банки одного сорта варенья и 3 банки другого?
8. В соревнованиях по вольной борьбе участвовало 12 человек. Каждый участник должен был встретиться с каждым из остальных по одному разу. Докажите, что в любой момент соревнования имеются два участника, проведшие одинаковое число схваток.
Принцип Дирихле (ответы)
2. Да.
3. Возьмем 10 ботинок. Может оказаться, что среди них 5 светлых на одну ногу и 5 темных тоже на одну ногу. В этом случае, если взять 11-й ботинок, он с одним из ранее взятых дает пару светлых или темных ботинок.
4. Первый ключ находит свой чемодан в худшем случае за 4 пробы, второй √ за 3, третий √ за 2, четвертый √ за 1, пятый подходит к оставшемуся чемодану. В худшем случае всего будет 10 проб.
5. 10 карандашей.
6. а) 10; 6) 15; в) 19; г) 20.
7. Можно вынести 7 банок.
8. Каждый участник должен провести 11 схваток. Распределим участников по группам. К 1-й группе отнесем тех, кто в данный момент не провел ни одной схватки; ко второй √ тех, кто провел одну схватку, и т. д. К последней, 12-й группе, отнесем тех, кто провел все 11 схваток. Но одновременно не могут существовать 1-я и 12-я группы. Так, если хотя бы один участник провел все схватки, то не может быть участника, который не провел бы ни одной схватки. Отсюда число групп может быть только 11, а число участников √ 12. По принципу Дирихле к одной из групп должно принадлежать, по крайней мере, два участника.
Принцип Дирихле
В простейшем виде его выражают так: ╓Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух Кроликов╞. Общая формулировка: ╓Если n кроликов сидят в k ящиках,то найдётся ящик, в котором сидят не меньшечем n/k кроликов, и найдется ящик, в котором сидят не больше чем n/k кроликов╞. Пусть вас не смущает дробное число кроликов■ если получится, что в ящике не меньше 7/3 кроликов, значит, их не меньше трех. Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше, чем (n/k)*k=n. Противоречие.
Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, ни ящики.
Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы B ■ ящиками.
Принцип Дирихле бывает непрерывным: ╓Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг╞ (а если кто-то съел больше среднего, то кто-то съел меньше среднего). И Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава,■ роль кроликов, сидящих в ящиках.
Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение. Всего в году бывает 366 дней. Назовем дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше Я кроликов, т.е. больше одного. Следовательно, не меньше двух.
Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.
Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 x 6 из чисел +1, √ 1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.
Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от √ 6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит составить такой квадрат невозможно.
Пример 3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.
Решение. Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмем эту точку вместе с противоположной к ней.
Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных?
Решение. Рассмотрим множество наборов из трех оценок за соответствующие контрольные. Количество таких наборов равно 4~ или 64 (4 возможности за каждую из трех контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.
Задачи
2. На Земле больше 4 миллиардов человек, которые моложе 100 лет, Докажите, что на Земле есть два человека, родившихся в одну и ту же секунду.
3. На плоскости проведено 12 прямых. Докажите,, что какие-то две из них образуют угол не больше 15╦.
4. В ящике лежат носки: 10 черных, 10 синих, 10 белых. Какое наименьшее количество носков, надо вынуть не глядя, чтобы сряди вынутых, оказалось два носка а) одного цвета; б) разных цветов; в) черного цвета?
5. На карьере добыли 36 камней. Их веса соответственно 490кг, 495кг, 500кг,┘, 665кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трехтонных грузовиках?
6. Какое наименьшее число карточек спортлото ╓6 из 49╞ надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер?
7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем незнакомы.)
8. Докажите, что из любых целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.
9. Квадратная таблица (2n+1) х (2n+1) заполнена числами от 1 до 2 так, что в каждой строке и в каждом столбце представлены все эти числа. Докажите, что если это расположение симметрично относительно главной диагонали, то на главной диагонали тоже представлены все эти числа.
10. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
11. Комиссия из 60 человек провела 40 заседаний, причем на каждом присутствовало ровно 10 членов комиссий. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.
12. На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола, до концов минутных стрелок будет больше, чем сумма расстояний от центра стола до центров часов.
13. Каждая из 9 прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что по крайней, мере три из этих прямых проходят через одну точку.
| Предыдущее занятие | | В начало | | Следующее занятие |
|---|