Почему нельзя собрать Пятнашки, поменяв 14 и 15. Простое доказательство без Теории групп
Habr ·
Пятнашки - это простая головоломка-пазл известная любому школьнику прошлого века :) 15 пронумерованных костяшек случайным порядком расставлены на доске 4х4. Одна клетка остается свободной и на это свободное место можно сдвинуть соседнюю костяшку. Задача - перемещая косточки, выставить их по порядку слева направо, сверху вниз, от 1 до 15. Есть большое количество онлайн реализаций этой игры, но все эти реализации, дабы не нервировать игроков, всегда имеют решение. Кроме той, которую я написал специально для этой статьи . В настоящих Пятнашках, когда костяшки высыпались на стол и случайным образом ставились на поле, решение находилось не всегда. Это как в карточном пасьянсе - может сойтись, а может и нет. Я помню, в школе была любимая подколка: когда твой одноклассник первый раз собирал пятнашки, я менял местами последние костяшки 14 и 15, и предлагал собрать заново. И вот твой товарищ, который еще минуту назад сиял от осознания собственной сообразительности, всю перемену двигает костяшками и у него ничего не получается. Почему? Тогда в школе ответ был очевидный, потому что не получается, и все! Можешь попробовать! Они либо собираются, либо нет. Причем если нет, то всегда в самом последнем ряду 15 стоит перед 14. Конечно, у математиков есть доказательство, почему это невозможно сделать - все дело в четности инверсий, но во-первых в 3 третьем классе такое объяснение не прокатит, а во вторых - оно выглядит, как доказательство следствия, не объясняя причину! Оно звучит так: При определенной нумерации ячеек при нечетном количество инверсий пазл сложить невозможно. Я же хотел найти доказательство без знания того, что такое инверсия, просто "на пальцах" и главное, все же докопаться до причины.. Читать далее
Пятнашки - это простая головоломка-пазл известная любому школьнику прошлого века :) 15 пронумерованных костяшек случайным порядком расставлены на доске 4х4. Одна клетка остается свободной и на это свободное место можно сдвинуть соседнюю костяшку. Задача - перемещая косточки, выставить их по порядку слева направо, сверху вниз, от 1 до 15. Есть большое количество онлайн реализаций этой игры, но все эти реализации, дабы не нервировать игроков, всегда имеют решение. Кроме той, которую я написал специально для этой статьи . В настоящих Пятнашках, когда костяшки высыпались на стол и случайным образом ставились на поле, решение находилось не всегда. Это как в карточном пасьянсе - может сойтись, а может и нет. Я помню, в школе была любимая подколка: когда твой одноклассник первый раз собирал пятнашки, я менял местами последние костяшки 14 и 15, и предлагал собрать заново. И вот твой товарищ, который еще минуту назад сиял от осознания собственной сообразительности, всю перемену двигает костяшками и у него ничего не получается. Почему? Тогда в школе ответ был очевидный, потому что не получается, и все! Можешь попробовать! Они либо собираются, либо нет. Причем если нет, то всегда в самом последнем ряду 15 стоит перед 14. Конечно, у математиков есть доказательство, почему это невозможно сделать - все дело в четности инверсий, но во-первых в 3 третьем классе такое объяснение не прокатит, а во вторых - оно выглядит, как доказательство следствия, не объясняя причину! Оно звучит так: При определенной нумерации ячеек при нечетном количество инверсий пазл сложить невозможно. Я же хотел найти доказательство без знания того, что такое инверсия, просто "на пальцах" и главное, все же докопаться до причины.. Читать далее