Принцип дирихле План: Введение Различные формулировки принципа Дирихле

Решение: 400 > 366.
Задача 3. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?
Решение: Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.
II. 2. Принцип Дирихле в теории чисел
Возможна следующая переформулировка принципа Дирихле:
"Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".
При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, . . . , p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p. Рассмотрим классические примеры.
Задача 1. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.
Решение: По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r. Тогда их разность делится на 10: A - B = 10(a - b).

Задача 2. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это. Решение: Все числа можно разбить на два класса: чётные и нечётные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трёх целых чисел найдутся два числа одинаковой чётности. Их сумма чётна.