Шесть зайцев в пяти клетках

17

Математический кругжок

В. Болтянский

ШестЬ зайцев в пяти клетках

«Ну зайцы, погодите!»
Волк

Согласитесь, что если в каждой клетку разрешается посадить не более одного зайца, то разместить шесть зайцев в пяти клетках не удостся, и вообше, ни для какого натурального n не удостся разместить n + 1 зайцев в n клетках. Можно сказать и иначе: если в n клетках находится n + 1 или больше зайцев, то найдемся клетка, в котором сидит не менее двух зайцев.

Обозначим зайцев символами p₁, …, pₙ+1, а клетки — q₁, …, qₙ. тогда каждой способ разадить зайцев в клетки можно рассматривать как некоторое отображение (рис. 1) множество P = {p₁, …, pₙ+1} в множество Q = {q₁, …, qₙ}: зайцу pᵢ ∈ P ставится в соответствие (в качестве его «образа») та клетка qᵢ ∈ Q, в которой этот заяц сидит. Таким образом, сформированное выше утверждение о заяцах в клетках имеет следующий математический смысл: при любом отображении множества P, содержащого n + 1 элементов, в множество Q, содержащое n элементов, найдется два элемента множества P, имеющие один и тот же образ.

Это утверждение называется принципиом Дирихле*). Его справедливо нетрудно доказать с помощью метода математической индукции. По неписанной традиции, математики всего мира, рассматривая о принципие Дирихле, разъясняют его смысл не на языке множества и отображений и не с какими-либо других предметами, а именно с зайцами и клетками.

Приципи Дирихле, несмотря на его простоту и оченьность, очень часто используется при доказательстве теорем и решении задач.

Пример 1. Доказать, что если пряма l, расположенная в плоскости треугольника ABC, не проходит ни

*) Петер Густав Лежен Дирихле (1805—1859) — выданнойся немецкий математик; ему принадлежат основополагающие работы в теории чисел и других области математики.

Рис. 1.

20

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

Пример 6. Пусть $p$ и $q$ — натуральные числа, и рациональное число $\frac{p}{q}$ записьвается в виде бесконечной десятичной дроби. Доказим, что модела эта дробь обязательно будет периодическая.

Доказательство этого факта (в школе оно не рассматривается) нетрудно получить с помощью причины Дирихле. При выполнении деления $p: q$ «столбиком» все время будет получаться от нуля остатки (инначе число $\frac{p}{q}$ не записьвалось бы в виде бесконечной десятичной дроби). Таким образом, каждый раз при нахождения очередной цифры частного будет получаться в остатке одно из чисел 1, 2, …, $q-1$). Эти возможные значения остатков мы и будем считать «клетками», так что всего имеет $q-1$ «клеток». «Зайцами» же будем считать остатки, которые в действительности получаются после того, как мы снесли последнюю значшую цифру делимого (рис. 4). Расмотрим первых $q$ «зайцев» (на 1 большие, чем число «клеток»). Каждый «зайц» попадает в какую-либо «клетку» — каждый остаток равен одному из чисел 1, 2, …, $q-1$. В силу причины Дирихле найдется два «зайца», попавшие в одну «клетку». Иначе говоря, среди чисел 1, 2, …, $q$ можно выбрать такие два числа $i, j$, что $i$-й и $j$-й остатки (после того, как мы снесли последнюю значшую цифру