П'ятнашки

Розв'язок головоломки

П'ятна́шки (п'ятнадцять) — популярна головоломка, придумана у 1878 році Ноєм Чепменом. Складається з 15 однакових квадратних пластинок з нанесеними числами від 1 до 15. Пластинки поміщаються в квадратну коробку, довжина сторони якої в чотири рази більша довжини сторони пластинок, відповідно в коробці залишається незаповненим одне квадратне поле. Мета гри — переміщаючи пластинки по коробці добитися впорядковування їх по номерах (як зображено на рисунку), бажано зробивши якомога менше переміщень.

Історія

Винахідником головоломки був Ной Палмер Чепмен, поштмейстер з Канастоти, який ще в 1874 році показував друзям головоломку, що складалася з шістнадцяти пронумерованих квадратиків, які треба було скласти в ряди по чотири штуки так, щоб сума чисел в кожному ряду була рівна 34. Потім син Ноя Чепмена, Френк Чепмен привіз допрацьовані головоломки в Сиракузи (штат Нью-Йорк), а потім в Гартфорд (Коннектикут), де слухачі Американської школи для глухих почали виробництво головоломки. До 1879 року вона вже продавалася не тільки в Хартфорді, але і в Бостоні. Тоді про гру дізнався художник по дереву Маттіас Райс. У грудні 1879 року він почав бізнес по виробництву нової головоломки під назвою «Дорогоцінна головоломка» англ. Gem Puzzle. На початку 1880 року Чарльз Певі, дантист з Вустера, привернув увагу громадськості, запропонував грошову винагороду за рішення задачі збирання головоломки, що додало популярності новій забаві. Весною того ж року гра досягла Європи. 21 лютого 1880 року Ной Чепмен спробував оформити патент на свій винахід, проте заявка на патент була відхилена, оскільки мало відрізнялася від вже оформленого трьома роками раніше патенту «Хитрі блоки».

Математична теорія

Одна із стартових позицій, що не має розв'язків

Позначивши пусту клітину числом 16, властивості головоломки можна одержувати із властивостей перестановок чисел 1..16. Так кожне переміщення у головоломці відповідає деякій транспозиції числа 16 і деякого іншого числа. Кожна така транспозиція змінює парність перестановки чисел. Якщо в початковому розміщенні пуста клітина розташована у нижньому правому куті, то на своє місце вона може повернутися за парну кількість кроків, тобто парність у цьому випадку не зміниться. Тому якщо початкова перестановка є непарною (як наприклад на другому малюнку) то головоломка розв'язку не має. У загальному випадку розв'язку не існує, якщо непарним є число $n+i+j\,,$ де n — рівно нулю для парних початкових перестановок чисел 1..16 і одиниці для непарних, i, j — позиція пустої клітини.

Натомість кожне початкове розміщення, для якого число $n+i+j$ є парним, має розв'язок головоломки. Цей факт достатньо довести для випадку коли у початковому розміщенні пуста клітина розміщується у нижньому правому куті. Потрібно розглянути множину перестановок, що можна одержати з правильного розміщення (що є розвязком головоломки). Треба довести, що ця множина є множиною парних перестановок чисел 1..15.

Спершу можна побачити, що серед перестановок, які можна здійснити є цикл (11, 12, 15) (здійснюючи рух південь-схід-північ-захід). Тоді можна здійснити перестановки так щоб числа 11 і 12 були фіксовані, а на місці 15 опиниться довільне інше число. Тобто в групі перестановок також є цикли (11, 12, x) для довільного x з множини 1-10, 13, 14. Такі цикли породжують групу парних перестановок, що й доводить твердження.

Див. також

• Кубик Рубика

Література

• David Joyner (2002). Adventures in Group Theory : Rubik's Cube, Merlin's Machine, and Other Mathematical Toys. The Johns Hopkins University Press. ISBN 0-8018-6947-1. Електронна версія попереднього варіанту під назвою Mathematics of the Rubik's cube
• Jerry Slocum, Dic Sonneveld The 15 Puzzle book, 2006 ISBN 1-890980-15-3