Принцип Дирихле
Формулировка: Если в n "клетках" сидят не менее n+1 "кроликов", то в какой-то из "клеток" сидят не менее 2-х "кроликов". (Термины "кролики" и "клетки" являются общепринятыми в математике и будут применяться в том числе и в данной лекции.)
Доказательство: Противоречие к формулировке звучит так: "в каждой клетке сидит не более одного кролика". Но тогда кроликов, очевидно, не больше, чем клеток?! Поэтому есть клетка, где кроликов не менее двух ч.т.д.
(!) Принцип Дирихле и различные его усиления - едва ли не самая частая идея в олимпиадных задачах, поэтому на данную лекцию стоит обратить особое внимание. Точные оценки в различных обобщениях (п.3 и п.4) следует помнить наизусть, поскольку они в точности подходят ко многим задачам.
Различные усиления, обобщения и т.п.:
1. Если в n клетках сидят не более n-1 кроликов, то есть пустая клетка.
Также доказывается от противного (как и все последующие пункты): если пустой клетки нет, то в каждой клетке сидит хотя бы 1 кролик. Тогда кроликов не меньше, чем клеток?! Значит, пустая клетка есть, ч.т.д.
2. Если в n клетках сидят ровно n кроликов, то либо в каждой клетке сидит ровно один кролик, либо есть и пустая клетка, и клетка, в которой не менее 2-х кроликов.
Действительно, если не в каждой клетке сидит ровно 1 кролик, то либо (а) есть пустая клетка, либо (б) есть клетка, в которой не менее 2-х кроликов. В случае (а) у нас n кроликов оказываются рассаженными в n-1 клеток, поэтому, по принципу Дирихле, есть и клетка, в которой не менее 2-х кроликов ч.т.д. В случае (б) у нас не более n-2 оставшихся кроликов оказываются рассаженными в n-1 клеток, следовательно, по п.1, есть и пустая клетка ч.т.д.
(!) П.2 очень полезен в тех случаях, когда мы знаем, что ровно по одному кролику в каждой клетке сидеть не может.
3. Если в n клетках сидят не менее n*(k-1)+1 кроликов, то в какой-то из клеток сидят не менее k кроликов.
Действительно, если в каждой клетке сидит не более k-1 кролика, то во всех клетках сидит не более n*(k-1) кроликов, а их хотя бы на 1 больше?! ч.т.д.
4. Если в n клетках сидят не более n*(k+1)-1 кроликов, то в какой-то из клеток сидят не более k кроликов.
Действительно, если в каждой клетке сидит не менее k+1 кролика, то во всех клетках сидит не менее n*(k+1) кроликов, а их хотя бы на 1 меньше?! ч.т.д.
5. (Это утверждение обобщает принцип Дирихле на случай нецелого числа кроликов.) Если сумма n чисел равна S, то среди них есть число, не меньшее S/n, и число, не большее S/n.
Действительно, если все числа (строго!) меньше S/n, то их сумма меньше S, а если все числа (строго!) больше S/n, то их сумма больше S. В обоих случаях получаем противоречие ч.т.д.
(!) На принцип Дирихле при решении задач на олимпиаде можно прямо ссылаться, на обобщения и усиления - не рекомендуется. Легче подставить в нужное место решения доказательство соответствующего утверждения. Слова "принцип Дирихле" в таком случае можно вообще не упоминать ;-)
Примеры:
Задача 1. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
Решение: 3 шарика. Это - просто применение принципа Дирихле: кроликами будут взятые шарики, а клетками - черный и белый цвета. Клеток две, поэтому если кроликов хотя бы три, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика). С другой стороны, взять два шарика мало, потому что они могут быть двух разных цветов.
Задача 2. Дано 233 целых числа. Доказать, что разность каких-то двух из них делится на 232. (Принцип Дирихле часто используется и в задачах по теории чисел !)
Решение: У нас есть 233 числа, которые мы, скорее всего, сделаем кроликами. Найдем подходящие клетки: их должно быть не более 232, и разность 2-х чисел, "сидящих в одной клетке" должна делится на 232. Остатки от деления на 232 как раз подходят. Применяем принцип Дирихле для 233 кроликов-чисел и 232 клеток-остатков и получаем требуемое. (В теоретико-числовых задачах на Дирихле чаще всего клетками бывают остатки от деления чего-либо на какое-то число !)
Задача 3. В магазин привезли 25 ящиков яблок 3-х сортов (в каждом ящике все яблоки одного сорта). Доказать, что среди них есть, по крайней мере, 9 ящиков с яблоками одного сорта.
Решение: Возьмем ящики в качестве кроликов и сорта в качестве клеток. Тогда нам в точности подходит утверждение п.3 при n=3, k=9.
Задача 4. Пятеро программистов получили на всех зарплату - 1750 долларов. Каждый из них хочет купить себе новый компьютер за 360 долларов. Докажите, что кому-то из них это не светит.
Решение: Воспользуемся утверждением п.5 для n=5, S=1750. Тогда понятно, что зарплата одного из программистов не более S/n=350 долларов. Ему и не светит покупка.
Очень часто в задаче на принцип Дирихле нужны разные дополнительные соображения (либо он вообще появляется, как промежуточное соображение):
Примеры:
Задача 1. На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Доказать, что кто-то из них решил не менее 5 задач.
Решение: (Стандартное соображение: если известно, что какие-то объекты есть, то есть хотя бы по одному экземпляру, который можно выделить и рассмотреть !) Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. Если взять задачи в качестве кроликов и школьников в качестве клеток, то получается в точности утверждение п.3 при n=7, k=5 ч.т.д.
Задача 2. Докажите, что равностронний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками. (Да, принцип Дирихле иногда используется и в геометрии !)
Решение: Главное соображение: меньший равносторонний треугольник, как его не клади, не сможет покрыть 2 вершины большего. Поэтому, взяв вершины в качестве клеток и маленькие треугольники в качестве кроликов, мы получим, что кроликов меньше, чем клеток (утверждение п.1 !), откуда следует, что есть пустая клетка. Это означает, что какую-то из вершин большого треугольника мы никогда не накроем, поэтому и не накроем его целиком ч.т.д.
Задача 3. На планете в звездой системе Тау Кита суша занимает больше половины площади. Доказать, что таукитяне смогут прорыть прямой туннель через центр планеты так, чтобы он соединял сушу с сушей..
Решение: (Да, эта задача в некотором смысле тоже на принцип Дирихле !) Возьмем на планете множество точек суши и множество точек, диаметрально противоположных суше. Сумма площадей этих множеств - удвоенная площадь суши, что строго больше площади планеты. Тогда эти 2 множества перекроются. В точке перекрытия и можно будет начать рыть туннель.
"Решение" №2: (Проясняющее связь с принципом Дирихле) Будем считать кроликами точки суши, а клетками - пары диаметрально противоположных точек планеты. "Количество" кроликов в данном случае - это площадь суши, а "количество" клеток - половина площади планеты. Поскольку площадь суши больше половины площади планеты, то "кроликов больше, чем клеток". Тогда есть клетка, в которой сидит не менее двух кроликов, т.е. пара противоположных точек, обе из которых - суша. Эти точки и надо соединить туннелем.
Задача 4. За круглым столом сидят 100 человек, причем более половины из них - рыцари. Доказать, что какие-то два рыцаря сидят напротив друг друга
Решение: (Эта задача имеет подчеркнутое сходство с предыдущей). Будем считать кроликами рыцарей, а клетками - пары диаметрально противоположных мест за столом. Клеток тогда ровно половина от числа мест за столом (т.е. 50), а кроликов - строго больше. Тогда есть клетка, в которой сидит не менее двух кроликов, т.е. пара противоположных мест, за которыми сидят два рыцаря. Они и есть искомые.
(!) Совершенно необходимо понять, почему "решение" №2 предпоследней задачи не является корректным решением. Принцип Дирихле формулировался и доказывался нами только для конечного числа клеток и кроликов. Здесь же мы имеет дело с бесконечным числом точек, а сравнение бесконечно больших величин, в общем случае - отдельная глубокая теория (в частности, к ней относится знаменитая континуум-гипотеза). Однако именно для случая покрытий геометрических фигур верен принцип Дирихле, сформулированный в терминах площади так, как указано ниже.
Переформулировка принципа Дирихле для площадей и покрытий фигур:
0. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) больше S, то у нее имеется точка, покрытая не менее 2-х раз (именно им мы и пользовались, решая последнюю задачу 3).
1. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) меньшеS, то у нее имеется точка, ни покрытая ни разу.
2. Если фигура площади S покрыта несколькими фигурами с суммой площадей ровно S, то либо каждая точка покрыта ровно один раз, либо есть и точка, не покрытая ни разу, и точка, покрытая не менее 2-х раз.
3. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) больше (k-1)*S, то у нее имеется точка, покрытая не менее k раз.
4. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) меньше (k+1)*S, то у нее имеется точка, покрытая не более k раз.
(!) Обратите внимание, что эти утверждения является прямой аналогией утверждений с тем же номером, обобщающих простой принцип Дирихле. Строгих доказательств этих утверждений мы не приводим, тем более что в условиях олимпиады гораздо легче и лучше ссылаться на них, как на очевидные, чем пытаться вспомнить и записать доказательство ;-)
Принцип Дирихле
В простейшем виде его выражают так: «Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух кроликов».
Общая формулировка: «Если n кроликов сидят в k ящиках, то найдётся ящик, в котором сидят не меньше чем n/k кроликов, и найдётся ящик, в котором сидят не больше чем n/k кроликов». Пусть вас не смущает дробное число кроликов – если получится, что в ящике не меньше 7/3 кроликов, значит, их не меньше трёх.
Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.
Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше чем n/k*k = n. Противоречие.
Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, не ящики.
Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы В – ящиками.
Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего).
Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава – роль кроликов, сидящих в ящиках.
Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение. Всего в году 365 дней. Назовём дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, т.е. больше одного. Следовательно, не меньше двух.
Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.
Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 х 6 из чисел +1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.
Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться от –6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит, составить такой квадрат невозможно.
Пример 3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.
Решение. Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной к ней.
Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2,3,4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на контрольных?
Решение. Рассмотрим множество наборов из трёх оценок за соответствующие контрольные. Количество таких наборов равно 43 или 64 (4 возможности за каждую из трёх контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.
Задачи
1. 1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные – меньше. Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.
2. 2. На земле больше 4 миллиардов человек, которые моложе 100 лет. Докажите, что на Земле есть два человека, родившихся в одну и ту же секунду.
3. 3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15о.
4. 4. В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка а) одного цвета; б) разных цветов; в) чёрного цвета?
5. 5. На карьере добыли 36 камней. Их веса соответственно 490 кг, 495 кг, 500 кг, …, 665 кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трёхтонных грузовиках?
6. 6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер?
7. 7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем не знакомы).
8. 8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.
9. 9. Квадратная таблица (2n + 1) x (2n + 1) заполнена числами от 1 до 2n + 1 так, чтобы в каждой строке и в каждом столбце были представлены все эти числа. Докажите, что если это расположение симметрично относительно главной диагонали, то на главной диагонали тоже представлены все эти числа.
10. 10. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
11. 11. Комиссия из 60 человек провела 40 заседаний, причём на каждом заседании присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.
12. 12. На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола до концов минутных стрелок будет больше, чем сумма расстояний от центра стола до центров часов.
13. Каждая из 9 прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.