занятие 16

Тема: Делимость и остатки

4. Принцип Дирихле

     Многие из вас слышали о принципе Дирихле в такой вот шутливой формулировке: "Если в N клетках сидят не менее N + 1 кроликов, то в какой-то из клеток сидит не менее двух кроликов". Обратите внимание на расплывчатость выводов - "в какой-то из клеток", "не менее". Это является отличительной чертой принципа Дирихле, которая иногда приводит к возможности неожиданных выводов на основе, казалось бы, совершенно недостаточных сведений.

     Доказательство самого принципа чрезвычайно просто, в нем используется тривиальный подсчет кроликов в клетках. Если бы в каждой клетке сидело не более одного кролика, то всего в наших N клетках сидело бы не более N кроликов, что противоречило бы условию. Таким образом, мы доказали принцип Дирихле, применив (обязательно обратите на это внимание) метод доказательства "от противного".

     Но, скажите на милость, о каких кроликах может идти речь в следующей задаче?

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

     Решение. Достанем из мешка три шарика. Если бы среди этих шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шаров, что противоречит тому, что мы достали три шарика. Ну а двух шариков может и не хватить.

Кроликами здесь являются шарики, а клетками - их цвета - черный и белый.

Но вам эта задача больше знакома, как задача из серии "в худшем случае".

Ответ: 3

     Задача 2. В лесу растет миллион ёлок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым количеством иголок.

     Решение. Перед нами миллион "кроликов" - ёлок и всего 600001 "клетка" с номерами от 0 до 600000. Посадим каждого "кролика"-ёлку в "клетку" с номером, равным количеству иголок на этой ёлке. Так как "кроликов"-ёлок гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере 2 "кролика". Но ведь, если 2 "кролика"-ёлки сидят в одной клетке, то количество иголок у них одинаково.

Задачи для самостоятельного решения

     

     Задача 3. Дано 12 целых чисел. Докажите (с помощью принципа Дирихле!), что из них можно выбрать два, разность которых делится на 11.

     Задача 4. В городе Санкт-Петербурге живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос.

     Задача "не в тему №1". Пять прямых пересекаются в одной точке. Известно что угол 1 равен 50 градусов, угол 2 равен углу 3 и равен 20 градусов, а угол 4 вдвое больше угла 5. Не производя никаких измерений, найдите величину угла 5.

     

     Задача "не в тему №2". Найдите наименьшее натуральное число n такое, что число     делится на 2004.  

Ответы и решения

     Задача 3. Чисел 12. Какое бы число мы ни взяли, оно будет делиться нацело на 11 (остаток 0), либо будет давать остаток 1, 2, 3, 4, 5, 6, 7, 8, 9 или 10.

Итак, в этой задаче в роли кроликов выступают 12 чисел, а в роли клеток - 11 остатков от деления на 11 (0-10). Хотя бы два кролика поневоле окажутся в одной клетке, то есть хотя бы два числа будут иметь одинаковые остатки при делении на 11. Тогда разность этих чисел с одинаковым остатком будет кратна 11. 

Чтобы было понятнее, приведу пример (помните, что пример не является доказательством!). Числа 23 и 45 имеют остаток 1 при делении на 11, их разность 

45 - 23 = 22, а 22 кратно 11.

     Задача 4. Итак, клеток-волос -  1000000 (от 0 до 999999). Санкт-Петербуржцев - более 5 миллионов. Садим каждого петербуржца в клетку с номером, равным количеству волос у него на голове. Отдельных клеток на всех не хватит. Делаем вывод.

     Задача "не в тему №1". Для каждого пронумерованного угла есть парный, вертикальный с ним угол. Поскольку вертикальные углы равны, то на чертеже имеется 2 угла по 50 градусов, 4 угла по 20 градусов, два угла по х градусов, и 2 угла по 2х градусов. Суммарная же градусная мера этих 10 углов равна 360 градусов.

6х + 180 = 360

6х = 180

х = 30

30 градусов - это угол 5.

     Ответ: угол 5 равен 30 градусов

     Задача "не в тему №2". Разложим число 2004 на простые множители:
2004     2
1002     2
 501      3
 167     167
     1

Разложим n^2 + n   на множители: n^2 + n  = n(n + 1), тогда один из этих множителей обязательно должен делиться на 167. Если n кратно числу 167, то получаем наименьшее число 167(167 + 1) = 28056 и оно кратно 2004. Если же n + 1 кратно 167, то n может равняться 166 (не подходит - показывает проверка), 333,..., но это уже не наименьшее значение;  наименьшее n уже найдено - это число 167.
     Ответ: n = 167