Призрак Леонардо

26

КВАНТ 2008/№1

Конкурс имени А.П.Савина

«Математика 6–8»

Мы завершаем очередной конкурс по решению математических задач для учащихся 6–8 классов. Решения задач высылайте в течение месяца после получения этого номера журнала по адресу: 119296 Москва, Ленинский проспект, 64-А, «Квант» (с пометкой «Конкурс «Математика 6–8»). Не забудьте указать имя, класс и домашний адрес. Как и прежде, мы приветствуем участие в конкурсе не только отдельных школьников, но и математических кружков. Руководителей кружков просим указать электронный адрес или контактный телефон. По традиции, кружки-победители заочного конкурса приглашаются на финальный очный турнир.

16. При каких натуральных n > 2 можно записать в одну строку числа от 1 до n так, чтобы среди любых трех чисел, записанных подряд, одно из них было не меньше суммы двух других? И.Акулич

19. Числовая последовательность $f_{0}, f_{1}, f_{2}$, … строится следующим образом:

20. Найдите все натуральные степени простых чисел, представимые в виде суммы двух кубов натуральных чисел. В.Сендеров

Докажите, что все числа этой последовательности – целые. В.Лецко

18. Точку D, лежащую внутри остроугольного треугольника АВС, отразили симметрично относительно трех его сторон АВ, ВС, СА. Оказалось, что соответствующие три новые точки $C_{1}, A_{1}, B_{1}$ лежат на окружности, описанной вокруг треугольника АВС. Затем на чертеже оставили точки $A_{1}, B_{1}, C_{1}$, а все остальное стерли. Восстановите треугольник АВС по этим трем точкам. С.Дворянинов

$f 0 =^{0}, f_{n} +_{1} =$

$3 f_{n} + 5 f_{n}^{2} + 4$

2

, n = 0, 1, 2, …

20. Натуральные числа х и у таковы, что ху + 1 является квадратом целого числа. Докажите, что найдется натуральное число z такое, что числа yz + 1, zx + 1, а также число xy + yz + zx + 1 являются квадратами целых чисел. В.Произволов

Призрак Леонардо

И.АКУЛИЧ

Пусть тот, кто не математик, не читает меня.

Леонардо да Винчи. Научная проза

ПОЛТЫСЯЧЕЛЕТИЯ ОТДЕЛЯЕТ НАС ОТ ВЕЛИКОГО ЛЕОНАР- до да Винчи, но человечество и по сей день неустанно ищет ответ на вопрос: кто же он был такой? Художник? Изобретатель? Философ? Гений, намного опередивший свое время, или вообще посланник инопланетного разума? Свидетельствами неувядающего интереса к этому титану эпохи Возрождения являются наделавшая много шума книга (а затем и фильм) «Код да Винчи», а также увлекательная компьютерная $игра^{1}$. Она прямо-

1 Cм., например, www.1980-games.com/us/reflexion-games/ reflexion-others/026.php или www.1980-games.com/us/reflexion- games/reflexion-others/debout.php таки насыщена задачами, головоломками и прочими затруднениями, что делает ее чрезвычайно трудной, но и весьма интересной. Одна из задач этой игры и явилась отправной точкой истории, которую мы сейчас изложим. Итак, дан клетчатый квадрат размером 5 ѣ 5 клеток, каждая клетка которого может быть либо белой, либо черной (первоначально все клетки белые, хотя это и несущественно). Разрешается выбрать любую клетку и одновременно перекрасить в противоположный цвет ее саму и все клетки, имеющие с ней общую сторону (мы их будем называть соседями). Требуется за несколько таких операций перекрасить все клетки квадрата в противоположный цвет. Трудно сказать, приложил ли руку к этой задаче сам Леонардо да Винчи, но вполне возможно, что да. Во

27

всяком случае, похоже на то. Уж очень… но об этом позже. Безусловно, многие пользователи компьютерной игры решали головоломку «методом тыка», щелкая мышью по различным клеткам по велению души. Но мы постараемся подойти к делу научно. Для начала назовем перекрашивание какой-либо клетки (и одновременно всех ее соседей по стороне) ходом в эту клетку. Пусть мы сделали какое-то количество ходов в какие-то клетки и добились своего, перекрасив все клетки квадрата в противоположный цвет. Рассмотрим любую клетку. При каждом ходе в нее саму или в любую соседнюю с ней клетку она меняет цвет. Следовательно, если в итоге клетка получила противоположный цвет, суммарное число ходов в эту клетку и все соседние с ней клетки должно быть нечетным. При этом очередность ходов, очевидно, не имеет никакого значения – от перестановки слагаемых сумма (а тем более четность) не меняется. Поразмыслив, можно сделать еще один, не менее важный вывод: если в какую-либо клетку было сделано не меньше двух ходов, то, уменьшив количество ходов в эту клетку на 2, мы придем к такому же результату. Закон четности проявляется и здесь. Но если так, то, уменьшая число ходов в каждую клетку на 2 до тех пор, пока это возможно, мы доведем количество ходов в каждую клетку до одного или вообще до ни одного. Другими словами, если возможно с помощью некоторого набора ходов в некоторые клетки достичь желаемого результата, то того же можно добиться, сделав в каждую клетку не более одного хода. Такой вывод позволяет нам разделить клетки на две категории: в которые был сделан ход (единственный!) и в которые не было сделано хода. Посему давайте отметим клетки, в которые надо сделать ход, и подумаем, каким условиям должна удовлетворять полученная конфигурация. Заметим, что с каждой отмеченной клеткой обязано соседствовать четное число отмеченных клеток (т.е. или ни одной, или две, или четыре), а с каждой неотмеченной клеткой – нечетное число отмеченных клеток (т.е. или одна, или три). Несомненно, большинство читателей согласятся с этим без колебаний, а для тех, кто сомневается, поясним подробнее. Рассмотрим любую неотмеченную клетку А. С ней соседствует нечетное число отмеченных клеток. Так как при ходе в любую такую соседнюю клетку клетка А поменяет цвет, то после всех ходов она поменяет цвет

М

Ш

Иллюстрация В.Иванюка

К

нечетное число раз, и в итоге ее цвет станет противоположным исходному. Теперь рассмотрим любую отмеченную клетку В. С ней соседствует четное число отмеченных клеток. Так как при ходе в любую такую соседнюю клетку клетка В поменяет цвет, то после всех ходов в соседние отмеченные клетки она поменяет цвет четное число раз. Плюс к тому же она один раз поменяет цвет при ходе в саму клетку В. Таким образом, в итоге ее цвет станет противоположным исходному. Что ж, нам удалось преобразовать «динамическую» задачу (где клетки то и дело меняют цвет) в «статический» вариант, где нужно всего лишь отметить некоторые клетки доски определенным образом: чтобы с каждой отмеченной клеткой соседствовало четное число отмеченных клеток, а с каждой неотмеченной – нечетное число отмеченных клеток. Приступим. Для квадрата 5 ѣ 5 решение имеется (рис.1, отмеченные клетки окрашены в красный цвет). С помощью поворотов и отражений можно получить еще три решения, но самое интересное, что других решений нет! Уже это позволяет предположить, что великий Леонардо мог быть причастен к такой задаче – ведь интуитивно кажется, что решение должно быть «более симметричным», ну хотя бы относительно вертикальной и горизонтальной осей. Разумеется, мы не станем ограничиваться квадратом 5 ѣ 5, а «потрогаем» квадраты n ѣ n и для других n.

28

КВАНТ 2008/№1

Рис. 1

При небольших n это можно сделать без особого труда. Проще всего получить ответ для n = 1 – это просто единственная отмеченная клетка. При n = 2 имеем четыре закрашенные клетки, и решение тоже единственное. Значение n = 3 дает красивую конфигурацию, опять-таки единственную (рис.2).

Рис. 2

Неожиданную россыпь различных конфигураций порождает n = 4. Существует пять принципиально различных способов отметить клетки (рис.3).

Рис. 3

Первые два из них с помощью поворотов и отражений «раздваиваются», а остальные три «расчетверяются». Итого, получается 16 способов. Весьма «выпадающий» результат на фоне остальных уже рассмотренных n. Далее решения вплоть до n = 8 еще удалось подобрать вручную (отметим, кстати, что задача для квадрата 8 ѣ 8, т.е. собственно шахматной доски, была предложена в конкурсе «Математика 6–8» текущего учебного года (задача 5) – так что заодно мы решили и ее). При этом были обнаружены весьма симпатичные, обладающие высокой степенью симметрии конфигурации (рис.4). Уже на этом этапе, несмотря на достигнутые успехи, появились смутные мрачные предчувствия. Во-первых, не удалось нащупать никаких «общих» способов отметить клетки требуемым способом. Неудачной оказались и попытки использовать найденные результаты для меньших n при поиске решений для бóльших n. Правда, конфигурация для n = 8, как легко заметить, получается как бы дополнением «каймы» к конфигу-

Рис. 4

рации для n = 6, но этот успех слишком скромен (и выявлен он был, честно сказать, задним числом). Что делать? Пришлось поставить на службу достижения современной вычислительной техники и поручить компьютеру поискать, для каких еще n можно отметить клетки (а заодно подсчитать количество способов это сделать для каждого n). Бодро стартовав, компьютер добрался только до n = 28, поскольку с дальнейшим ростом n он начинает думать безбожно долго. Тем не менее, анализ результатов оказался настолько поразительным, что предположение о причастности да Винчи к рассматриваемой задаче только укрепилось. Посудите сами. Во-первых, компьютер подтвердил единственность решения для n = 6, 7 и 8. Более того, выяснилось, что решение существует для всех рассмотренных n, причем для n = 10, 12, 13, 15, 18, 20, 21, 22, 25, 26, 27 и 28 оно единственно. Следовательно, оно обладает симметрией относительно всех осей симметрии самой доски (иначе появились бы дополнительные решения, полученные поворотами и отражениями). Далее, для n = 17 (как и для известного нам n = 5) имеется 4 решения, для n = 14 и 24 имеется 16 решений, для n = 11 число решений достигает 64, для n = 9 и 16 оно равно 256. А дальше – прямо-таки потрясающий взлет: при n = 23 число решений резко «прыгает» до 16384, а для n = 19 – до 65536. Отметим, что каждое из фигурирующих здесь чисел (1, 4, 16, 64, 256, 16384 и 65536) является целой неотрицательной степенью четверки. При этом на свет уже появляются и конфигурации, не обладающие ни осевой, ни поворотной симметрией (хотя отдельные их фрагменты могут быть симметричны). Например, вот как выглядит один их возможных результатов для доски 19 ѣ 19 (рис.5). Фантасмагория какая-то! Такого рода результаты просто ошарашивают, и начинает казаться, что где-то рядом неслышной тенью проходит восставший из глубины веков призрак Леонардо. Неужели он предчувствовал нечто подобное (отсутствие компьютера гению, как известно, не помеха)? Так или иначе, но то,

Рис. 5