чому-15-типазл-неможливо-розв'язати

Чому 15-типазл неможливо розв'язати

"15-типазл", відомий також як "цифрова задача 15", не є нерозв'язним, а радше цільовий стан не може бути досягнутий з деяких початкових станів.

Опис гри

"15-типазл" — це гра зі слайдерами, де ігрове поле — це сітка 4×4 з 15 слайдерами, позначеними числами від 1 до 15, та порожнім місцем. Мета гравця — перемістити слайдери в порядку зліва направо, зверху вниз, що призведе до впорядкованої послідовності від 1 до 15, з порожнім місцем у правому нижньому куті.

Випадки нерозв'язності

Ситуація не може бути законно переміщена для досягнення цільового стану, якщо і тільки якщо кількість пар з оберненим порядком у початковому стані є непарною. Пара з оберненим порядком - це пара чисел в послідовності, які називаються парою з оберненим порядком, якщо позиції, на яких вони стоять, знаходяться в зворотному порядку величини, тобто число попереду більше, ніж число позаду . Наприклад, у послідовності 2, 4, 3, 1 обернені пари — це (2, 1), (4, 3), (4, 1), (3, 1), всього чотири.

Доведення.

Переміщення слайдерів на дошці можна розглядати як перетворення розташування цих слайдерів. Кожного разу, коли слайдер переміщується, порожнє місце насправді обмінюється з сусіднім слайдером. І ця операція обміну змінює парність оберненого логарифма розташування. Обернений логарифм цільового стану дорівнює 0, що є парним числом. Якщо обернений логарифм початкового стану непарний, то незалежно від кількості переміщень його обернений логарифм не може бути змінено на парне число, і цільовий стан неможливо досягти.

Якщо вам подобається грати в Пазли також, це абсолютно безплатно, весело і легко.