Позиционные кубики

Начните с малых n. Выясните, почему задача не имеет решения при n = 2 и n = 3. Попытайтесь найти расстановку кубиков для n = 4 и еще одну для n = 5.

Все натуральные числа можно разбить на четыре класса — в один класс попадают числа, дающие один и тот же остаток от деления на 4. Такими остатками могут быть 0, 1, 2 и 3, а числа из i-го класса записываются в виде 4k + i. Сразу скажем, что если n = 4k или n = 4k + 1, то кубики можно расставить требуемым образом, а если n = 4k + 2 или n = 4k + 3, то расставить кубики нельзя. Рассмотрим все четыре случая.

1) n = 4k.

В этом случае имеется 8k кубиков с номерами от 1 до 4k — по два кубика с каждым номером. Выстраивая кубики в ряд, начинать нужно с пары кубиков с наибольшим нечетным номером 4k − 1. Они должны стоять на позициях 2k + 1 и 6k. На рис. 2 показана расстановка для k =4. При таком k наибольшее нечетное число равно 15 и кубики с ним должны быть на позициях с номерами 9 и 24.

Рис. 2.

Далее вокруг числа 4k − 1, находящегося на позиции 2k + 1, расставим симметрично пары кубиков с четными номерами от 2 до 4k.

Оставшиеся нечетные кубики расставляются следующим образом. Начинаем с кубиков с номерами 2k − 1: один из них нужно поставить справа от кубика с наибольшим четным номером 4k, а второй — справа от кубика с наибольшим нечетным номером (стоящего на позиции с номером 6k). Разность между этими позициями равна (6k + 1) − (4k + 2) = 2k − 1, так что все в порядке. Уточним, что разность их позиций равна в точности равна . Теперь вокруг кубиков, находящихся на соседних позициях 6k и 6k + 1 расставим симметрично пары кубиков с нечетными номерами от 3 до 2k − 3. Далее, справа от уже расставленных кубиков с нечетными номерами, располагаем пару кубиков с номером 1. Остальные пары кубиков с нечетными номерами от 2k + 1 до 4k − 3 расставляем тоже симметрично, но уже вокруг блока из всех ранее расставленных кубиков с нечетными номерами. Получили требуемую расстановку кубиков.

2) n = 4k + 1.

Здесь все аналогично. На рис. 3 показана схема расстановки для k = 4.

Рис. 3.

3) n = 4k + 2 и n = 4k + 3.

Покажем, что в этих случаях расставить кубики требуемым образом нельзя. Заметим, если в ряд выстроено 2n кубиков, то сумма всех их позиций равна \(S_1=1+2+3+\ldots+2n=n(2n+1)\). Рассмотрим теперь два кубика с произвольным номером m. Если они стоят на позициях x и x + m, то сумма номеров их позиций равна 2x + m, а значит имеет такую же четность, что и само число m. Но тогда сумма всех позиций имеет ту же четность, что и число \(S_2=1+2+3+\ldots+n=\frac12n(n+1)\).

При n = 4k + 2 получим, что \(S_1=(4k+2)(2(4k+2)+1)=2(2k+1)(8k+5)\) — четное, а \(S_2=\frac12(4k+2)(4k+2+1)=(2k+1)(4k+3)\) — нечетное. При n = 4k + 3 получим, что \(S_1=(4k+3)(2(4k+3)+1)=(4k+3)(8k+7)\) — нечетное, а \(S_2=\frac12(4k+3)(4k+4)=2(4k+3)(k+1)\) — четное.

В обоих случаях числа \(S_1\) и \(S_2\) разной четности, поэтому расставить кубики в ряд так, чтобы выполнялись все условия задачи, невозможно.

Немного предыстории. Однажды я был участником семинара для учителей, занимающих организацией и проведением математических олимпиад школьников. Занятия проводились в Сочи в образовательном центре «Сириус», созданном на базе одного из олимпийских объектов для развития одаренных детей нашей страны.

Авторы олимпиадных задач, придумывая новые задачи, стараются придерживаться определенных критериев: олимпиадные задачи должны быть нестандартными, глубокими по идейному содержанию, красивыми по формулировке, иметь оригинальное решение. На семинаре красной нитью проходила идея о том, что если даже ученик не решит хорошую задачу непосредственно на олимпиаде, то к ней он обязательно вернется потом и постарается дорешать. В общем, хорошая задача сама побуждает себя решать. Для меня такой оказалась предложенная на том семинаре задача на расстановку 100 кубиков, являющаяся частным случаем рассматриваемой задачи при n = 50. Эксперименты с небольшими n выявили озвученную в решении картину: для чисел n вида 4k и 4k + 1 требуемая расстановка существует, а для n вида 4k + 2 и 4k + 3 расставить кубики так, как нужно, нельзя. Общую схему расстановки придумал А. Домашенко.

Еще одно интересное решение для n = 50 было предложено прямо во время семинара С. Нохриным. Неожиданным образом в нем сработала идея шахматной раскраски. Рассуждение следующее. Пусть требуемая расстановка кубиков существует, зафиксируем ее. Раскрасим кубики в шахматном порядке: самый левый кубик покрасим в черный цвет, соседний с ним — в белый, следующий — опять в черный и т. д. Кубики с номером 1 стоят рядом, поэтому у них разные цвета. Кубики с номером 2 стоят через одну позицию, поэтому они одного цвета. И вообще, если на кубиках написано одно и то же нечетное число, то кубики разноцветны, а если четное, то они одного цвета. Так как всего кубиков четное число, то среди них поровну черных и белых. Удалим все кубики с нечетными номерами — черных и белых кубиков останется поровну. При этом мы оставили ровно половину кубиков, значит, черных и белых осталось по 25. Но оставшиеся кубики разбиваются на одноцветные пары (кубики с одинаковыми номерами), поэтому кубиков каждого цвета должно быть четное количество. Противоречие.

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

Убедитесь, что приведенные рассуждения с раскраской кубиков обобщаются на случаи n = 4k + 2, и что эти же рассуждения с небольшим изменением подходят для доказательства невозможности расстановки кубиков при n = 4k + 3 (в чем заключается это изменение?).

При малых значениях n можно отыскать все решения задачи. Например, задача с десятью кубиками имеет десять различных решений (рис. 4).

Рис. 4.

Понятно, что здесь есть пары «взаимно обратных» расстановок (например, первая и десятая расстановки), поэтому фактически в этом случае задача имеет пять различных решений.

У рассматриваемой задачи есть близкий по смыслу вариант, в котором тоже нужно расставить пары пронумерованных кубиков, но так, чтобы расстояние между кубиками с одним номером, измеренное в кубиках между ними, было равно их номеру. Например, между кубиками с номером 1 должен быть только один другой кубик, между кубиками с номером 2 должно быть два кубика, и т. д. в такой постановке расстановка существует, если n = 4k или n = 4k + 3, и не существует, если n = 4k + 1 или n = 4k + 2. Попробуйте это доказать. На рис. 5 показана правильная расстановка для n = 11.

Рис. 5.

Т. Сильвер придумал «тройной» вариант этой задачи: имеется по три кубика с каждым номером, которые требуется расставить так, чтобы в каждой тройке с одним номером расстояния от крайних кубиков до центрального (измеренные в кубиках) были равны их номеру. С помощью компьютера Сильверу удалось найти два значения n, при которых эта задача имеет решение. При n = 9 подходит последовательность 181915267285296475384639743, а при n = 10 — последовательность 1(10)1214297248(10)5647935863(10)753968. Я тоже использовал компьютер и нашел для этих n еще по несколько других расстановок. Для других значений n вплоть до 12 поиск результатов не дал. Получится ли у вас продвинуться в решении этой задачи? Также интересно, возможны ли подобные расстановки для наборов, в которых кубик с каждым номером встречается четыре, пять или больше раз.