А теперь сама задача.
На шахматной доске, бесконечно простирающейся вправо и вверх (то есть, заполняющей собой первый квадрант), в левом нижнем углу стоят три шашки в позиции, показанной на рисунке.
На каждом ходу выбирается одна из шашек, убирается с доски, а в соседнюю клетку справа и в соседнюю клетку сверху ставится по новой шашке. Ход возможен только в том случае если обе соседние клетки (и справа, и сверху) свободны.
Одна из возможных последовательностей первых четырех ходов изображена на рисунке ниже (шашка, которую мы убираем на текущем ходу показана окружностью):
Необходимо указать последовательность ходов, в результате которой все три стартовые клетки (на рисунках выше они обведены жирной линией) окажутся пустыми. Или показать, что это невозможно.
Решение на следующей неделе. Комментарии до публикации решения скрыты.
PS. Я умышленно не указываю пока источник картинок. Тем не менее, они достаточно легко гуглятся. Однако, на том конце решения нет. Есть только существенная подсказка (на английском языке, ага). Ежели станет невмоготу, можете воспользоваться.
PPS. Знаний свыше обычной школьной программы 9 класса по алгебре для решения не потребуется.
UPD. Уважаемый
kercenter весьма оперативно сделал интерактивную версию игры. Поле ограничено, 20х20, но для того, чтобы вникнуть в суть происходящего — более чем достаточно.
M 0[9R`0F-u%/?˰ <8lSa'Kl&hY(n կ #QGN [H D2xd
ПРИМЕЧАНИЕ К ОТВЕТУ: в качестве ответа формулировкой задачи ен предусмотрен алгоритм (тем более алгоритм, никогда не останавливающийся).
ПИРМЕЧАНИЕ К ОТВЕТУ №2: вообще-то ответ "не очень честный", т.к. он ищет "дыру" по форме постановки задачи, а не по сути (как-нибудь забить всё внешнее поле чёрными клеточками).
По-"честному" надо было бы показать, что любое построение будет "в принципе не плотным" (а нам надо забить все точки на "белой" стороне квадранта).
// ОБЩАЯ ИДЕЯ РЕШЕНИЯ:
- подметим, что можно задать вес ячейки так, что при преобразовании (1 чёрной клетки в 2 чёрные) этот вес сохранится.
- подсчитаем, что вес чёрных точек квадранта равен весу всего остального (бесконечного!) квадранта.
- вывод: нам надо забить, причём полностью весь квадрант (кроме 3 точек).
- дадим формальный ответ, что привести последовательность невозможно, т.к. она бесконечная.
- если формулировка будет изменена и потребуется привести алгоритм -- займёмся этим на выходных.
// НЕКОТОРЫЕ ОПРЕДЕЛЕНИЯ
0. Договоримся, что самая первая ячейка имеет координаты (1,1).
это будет важно, когда будет определяться её "вес" и норма.
1. Введём норму N(x,y) = x+y.
2. Введём "вес ячейки" T = (1\2)^N.
3. Очевидно, что при преобразовании фишки получается 2 фишки, причём:
A0(x0,y0) -> A1 (x0+1, y0) U A2(x0, y0+2).
N(A1) = N(A2) = N(A0 + 1) **********************(3)
ПРИ ПРЕОБРАЗОВАНИИ ОБЕ НОВЫЕ ЯЧЕЙКИ ИМЕЮТ НОРМУ на 1 большую, чем у старой.
4. Вычислим "вес" ячейки до и после преобразования:
T(A1) + T(A2) = T(x0+1, y0) + T(x0, y0 +1) = (1/2)^(x0+1+y0) + (1/2)^(x0+y0+1) = 2 * (1/2)^(x0+y0+1) = T(A0) **********(4)
ПРИ ПРЕОБРАЗОВАНИИ ВЕС "ЗАКРАШЕННЫХ" ЯЧЕЕК СОХРАНЯЕТСЯ.
5. Введём понятие "Вес четверти круга" (как вес всех ячеек, входящих в четверть круга, с нормой ячейчк <= R).
S(R) = СУММА(T(A)), для всех A, N(A)<=R
S(R) = 1*(1/4) + 2*(1/8) + 3*(1/16) + .... ***************(5)
// НЕКОТОРЫЕ "ОЧЕВИДНЫЕ" ВЕЩИ:
а) изначальный вес закрашенных точек = S(2) = T(1, 1) + T(1, 2) + T(2, 1) = 1/4 + 1/8 + 1/8 = 0.5
б) при преобразовании вес закрашенных ячеек не меняется.
в) Фактически нам надо найти (даже не построить) четверть-круга, которая будет разбита на 2 части:
- незакрашенную часть площадью (минимум!!!) S(3) = 1/2
- закрашенную часть, площадью = 1/2, что следует из (б).
г) S(бесконечности) = 1.
решим так:
i. 1*1/4 + 2*1/8 +3*1/16 + 4*1/32 = СУММА:
1/4 + 1/8 + 1/16 + 1/32 + .... = 1/2
1/8 + 1/16 + 1/32 + .......... = 1/4
1/16 + 1/32 + ................ = 1/8
...............
ii. Эта сумма = 1.
// РЕШЕНИЕ:
возможны две ситуации:
- построение невозможно вообще (рано или поздно мы "наткнёмся" на невозможность переместить ячейку).
- построение возможно, но требует бесконечного числа преобразований -- в этом случае предъявить ответ В ВИДЕ ПОСЛЕДОВАТЕЛЬНОСТИ ПРЕОБРАЗОВАНИЙ НЕЛЬЗЯ.
Edited at 2014-10-10 05:23 pm (UTC)
ЗАКРАШЕНО БЫТЬ НЕ МОЖЕТ:
2. При каждом преобразовании всегда будут закрашены только 2 ячейки в самом левом столбце \ только 2 ячейки в самой нижней строке.
3. Необходимое условие освобождения 3х первых ячеек (закраска всех остальных ячеек) не может быть выполнена.
ОТВЕТ:
закрашивание невозможно.
Edited at 2014-10-10 05:46 pm (UTC)
Обозначим первую координату фишки через x, вторую - через y
Несложно заметить, что ход любой фишки можно будет вычислить по формуле:
x,y -> x'=x+1,y'=y ; x''=x,y''=y+1
где слева находится убранная фишка, а справа - добавленные.
далее, для любых двух фишек, находящихся на диагонале (как фишки 2A и 1B на четвёртой картинке) будет действовать правило, запрещающее убирать их одну сразу после другой, поскольку их ходы будут мешать друг другу.
в самом деле, если x1 = x2+1 и y2 = y1+1 (а именно эти условия удовлетворяют диагональным фишкам), то x1''=x2' и y1''=y2', то есть одна из позиций для новых фишек будет одинакова для этих двух фишек. и, что бы убрать обе фишки, нужно будет, с начала, отчистить эту позицию.
Однако, каждый ход порождает две новые диагональные фишки, поскольку x'=x''+1 и y''=y'+1, то есть, выполняется условие для диагональных фишек.
Любые две диагональные фишки можно убрать за три последовательных хода, как показано в первых трёх картинках. Однако, для этого перед ними должно быть свободно пять клеток, которые окажутся занятыми.
Эту последовательность можно продолжить, к примеру, три диагональные фишки можно убрать за 6 ходов, но, перед ними должны быть свободны 9 клеток, и, после 6 ходов мы получим один набор из 2-х диагональных фишек, один набор из трёх и один из четырёх.
Несложно посчитать, решение существует только для первого набора (любой длинны), поскольку после него для следующего набора не будет достаточно места, таким образом два набора из диагональных фишек (как на третей картинке) уже не имеют решения.
Или, можно сказать, что решение есть, но для него придётся вводить третье и последующие измерения.
20х20 вместо бесконечности, плюс я его слепил из того, что было на скорую руку, так что не без косяков.
красивая задача -
4*(2^n-1)^2 = 2 * 2^(2n+1) - 2^(n+3) + 4
Таким образом, в первых трех клетках сосредоточенно более половины объема мощности доски, и они не могут быть освобождены за конечное число ходов (я всегда могу взять n больше предполагаемого минимального конечного числа ходов, что бы шашки гарантированно не появились за пределами квадрата n*n с положительными координатами)
Edited at 2014-10-11 10:49 am (UTC)