§ 12. Принцип Дирихле

Тема этого параграфа напрямую, казалось бы, не связана с арифметикой. Тем не менее, простые но не тривиальные соображения Дирихле используются во многих теоретико-числовых рассуждениях.

Принцип Дирихле: Если есть m куч, в которых содержится N объектов, то найдётся куча с числом объектов не менее N / m и куча с числом объектов не более N / m .

Доказательство. От противного. Если во всех кучах меньше N / m объектов, то всего объектов меньше m(N / m) = N – противоречие.

Если во всех кучах больше N / m объектов, то всего объектов больше m(N / m) = N – противоречие.

Принцип Дирихле доказан.

Как ни странно, этот простой принцип имеет глубокие применения. Прежде чем к ним переходить, решим несколько простых задач.

Задача 1. В студенческой группе 25 студентов. Доказать, что по крайней мере у трёх студентов дни рождения в одном месяце.

Будем раскладывать студентов по двенадцати кучам в соответствии с месяцами их дней рождения. По принципу Дирихле в одной из этих куч будет не менее 25 / 12 = 2,008… студентов. Поскольку дробных студентов не бывает, то в этой куче не менее трёх студентов.

Задача 2. В классе 28 человек. В диктанте хулиган Вовочка сделал 13 ошибок, а остальные – меньше. Докажите, что по крайней мере 3 ученика сделали равное число ошибок.

Учеников будем раскладывать по кучам в соответствии с количеством сделанных ими ошибок. Таких куч 14 (ошибок может быть от 0 до 13), причём в последней только один человек – хулиган Вовочка. Значит, в остальных тринадцати – 27 человек. По принципу Дирихле, в какой-то куче будет не менее 27 / 13 = 2,007… учеников, т.е. не менее трёх.

Задача 3. В доме 123 жильца, которым в сумме 3813 лет. Можно ли выбрать 100 из них, которым вместе не меньше 3100 лет ?

Достаточно понять, будет ли вместе не меньше 3100 лет ста самым старшим ? Предположим, что ста самым старшим в сумме менее 3100 лет. Тогда оставшимся двадцати трём в сумме не менее 3813 – 3100 = 713 лет. Если эти года раскладывать эти годы (объекты) по двадцати трём кучам (жильцам), то одна из куч по принципу Дирихле будет содержать не менее 713 / 23 = 31 объектов. Это значит, что возраст одного из оставшихся двадцати трёх человек не менее 31 года. Значит, самым старшим ста жильцам не менее 31 года каждому и их суммарный возраст не менее 3100 лет – противоречие.

Задача 4. Докажите, что в любой компании из п  2 человек найдутся двое, имеющие одинаковое число знакомых (считаем, что каждый знаком, по крайней мере, сам с собой и если a знаком с b, то b знаком с a).

Количество знакомых у каждого может быть от 1 до n. Если раскладывать людей по кучам в соответствии с числом их знакомых, то в n куч разложатся n человек. Если предположить, что в каждой куче по одному человеку, то будет знакомый со всеми n, а значит, не будет человек, знакомого с только с одним человеком – противоречие.

Задача 5. В строку выписано п целых чисел. Докажите, что сумма нескольких рядом стоящих из них делится на п.

Пусть числа a₁ , … , a_n . Рассмотрим последовательные суммы b₁ = a₁ , b₂ = a₁ + a₂ , … , b_i = a₁ + … + a_i , … , b_n = a₁ + … + a_n . Нужно доказать, что одно из b_i делится на n, т.е. даёт остаток 0 при делении на n. Предположим, что остаток 0 не даёт ни одно из них. Тогда их n, а ненулевых остатков – (n – 1). Ясно, что по принципу Дирихле среди них два b_i и b_j при i > j дают один и тот же остаток. Значит, b_i – b_j = a_i + a_i–1 + … + a_j+1  n, что и требовалось.

Задача 6. Двоечник Вовочка выучил только одну цифру – единицу. Сможет ли он с её помощью записать число, делящееся на c = 102017+ 1 ?

Рассмотрим бесконечную последовательность чисел 1, 11, … , , … , записываемых одними единицами. Если раскладывать их по кучам – остаткам от деления на c , то в какой-то куче будет два числа . и при n > m. Значит,  c. Поскольку НОД(с, 10) = 1, то  с, так что Вовочка сможет записать нужное число одними единицами.

Задача 7. Докажите, что существует степень числа 13, оканчивающаяся на 00000001.

Рассмотрим степени 13¹ , 13² , … , 13ⁱ , … Нужно доказать, что среди них есть число 13^k  1 (mod 10⁸). По принципу Дирихле среди них есть два, имеющих одинаковые остатки при делении на 10⁸ : 13ⁱ  13^j (mod 10⁸) при i > j, т.е. 13^j(13^i–j – 1)  10⁸. Значит, можно взять k = i – j (?!).

Задача 8. В единичный квадрат бросили 50 точек. Доказать, что найдутся две из них, отстоящие друг от друга на расстояние не более 0,3.

Разобьём квадрат на равные 49 квадратиков, проведя прямые, параллельные сторонам квадрата. Тогда какие-то две точки попали в один квадрат, т.е. расстояние между ними не более длины диагонали квадратика, которая равна .

Задача 9. На складе имеется по 200 сапог 41-го, 42-го и 43-го размеров, причём среди всех 600 сапог есть 300 левых и 300 правых. Докажите, что можно обуть не менее 100 человек.

Если обуто менее ста человек, то на это пошло менее двухсот сапог, а значит, осталось более 400 сапог. Среди них поровну левых и правых, но нет левых и правых одного размера, иначе можно было бы ещё кого-нибудь обуть. Из этих оставшихся более чем 400 сапог будет левых и правых поровну и более чем по 200. Ни левые, ни правые не могут быть одного размера (общее количество сапог одного размера равно 200). Значит, среди левых есть сапоги, по крайней мере, двух размеров. Точно так же и среди правых есть сапоги, по крайней мере, двух размеров. Но тогда есть левые и правые одного размера – противоречие.

Задача 10. Даны пять точек на плоскости с целыми координатами. Доказать, что середина одного из отрезков, соединяющего две из них, тоже имеет целые координаты.

Докажем, что среди этих точек есть две, обе координаты которых одной чётности: если это точки M(a; b) и N(c; d), то середина отрезка MN имеет координаты  Z .

Рассмотрим координаты точек по модулю 2. Тогда они могут иметь один из четырёх видов (0; 0), (0; 1), (1; 0), (1; 1). Если точек пять, то у двух из них M(a; b) и N(c; d) получатся одинаковые координаты по модулю 2. Эти точки искомые.

Теперь докажем более серьёзное утверждение:

Лемма (о приближении действительных чисел рациональными). Для любого действительного числа r > 0 и произвольного n  N найдутся натуральные числа a, b  N, где 1  b  n со свойством |br – a|  .

Доказательство. Разобьём отрезок [0; 1] на n равных частей точками и рассмотрим последовательность чисел{0r}, {1r}, {2r}, … , {nr}, 1, где {x} = x – [x] – дробная часть числа x. Все члены последовательности принадлежат отрезку [0; 1], и каждый из них попадает в какой-то интервальчик (0 k  n). Поскольку таких интервалов только n+1, а рассматриваемых чисел n+2, то два из них попадут в один и тот же интервальчик. Либо {ir}, {jr}  при 0  i < j n, т.е. |{i} – {jr}|  и значит,

|(ir – [ir]) – (jr – [jr])| = |(i – j)r – ([jr] – [ir])| = |br – a|  ,

где 0  b = i – j  n, a = [jr] – [ir]  Z . Либо {ir}, 1  , т.е. будет |{ir} – 1|  и значит, |ir – [ir] – 1| = |br – a|  , где 0  b = i  n,

a = [ir] – 1  Z . В любом случае |br – a|  при 0  b  n, a  Z.

Лемма доказана.

Аналогично можно доказать следующее любопытное утверждение:

По окружности длины 1 из любой точки Н начинает в одну сторону прыгать кузнечик на расстояние. Тогда через несколько прыжков он обязательно попадёт в канавку К произвольной ширины  .

Более общо:

Лемма (о кузнечике). Для любого иррационального числа  , действительного s и положительного  найдутся такие целые числа a, b, что

|b – s – a| < .

Доказательство. Пусть кузнечик прыгает против часовой стрелки от точки Н на окружности длины 1 канавкой ширины  на расстоянии s от Н, преодолевая за один скок расстояние .

Во-первых, некоторые следы кузнечика окажутся на расстоянии меньше . Действительно, разобьём окружность на равные части длины 1 / N <  . Тогда по принципу Дирихле через более N прыжков некоторые два следа с номерами k, k + p попадут в одну из замкнутых частей, т.е. выполняется неравенство |(k + p) – k – a| <   |p – a| <  для некоторого целого a. При этом ввиду иррациональности  разность p – a не равна нулю.

Во-вторых, на расстоянии меньше будут и следы с номерами k + p и k + 2p, k + 2p и k + 3p, … , k + ip, k + (i+1)p (i  N):

|(k + (i+1)p) – (k + ip) – a| <   |p – a| <  .

Таким образом, следы с номерами k, k+p, k+2p, … следуют по окружности через одно и то же расстояние 0 <  <  . Значит эти следы (в какую бы сторону по окружности они ни шли), обязательно дойдут до канавки, а перепрыгнуть через неё не смогут.

Лемма доказана.

Доказанные леммы имеют весьма неочевидные применения:

Задача: Доказать, что степени двойки могут начинаться на любую комбинацию цифр.

Пусть N – число, десятичная запись которого представляет заданную комбинацию цифр. Нужно найти такие натуральные числа n, r, что

N10^r < 2ⁿ < (N + 1)10^r.

Это равносильно неравенствам r + lg N < nlg 2 < r + lg(N + 1). Отнимая от всех чисел середину рассматриваемого отрезка(r + lg N ; r + lg(N + 1)), получим

|nlg 2 – r – | < .

Это выполняется по лемме о кузнечике при иррациональном  = lg 2 , вещественном s = и положительном = .