Заячье занятие

Игорь Акулич
«Квантик» №12, 2018

— Сегодняшнее занятие нашего математического кружка условно назовём заячьим.

— Почему?

— Потом скажу. Надо же интригу сохранить. А начнём вот с такой задачи, предложенной девятиклассникам на заключительном этапе XXVIII Всероссийской олимпиады в 2002 году (автор — Д. Ю. Кузнецов):

Не буду от вас с ходу требовать найти решение — вы ещё не девятиклассники, да и не участники Всероссийской олимпиады. Поэтому авторское решение изложу вам сам.

Но сначала давайте поговорим о расстояниях между центрами клеток, занятых ладьями. Никакие две ладьи, по условию, не бьют друг друга и, значит, не лежат на одной горизонтали либо вертикали. Поэтому если взять любые две ладьи, то каждая из них сдвинута относительно другой на m по горизонтали и на n по вертикали, где m и n — натуральные числа... кстати, какие значения они могут принимать?

— От 1 до 7!

— Верно. Если горизонтали (вертикали), в которых стоят ладьи, — соседние, то сдвиг равен 1, а больше 7 он быть не может — размеры доски не позволяют. И если считать, что доска разбита на поля со стороной 1, то расстояние между ладьями — это длина диагонали прямоугольника со сторонами m и n. И сколько это будет?

— Будет $\sqrt{m^2+n^2}$.

— Поясни.

— Диагональ прямоугольника есть гипотенуза прямоугольного треугольника с катетами, равными сторонам этого прямоугольника. Теорема Пифагора...

— Молодец! Ну, а теперь слушайте. Рассмотрим семь пар ладей, стоящих в соседних столбцах (в 1-м и 2-м, во 2-м и 3-м и т.д.). По горизонтали ладьи каждой такой пары сдвинуты на 1, а по вертикали сдвиги могут быть разными. Но если два каких-то сдвига по вертикали тоже одинаковы, то и расстояния между ладьями в таких парах одинаковы, потому что эти расстояния — диагонали одинаковых прямоугольников.

Значит, если имеются два одинаковых сдвига по вертикали — то всё в порядке, два одинаковых расстояния непременно найдутся. Ну а вдруг все эти сдвиги различны? Может такое быть, как вы думаете?

— А почему бы и нет? Ведь эти сдвиги могут иметь 7 значений — от 1 до 7, и здесь как раз 7 пар ладей в соседних вертикалях — столько же!

— Отлично! Автор задачи рассуждал так же: если все сдвиги различны, то среди них встречается по разу каждое из чисел от 1 до 7. В частности, есть две ладьи, отстоящие друг от друга на 2 по вертикали и на 1 по горизонтали (назовём эти две ладьи парой А), и расстояние между ними равно $\sqrt{1^2+2^2}=\sqrt{5}$. Запомним пока этот результат и рассмотрим теперь 7 пар ладей, стоящих в соседних строках (в 1-й и 2-й, во 2-й и 3-й и т.д.). Рассуждения здесь аналогичны, и потому либо найдутся две пары в соседних строках с равным сдвигом по горизонтали, либо есть две ладьи, отстоящие друг от друга на 1 по вертикали и на 2 по горизонтали (пара В). Тогда расстояния в парах А и В совпадают — оба равны $\sqrt{5}$, но сами эти пары, очевидно, различны. Ну, как решение?

— Сложное! Не зря задача на олимпиаду попала...

— Верно! Но задача решается и не так хитро, если сразу воспользоваться великим и вместе с тем простым принципом Дирихле! Только не пугайтесь грозного названия. Иоганн Петер Густав Лежен Дирихле — немецкий математик XIX века. Он и сформулировал свой принцип, который чаще всего почему-то излагают в виде истории про зайцев (или кроликов), сидящих в клетках. Звучит он так: если в клетках сидят зайцы, причём зайцев больше, чем клеток, то найдётся хотя бы одна клетка, в которой сидит не меньше двух зайцев. Как вам такое утверждение?

— Так это же очевидно!

— Ну, скажем так, почти очевидно. Но доказывается совсем просто, например, методом «от противного». Предположим, что в каждой клетке сидит не более одного зайца. Тогда зайцев будет не больше, чем клеток, что противоречит условию! Значит, наше предположение было неверным, и на самом деле в какой-то клетке сидят не менее двух зайцев. Вот вам принцип Дирихле в самой что ни на есть простой и наглядной форме.

Да, но к чему всё это? А к тому, что при решении многих задач нередко удаётся успешно применить принцип Дирихле, правильно подобрав «клетки» и «зайцев». Да и в авторском решении нашей олимпиадной задачи принцип Дирихле незаметно используется (потом найдите, где). Но давайте применим его в самом начале. Итак, требуется доказать, что среди попарных расстояний между ладьями имеются два одинаковых. Предположим, что пары ладей (и соответствующие расстояния между этими ладьями) — это зайцы. Сколько всего у нас зайцев? Кто подсчитает?

— Давайте я. Всего ладей 8, поэтому первую ладью пары можно выбрать восемью способами. Второй же ладьёй может быть одна из семи оставшихся ладей. Поэтому всего имеем 8 × 7 = 56 пар.

— Неправильно! Кто поправит?

— Я! Надо ещё поделить на 2. Ведь если мы выбрали ладью Л₁, а потом в пару к ней ладью Л₂, то это будет та же самая пара, как если бы мы сначала выбрали ладью Л₂, а потом Л₁. Поэтому ответ таков: 56/2 = 28.

— Теперь верно! Итак, имеем 28 зайцев — пар ладей, каждой паре соответствует некоторое число — расстояние между этими ладьями. Ну, а клетки — это набор вообще всех различных значений, которые могут принимать расстояния между ладьями. Если окажется, что клеток меньше, чем зайцев, задача решена — среди расстояний найдутся два одинаковых, ибо два зайца-расстояния попадут в одну и ту же клетку-значение.

Осталось определить, сколько различных значений могут принимать всевозможные расстояния между ладьями. Мы уже знаем, что в общем виде такие расстояния записываются как $\sqrt{m^2+n^2}$, где m и n — целые от 1 до 7. Ну, поскольку от перестановки слагаемых сумма не меняется, можно смело ограничиться пределами 1 ≤ m ≤ n ≤ 7. Сколько разных пар (m, n) здесь получается? Если меньше 28 — то превосходно!

— Можно, я посчитаю? Для m = 1 число n может принимать 7 значений, от 1 до 7. Для m = 2 — уже только 6 значений, от 2 до 7. И так далее. Значит, всего получается, что различных пар (m, n) образуется 7 + 6 + 5 + ... + 1 = 28. Столько же, сколько и зайцев! Значит, принцип Дирихле здесь неприменим?

— Нет уж, всё-таки применим! Мы, образно говоря, за деревьями леса не увидели. Что с того, что у нас получилось 28 пар (m, n)? А вдруг, на наше счастье, какие-то две из этих пар дадут одно и то же значение $\sqrt{m^2+n^2}$? Тогда возможных значений (то есть клеток) окажется меньше, чем пар ладей (то есть зайцев). Поищите-ка такие совпадения...

— Я нашёл! Если m = 1 и n = 7, то $\sqrt{1^2+7^2}=\sqrt{50}$. Если же m = n = 5, то $\sqrt{5^2+5^2}=\sqrt{50}$ — то же самое!

— Конгениально! Итак, из 8 ладей можно составить 28 пар, а возможных значений, которые могут принимать расстояния между ладьями в парах — уж точно меньше 28. Значит, для каких-то двух пар расстояния между ладьями совпадут, что и требовалось. Все довольны? Вижу, да. Кроме вон того молодого человека, который, как я заметил, почему-то не принимал активного участия в нашей беседе. В чём дело?

— Да я тут, пока вы обсуждали, стал рисовать всякие разные расположения не бьющих друг друга ладей на доске — наугад, какие получатся. Несколько десятков нарисовал — вот, посмотрите! И обнаружил, что обязательно имеются три одинаковых расстояния между ладьями. Три, а не два!

— Три — это очень существенно! Принцип Дирихле здесь, пожалуй, мы не пристроим никак. В общем, подумать надо. Но, естественно, не сейчас. Давайте так: каждый из вас (да и я тоже) продумаем гипотезу нашего коллеги и попытаемся выяснить, верна ли она. Если да — попробуем доказать, если нет — опровергнуть. Задание понятно? Всего хорошего!

...Вот так драматично и загадочно закончилось заячье занятие математического кружка. Попробуйте самостоятельно разобраться с гипотезой о трёх одинаковых попарных расстояниях между ладьями. Если не получится — воспользуйтесь помощью компьютера или посмотрите ответ в конце журнала.

Художник Алексей Вайнер

Ответ

Гипотеза всё же неверна — есть такое расположение не бьющих друг друга восьми ладей, что среди попарных расстояний между ними нет трёх одинаковых (см. рисунок).

Но чисто по-человечески автор гипотезы почти прав. Ведь среди 40320 возможных расположений на доске восьми не бьющих друг друга ладей лишь у 36 нет трёх равных попарных расстояний (проверено на компьютере). Это менее 0,1% от общего количества. Найти такое расположение наугад, «методом тыка», почти нереально.