Задача Лукаса


Задача


Пять белых и пять черных шашек построены в горизонтальную линию на 11 клетках с одной свободной клеткой между ними.



Расположение шашек в задаче Лукаса


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


Назад ходить и перепрыгивать запрещено.


Ходить можно в любом порядке. То есть не обязательно ходы белых и черных шашек должны чередоваться.


Как переместить все белые шашки направо на место черных, а черные налево на место белых?


За какое количество ходов это можно сделать?



Решение


Перестановка всех шашек требует минимум 35 перемещений.


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


Вот как это выглядит с картинками через каждые 7 ходов.


б, ч, ч, б, б, б, ч.



Расположение шашек в задаче Лукаса после семи ходов


ч, ч, ч, б, б, б, б.



Расположение шашек в задаче Лукаса после 14 ходов


б, ч, ч, ч, ч, ч, б.



Расположение шашек в задаче Лукаса после 21 перемещения


б, б, б, б, ч, ч, ч.



Расположение шашек в задаче Лукаса после 28 ходов


И, наконец последние 7 ходов: ч, б, б, б, ч, ч, б.



------------------

Автор статьи: Евгений Миронов.

Комментарии к этой заметке больше не принимаются.



июль 2015
пн вт ср чт пт сб вс
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31