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

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

Многие вещи нам непонятны не потому, что наши понятия слабы; но потому, что сии вещи не входят в круг наших понятий.

В несерьезной форме принцип Дирихле гласит: 'Нельзя посадить 7 кроликов в 3 клетки, чтобы в каждой было не больше 2 кроликов.' Более общая формулировка: 'Если z зайцев сидят в k клетках, то найдется клетка, в которой не менее z/k зайцев.' Не надо бояться дробного число зайцев: если получается, что в ящике не меньше 7/3 зайцев, значит, их больше двух. Один математик сказал, что Дирихле по частоте упоминаний школьниками навсегда обеспечено одно из самых высших мест. И добавил: "Пожалуй, есть способ лишить его лидерства - назвать чьим-нибудь именем принцип 'никакое четное число не равно никакому нечетному'." Доказательство принципа Дирихле очень простое, но заслуживает внимания, поскольку похожие рассуждения 'от противного' часто встречаются. Допустим, что в каждой клетке число зайцев меньше, чем z/k. Тогда в k клетках зайцев меньше, чем k · z/k = z. Противоречие!

163.	В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года. Указание Указание. 400 > 366.
164.	В классе 40 учеников. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса? Ответ   Решение Ответ. Обязательно найдется. Решение. Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трех учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.
165.	В классе 30 учеников. В диктанте Вова сделал 13 ошибок, остальные меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну. Решение Решение. Каждый из остальных 29 учеников сделал не более 12 ошибок. Разобьем их на 13 групп по числу сделанных ошибок (от 0 до 12). (В некоторых группах учеников может и не быть). Если бы в каждой группе оказалось не более двух учеников, то во всех группах вместе было бы не более 26 учеников, а их 29. Значит, хотя бы в одной группе учеников больше двух.
166.	Из любых трех целых чисел можно выбрать два, сумма которых четна. Докажите это. Решение Решение. Все числа можно разбить на два класса: четные и нечетные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трех целых чисел найдутся два числа одинаковой четности. Их сумма четна.
167.	Среди любых шести целых чисел найдутся два числа, разность которых кратна 5. Докажите это. Указание Указание. Разбейте все множество целых чисел на 5 классов: в один класс поместите числа ...-14, -9, -4, 1, 6, 11, 16, 21, 26, ..., дающие остаток 1 при делении на 5, в другой - числа ...-13, -8, -3, 2, 7, 12, 17, 22, 27, ..., дающие остаток 2, в третий - числа, дающие остаток 3 при делении на 5, в четвертый класс - числа, дающие остаток 4 при делении на 5, наконец, пятый (или, если угодно, нулевой) класс составьте из чисел, кратных числу 5.
168.	Докажите, что из любых n + 1 целых чисел можно выбрать два числа, разность которых нацело делится на n. Указание Указание. Разбейте множество всех целых чисел на n классов в соответствии с тем, какой остаток они дают при делении на n.
169.	Даны 12 различных двузначных чисел. Докажите, что из них можно выбрать два числа, разность которых - двузначное число, записываемое двумя одинаковыми цифрами. Указание   Решение Указание. Двузначные числа, кратные 11 (и только они) записываются двумя одинаковыми цифрами. Решение. Рассмотрим остатки от деления данных чисел на 11. Поскольку разных остатков лишь 11 (0, 1, 2, ..., 9, 10), а чисел 12, то хотя бы два числа дают одинаковые остатки. Это означает, что разность этих чисел делится на 11. (Вообще говоря, нужно еще доказать, что эта разность является двузначным числом, но это очевидно: среди однозначных чисел только 0 делится на 11, а разность двух различных чисел не может равняться нулю.)
170.	Из любых ли ста целых чисел можно выбрать два числа, сумма которых кратна 7? Ответ   Решение Ответ. Не из любых. Решение. Возьмем, например, 100 целых чисел, каждое из которых дает остаток 1 при делении на 7. Из них невозможно выбрать два числа, сумма которых кратна 7.
171.	Существуют ли а) пятьдесят; б) более пятидесяти различных двузначных чисел, сумма никаких двух из которых не равна 100? Ответ Ответ. а) Да, например, числа от 50 до 99. б) Нет.
172.	Из любых ли а) 51; б) 52 целых чисел можно выбрать два числа, сумма или разность которых кратна 100? Решение Решение. б) Рассмотрим 51 ящик с табличками: [0], [1-99], [2-98], [3-97], ..., [49-51], [50]. Число помещаем в ящик, на табличке которого присутствует остаток от деления его на 100. Хотя бы два из 52 чисел окажутся вместе в некотором ящике.
173.	На шахматной доске стоят 44 ферзя. Докажите, что каждый из них бьет какого-нибудь другого ферзя. Указание   Решение Указание. При любом положении на доске ферзь бьет не менее 21 поля. Решение. Пусть какой-то из этих 44 ферзей не бьет никакого другого ферзя. Тогда все клетки, которые находятся под боем этого ферзя, пусты. А так как при любом положении на шахматной доске ферзь бьет не менее 21 поля, то занято ферзями не более 64 - 21 = 43 полей. Противоречие.
174.	Каждый из 10 участников переговоров послал по их окончании поздравительные открытки пятерым другим участникам. Докажите, что какие-то двое послали открытки друг другу. Указание   Решение Указание. Докажите сначала, что хотя бы один участник получил не менее пяти открыток. Решение. Всего было отправлено 50 открыток. Значит, существует участник, который получил не менее пяти открыток (если бы каждый получил не более четырех, то всего было бы отправлено не более 40 открыток). Таким образом, он послал открытки пятерым участникам и получил открытки не менее чем от пяти участников. Поскольку, кроме него, имеется лишь 9 участников, то хотя бы один другой участник входит в обе пятерки.
175.	В группе 30 человек. Каждому нравятся ровно k людей из этой группы. При каком наименьшем k обязательно найдутся два человека из этой группы, которые нравятся друг другу? Ответ   Решение Ответ. При k = 15. Решение. Доказательство того, что при k = 15 два человека, которые нравятся друг другу, обязательно найдутся, совпадает с решением предыдущей задачи (нужно лишь заменить 5 на 15, 10 на 30, и заставить всех членов группы послать открытки тем, кто им нравится). А при k < 15 два человека, нравящиеся друг другу, могут и не найдись. В самом деле, расположим 30 человек по кругу. Может оказаться, что каждому человеку нравятся k следующих за ним по часовой стрелке людей.
176.	На плоскости нарисовали 5 прямых. Докажите, что угол между какими-то двумя из них не больше 36°. (Если какие-нибудь прямые параллельны, считайте, что угол между ними равен 0°.) Указание   Решение Указание. Угол между прямыми не изменяется, если к ним применить параллельный перенос (для каждой прямой - свой перенос). Решение. Отметим на плоскости произвольную точку и переместим параллельными переносами все прямые так, чтобы они проходили через эту точку. Величины углов между прямыми при этом не изменятся. Теперь мы получили пять прямых, проходящих через одну точку, которые образовали 10 углов (внутренние области которых не пересекаются). Сумма величин этих углов равна 360°. Если бы все эти величины были больше 36°, то их сумма была бы больше 360°. Следовательно, величина хотя бы одного из этих десяти углов не превышает 36°.
177.	Какое наибольшее число клеток шахматной доски можно покрасить, чтобы никакие две покрашенные клетки не соприкасались (даже в одной точке)? Решение Решение. Ответ очевиден из рисунка, на котором никакие две закрашенные клетки не соприкасаются, а семнадцатую клетку с соблюдением условия не покрасишь: Но как доказать, что никаким другим способом нельзя расположить на доске десять несоприкасающихся клеток? Перебором? Вариантов гораздо больше, чем кажется на первый взгляд. И уж совсем невозможно решение методом перебора, если доску 8×8 заменить, например, на доску размером 2000×2000. Оказывается, можно разбить доску на квадратики размером 2×2: Больше одной окрашенной клетки в квадратике 2×2 быть не может, поэтому окрашенных клеток не больше, чем квадратиков.
178.	На шахматной доске нельзя разместить более 32 не бьющих друг друга коней. Докажите это. Указание   Решение Указание. Разбейте 64 клетки доски на 32 пары, так, чтобы клетки одной пары были связаны ходом коня. Решение. Рассмотрим следующее разбиение доски на 32 пары клеток: Поскольку клетки одной пары связаны ходом коня, то не более чем на одной из них может стоять конь. Таким образом, не бьющих друг друга коней не может быть более 32.
179.	Найдите значение дроби а)  В · А · Р · Е · Н · Ь · Е ; К · А · Р · Л · С · О · Н б)  Г · Р · У · З · И · Я , Т · Б · И · Л · И · С · И где разные буквы - это разные цифры. Ответ   Решение Ответ. Каждая из этих дробей либо равна нулю, либо не имеет смысла. Решение. Заметим, что в каждой из дробей записаны по 10 разных букв. Это значит, что все цифры задействованы, в том числе и 0. Если ноль стоит в числителе, то дробь равна нулю, а если в знаменателе - она не имеет смысла.
180.	Из любых а) пяти; б) восьми; в) девяти целых чисел можно выбрать два таких, разность квадратов которых делится на а) 7; б) 13; в) 16. Докажите это. Указание   Решение пункта а) Указание. Выясните, какие остатки может давать квадрат целого числа при делении а) на 7; б) на 13; в) на 16. а) Решение. При делении на 7 квадрат целого числа может дать только один из следующих остатков: 0, 1, 2 или 4. Докажем это. Пусть a - целое число. Если оно делится на 7, то и его квадрат делится на 7. Если a дает остаток 1 при делении на 7, то a представимо в виде a = 7n + 1, где n - целое. Поскольку (7n + 1)2 = 49n2 + 14n + 1, то a2 = 7(7n2 + 2n) + 1 тоже дает остаток 1. Таким же образом рассмотрим остальные случаи: если a = 7n + 2, то a2 = 49n2 + 28n + 4 = 7(7n2 + 4n) + 4; если a = 7n + 3, то a2 = 49n2 + 42n + 9 = 7(7n2 + 6n + 1) + 2; если a = 7n + 4, то a2 = 49n2 + 56n + 16 = 7(7n2 + 8n + 2) + 2; если a = 7n + 5, то a2 = 49n2 + 70n + 25 = 7(7n2 + 10n + 3) + 4; если a = 7n + 6, то a2 = 49n2 + 84n + 36 = 7(7n2 + 12n + 5) + 1. Итак, квадрат целого числа при делении на 7 может давать лишь один из четырех остатков. Значит, среди пяти квадратов целых чисел хотя бы два дают одинаковый остаток при делении на 7, а в таком случае их разность кратна 7.
181.	В какое наибольшее число цветов можно раскрасить клетки доски 8×8 так, чтобы у каждой клетки среди ее соседей (по стороне) были хотя бы две клетки, окрашенные в тот же цвет? Решение Решение. Разобьем доску на 16 квадратиков 2×2 и покрасим их в разные цвета. Докажем, что больше 16 цветов получить нельзя. Рассмотрим клетку любого цвета. Рядом с ней есть еще две клетки того же цвета. Эти две клетки имеют только одну соседнюю клетку того же цвета (среди рассмотренных), поэтому есть еще хотя бы одна клетка такого же цвета. Итак, каждого цвета не меньше четырех клеток, а следовательно, цветов не больше 16.