Популярно о науке

Previous Entry Share Next Entry
Новая не новая задачка.
ahiin
Забегая вперед, отмечу, что то решение, которое нашел лично я (вполне возможно, что есть и другие), использует идею, а скорее подход, чрезвычайно широко применяемый как в математике, так и в физике. Это дело стоит обсудить поподробнее, так что разбор решения будет лишь малой частью грядущего поста (а то и двух). Для интриги добавлю, что, например, Григорий Перельман в свое время использовал неизмеримо более продвинутый, но тем не менее идейно близкий, подход в своем знаменитом доказательстве гипотезы Пуанкаре.

А теперь сама задача.

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

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

Одна из возможных последовательностей первых четырех ходов изображена на рисунке ниже (шашка, которую мы убираем на текущем ходу показана окружностью):

picture2

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

Решение на следующей неделе. Комментарии до публикации решения скрыты.

PS. Я умышленно не указываю пока источник картинок. Тем не менее, они достаточно легко гуглятся. Однако, на том конце решения нет. Есть только существенная подсказка (на английском языке, ага). Ежели станет невмоготу, можете воспользоваться.

PPS. Знаний свыше обычной школьной программы 9 класса по алгебре для решения не потребуется.


UPD. Уважаемый kercenter весьма оперативно сделал интерактивную версию игры. Поле ограничено, 20х20, но для того, чтобы вникнуть в суть происходящего — более чем достаточно.

  • 1

M 0[9R`0F-u%/?˰ <8lSa'Kl&hY(n կ #QGN [HD2xd

ОТВЕТ: указать последовательность ходов невозможно, т.к. если она вообще существует, то должна быть бесконечной.

ПРИМЕЧАНИЕ К ОТВЕТУ: в качестве ответа формулировкой задачи ен предусмотрен алгоритм (тем более алгоритм, никогда не останавливающийся).

ПИРМЕЧАНИЕ К ОТВЕТУ №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)

Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal северного региона. Подробнее о рейтинге читайте в Справке.

ЗАКРАШЕНО БЫТЬ НЕ МОЖЕТ:

1. Как мы установили (см. предыдущий комментарий, вес ячеек, вес всего квадранта...) для того, чтобы "оствободить" первые три ячейки необходимо (и достаточно) "закрасить" весь остальной квадрант.
2. При каждом преобразовании всегда будут закрашены только 2 ячейки в самом левом столбце \ только 2 ячейки в самой нижней строке.

3. Необходимое условие освобождения 3х первых ячеек (закраска всех остальных ячеек) не может быть выполнена.

ОТВЕТ:
закрашивание невозможно.

Edited at 2014-10-10 05:46 pm (UTC)

Ну, конечной такой последовательности ходов не существует, как говорит нам функция 2/(2-x)^2.

Ок, пусть по вертикали клетки будут обозначены цифрами начиная от 1 (единице соответствует нижний ряд), а по горизонтали = латинскими буквами (букве а соответствует левый стобец)

Обозначим первую координату фишки через 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-х диагональных фишек, один набор из трёх и один из четырёх.

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

Или, можно сказать, что решение есть, но для него придётся вводить третье и последующие измерения.

Предлагаю предложить любителям потыкать решение поискать его там: http://ordenvoronov.clan.su/calculon/ptpt.html
20х20 вместо бесконечности, плюс я его слепил из того, что было на скорую руку, так что не без косяков.

красивая задача -

но мне её кто-то когда-то рассказал вместе с решением (веса, убывающие вдвое вправо и вверх - а каково её происхождение, кто её придумал и т.п.? И ещё - верно ли какое-то позитивное утверждение (что если сумма весов мала, то можно что-то очистить)?

Обозначим координаты стартовых клеток с шашками за (n,n) (n-1,n) (n,n-1). Зададим для каждой клетки характеристику "мощности": мощность клетки (m,k) c шашкой равна 2^(m+k), а мощность пустой клетки - 0. Легко понять, что во время хода суммарная мощность доски не меняется: 2^(m+k)+0+0 = 2^(m+k-1)+2^(m-1+k). В начале игры мощность доски равна 2^(2n+1). Максимальная мощность доски (при заполнении всех клеток с положительными координатами) равна

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)

  • 1
?

Log in

No account? Create an account