П'ятна́шки (п'ятнадцять) — популярна головоломка, придумана у 1878 році Ноєм Чепменом. Складається з 15 однакових квадратних пластинок з нанесеними числами від 1 до 15. Пластинки поміщаються в квадратну коробку, довжина сторони якої в чотири рази більша довжини сторони пластинок, відповідно в коробці залишається незаповненим одне квадратне поле. Мета гри — переміщаючи пластинки по коробці добитися впорядковування їх по номерах (як зображено на рисунку), бажано зробивши якомога менше переміщень.
Історія
Винахідником головоломки був Ной Палмер Чепмен, поштмейстер з Канастоти, який ще в 1874 році показував друзям головоломку, що складалася з шістнадцяти пронумерованих квадратиків, які треба було скласти в ряди по чотири штуки так, щоб сума чисел в кожному ряду була рівна 34. Потім син Ноя Чепмена, Френк Чепмен привіз допрацьовані головоломки в Сиракузи (штат Нью-Йорк), а потім в Гартфорд (Коннектикут), де слухачі почали виробництво головоломки. До 1879 року вона вже продавалася не тільки в Хартфорді, але і в Бостоні. Тоді про гру дізнався художник по дереву Маттіас Райс. У грудні 1879 року він почав бізнес по виробництву нової головоломки під назвою «Дорогоцінна головоломка» англ. Gem Puzzle. На початку 1880 року Чарльз Певі, дантист з Вустера, привернув увагу громадськості, запропонував грошову винагороду за рішення задачі збирання головоломки, що додало популярності новій забаві. Весною того ж року гра досягла Європи. 21 лютого 1880 року Ной Чепмен спробував оформити патент на свій винахід, проте заявка на патент була відхилена, оскільки мало відрізнялася від вже оформленого трьома роками раніше патенту «Хитрі блоки».
Математична теорія
Позначивши пусту клітину числом 16, властивості головоломки можна одержувати із властивостей перестановок чисел 1..16. Так кожне переміщення у головоломці відповідає деякій транспозиції числа 16 і деякого іншого числа. Кожна така транспозиція змінює парність перестановки чисел. Якщо в початковому розміщенні пуста клітина розташована у нижньому правому куті, то на своє місце вона може повернутися за парну кількість кроків, тобто парність у цьому випадку не зміниться. Тому якщо початкова перестановка є непарною (як наприклад на другому малюнку) то головоломка розв'язку не має. У загальному випадку розв'язку не існує, якщо непарним є число де n — рівно нулю для парних початкових перестановок чисел 1..16 і одиниці для непарних, 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. . Електронна версія попереднього варіанту під назвою
- Jerry Slocum, Dic Sonneveld The 15 Puzzle book, 2006
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (грудень 2015) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
P yatna shki p yatnadcyat populyarna golovolomka pridumana u 1878 roci Noyem Chepmenom Skladayetsya z 15 odnakovih kvadratnih plastinok z nanesenimi chislami vid 1 do 15 Plastinki pomishayutsya v kvadratnu korobku dovzhina storoni yakoyi v chotiri razi bilsha dovzhini storoni plastinok vidpovidno v korobci zalishayetsya nezapovnenim odne kvadratne pole Meta gri peremishayuchi plastinki po korobci dobitisya vporyadkovuvannya yih po nomerah yak zobrazheno na risunku bazhano zrobivshi yakomoga menshe peremishen Rozv yazok golovolomkiIstoriyaVinahidnikom golovolomki buv Noj Palmer Chepmen poshtmejster z Kanastoti yakij she v 1874 roci pokazuvav druzyam golovolomku sho skladalasya z shistnadcyati pronumerovanih kvadratikiv yaki treba bulo sklasti v ryadi po chotiri shtuki tak shob suma chisel v kozhnomu ryadu bula rivna 34 Potim sin Noya Chepmena Frenk Chepmen priviz dopracovani golovolomki v Sirakuzi shtat Nyu Jork a potim v Gartford Konnektikut de sluhachi pochali virobnictvo golovolomki Do 1879 roku vona vzhe prodavalasya ne tilki v Hartfordi ale i v Bostoni Todi pro gru diznavsya hudozhnik po derevu Mattias Rajs U grudni 1879 roku vin pochav biznes po virobnictvu novoyi golovolomki pid nazvoyu Dorogocinna golovolomka angl Gem Puzzle Na pochatku 1880 roku Charlz Pevi dantist z Vustera privernuv uvagu gromadskosti zaproponuvav groshovu vinagorodu za rishennya zadachi zbirannya golovolomki sho dodalo populyarnosti novij zabavi Vesnoyu togo zh roku gra dosyagla Yevropi 21 lyutogo 1880 roku Noj Chepmen sprobuvav oformiti patent na svij vinahid prote zayavka na patent bula vidhilena oskilki malo vidriznyalasya vid vzhe oformlenogo troma rokami ranishe patentu Hitri bloki Matematichna teoriyaOdna iz startovih pozicij sho ne maye rozv yazkiv Poznachivshi pustu klitinu chislom 16 vlastivosti golovolomki mozhna oderzhuvati iz vlastivostej perestanovok chisel 1 16 Tak kozhne peremishennya u golovolomci vidpovidaye deyakij transpoziciyi chisla 16 i deyakogo inshogo chisla Kozhna taka transpoziciya zminyuye parnist perestanovki chisel Yaksho v pochatkovomu rozmishenni pusta klitina roztashovana u nizhnomu pravomu kuti to na svoye misce vona mozhe povernutisya za parnu kilkist krokiv tobto parnist u comu vipadku ne zminitsya Tomu yaksho pochatkova perestanovka ye neparnoyu yak napriklad na drugomu malyunku to golovolomka rozv yazku ne maye U zagalnomu vipadku rozv yazku ne isnuye yaksho neparnim ye chislo n i j displaystyle n i j de n rivno nulyu dlya parnih pochatkovih perestanovok chisel 1 16 i odinici dlya neparnih i j poziciya pustoyi klitini Natomist kozhne pochatkove rozmishennya dlya yakogo chislo n i j displaystyle n i j ye parnim maye rozv yazok golovolomki Cej fakt dostatno dovesti dlya vipadku koli u pochatkovomu rozmishenni pusta klitina rozmishuyetsya u nizhnomu pravomu kuti Potribno rozglyanuti mnozhinu perestanovok sho mozhna oderzhati z pravilnogo rozmishennya sho ye rozvyazkom golovolomki Treba dovesti sho cya mnozhina ye mnozhinoyu parnih perestanovok chisel 1 15 Spershu mozhna pobachiti sho sered perestanovok yaki mozhna zdijsniti ye cikl 11 12 15 zdijsnyuyuchi ruh pivden shid pivnich zahid Todi mozhna zdijsniti perestanovki tak shob chisla 11 i 12 buli fiksovani a na misci 15 opinitsya dovilne inshe chislo Tobto v grupi perestanovok takozh ye cikli 11 12 x dlya dovilnogo x z mnozhini 1 10 13 14 Taki cikli porodzhuyut grupu parnih perestanovok sho j dovodit tverdzhennya Div takozhKubik RubikaLiteraturaDavid 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 Elektronna versiya poperednogo variantu pid nazvoyu Jerry Slocum Dic Sonneveld The 15 Puzzle book 2006 ISBN 1 890980 15 3 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno gruden 2015