Головоломки онлайн

Представим, что пустое место заполнено фишкой с номером 16. Значит каждый ход — перемещение фишки — будет состоять в том, что она меняется местами с фишкой 16. Операцию, при которой какие-либо фишки (не обязательно соседние!) меняются местами, можно назвать — обменом; математический термин, применяемый к этим операциям — транспозиция. Очевидно, что из любой расстановки 16 фишек можно не более чем за 15 обменов получить правильную позицию — назовем эту позицию S — и любую другую расстановку. При этих перестановках не запрещается вынимать фишки из коробки. Например, можно первым ходом поставить на свое место фишку 1, поменяв ее с той фишкой, занимающей это место, затем таким же образом поставить на место фишку 2 и т. д. Последними ходами будет обмен фишек 15 и 16. Конечно, возможно, что по ходу перестановок какие-то фишки сразу, автоматически, попадут на свои места, и их переставлять не придется, тогда число обменов будет меньше 15. Можно расставлять фишки используя эту же систему, но в порядке, скажем 16, 15, 14, .... или в каком то, только Вам известном порядке, и тогда число перестановок окажется другим. Однако, как бы Вы не ухищрялись, какие бы способы ни выбирали, превращающую одну заданную расстановку фишек в другую, четность числа перестановок в этой выбранной Вами последовательности всегда будет одной и той же. Это очень важное и не очевидное заключение докажем ниже. Это позволяет дать следующее определение: расстановка фишек является четной, если эту расстановку можно превратить в правильную (начальную) позицию с помощью четного числа перестановок, и нечетной в противном случае. В математике обычно используют термин не «расстановка», а «перестановка»; к этому мы еще вернемся позднее. Правильная расстановка S сама всегда четная, а ловушка Лойда, назовем ее L, нечетная. Так почему же они не могут переходить друг в друга? Как ранее уже было сказано, каждый ход в игре «пятнашки» можно рассматривать как перестановку фишек, меняясь с одной из соседних. Значит, при каждом ходе четность расстановки 16 фишек меняется: если до совершения хода расстановку фишек можно было упорядочить за N перестановок, то после этого хода — за N+1 перестановок (взяв этот ход назад), а числа N и N+1 имеют разную четность. В этих двух расстановках классической головоломки Лойда дырка (или фишка 16) расположена одинаково. Если бы мы могли одну расстановку фишек перевести в другую, то фишка 16 должна была совершить одинаковое количество ходов вверх и вниз, одинаковое количество ходов вправо и влево, иначе она не вернулась бы на прежнее место. Поэтому пришлось бы сделать четное количество ходов, а так как при каждом ходе четность расстановки меняется, в начале и в конце четность была бы одинаковой. Но позиции S и L, мы видим, имеют разную четность. Рассмотрев эту известную математическую головоломку, придуманную замечательным американским шахматистом и автором головоломок, будем надеяться, что когда-нибудь ещё придумают что то, более популярную, чем игра «пятнашки!

Новости - Категории   Темы новостей