Rubik kubining matematikasi

Rubik kubining matematikasi - bu Rubik kubining xususiyatlarini abstrakt matematik nuqtai nazaridan oʻrganish uchun matematik usullar toʻplami. Matematikaning ushbu boʻlimi kublarni yigʻish algoritmlarini oʻrganadi va ularni baholaydi. Grafika nazariyasi, guruh nazariyasi, hisoblash nazariyasi va kombinatorikaga asoslangan.

Chigallangan (pastda) va terilgan (yuqorida) Rubik kubi

Rubik kubini ixtiyoriy konfigurasiyadan yakuniy konfigurasiyaga (yigʻilgan kub) oʻtkazish uchun moʻljallangan koʻplab algoritmlar mavjud. 2010-yilda Rubik kubini ixtiyoriy konfigurasiyadan yigʻilgan konfigurasiyaga (koʻpincha „yigʻish“ yoki „yechim“ deb ataladi) oʻtkazish uchun kub yuzalarining 20 dan ortiq burilishi yetarli emasligi qatʼiy isbotlangan. Bu raqam Rubik kublari guruhining Kayli grafigining diametri. 2014-yilda Rubik kubini faqat yuzlarning 90° burilishi yordamida yechish uchun har doim 26 ta harakat yetarli ekanligi isbotlangan.

Belgilanishi

$L,R,F,B,U,D$ harflari mos ravishda chap (chap), oʻng (oʻng), old (old), orqa (orqa), yuqori (yuqoriga) va pastki (pastga) yuzlarning soat yoʻnalishi boʻyicha 90° ga aylanishini bildiradi. 180 ° burilishlar harfning oʻng tomoniga 2 qoʻshilishi yoki harfning oʻng tomoniga 2 ustki belgisi qoʻshilishi bilan koʻrsatiladi. 90° soat miliga teskari burilish tire (′) qoʻshish yoki harfning oʻng tomoniga -1 ustki belgisini qoʻshish orqali koʻrsatiladi. Masalan, yozuvlar $L^{2}$ va $L2$ yozuvlar kabi ekvivalentdir $L'$ va $L^{-1}$ .

Rubik kublari guruhi

Rubik kubini matematik guruhga misol sifatida oʻrganish mumkin.

Rubik kubining yuzalarining oltita aylanishining har biri yuzlarning markazlari boʻlmagan 48 ta Rubik kubining yorliqlari toʻplamining simmetrik guruhining elementi sifatida qaralishi mumkin. Aniqroq aytganda, siz barcha 48 ta tegni 1 dan 48 gacha raqamlar bilan belgilashingiz va har bir harakatga mos keltirishingiz mumkin. $\{F,B,U,D,L,R\}$ nosimmetrik guruh elementi $S_{48}$ .

Bunda Rubik kublari guruhi $G$ kichik guruh sifatida belgilangan $S_{48}$ yuzning oltita aylanishi bilan yaratilgan :

$G=\langle F,B,U,D,L,R\rangle .$

Guruh tartibi $G$ bu

$|G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\,252\,003\,274\,489\,856\,000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.$

Har $4{,}325\cdot 10^{19}$ konfigurasiyalardan biri 20 dan ortiq boʻlmagan harakatlarda hal qilinishi mumkin (agar yuzning har qanday burilishi harakat sifatida hisoblansa).

Elementning eng katta tartibi $G$ 1260 ga teng. Masalan, harakatlar ketma-ketligi $(R\ U^{2}\ D^{\prime }\ B\ D^{\prime })$ Rubik kubi asl holatiga qaytgunga qadar 1260 marta takrorlanishi kerak .

"Superflip" - boshlang'ichdan 20f * masofada joylashgan birinchi aniqlangan konfigurasiya.

Tistletueyt algoritmi

1980-yillarning boshlarida ingliz matematigi Morvin Tistletueyt yuqori chegarani sezilarli darajada yaxshilagan algoritmni ishlab chiqdi. Algoritmning tafsilotlari 1981-yilda Scientific American jurnalida Duglas Xofstadter tomonidan nashr etilgan. Algoritm guruh nazariyasiga asoslangan va toʻrt bosqichni oʻz ichiga olgan.

Tistletueyt 4 uzunlikdagi bir qator kichik guruhlardan foydalangan

$G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\},$

bu yerda:

• $G_{0}=\langle L,R,F,B,U,D\rangle .$

Bu guruh Rubik kubi guruhi bilan bir xil $G$ . Uning tartibi

${\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{2}}=43\,252\,003\,274\,489\,856\,000.$

• $G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle .$

Ushbu kichik guruh chap yoki oʻng tomonlarning ± 90 ° ga aylanishidan foydalanmasdan hal qilinishi mumkin boʻlgan barcha konfigurasiyalarni oʻz ichiga oladi. Uning tartibi

${\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\,119\,142\,223\,872\,000.$

• $G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle .$

Ushbu kichik guruh toʻrtta vertikal yuzning ±90 ° ga aylanishi taqiqlangan holda hal qilinishi mumkin boʻlgan barcha konfiguratsiyalarni oʻz ichiga oladi. Uning tartibi

$8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2}}=19\,508\,428\,800.$

• $G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle .$

Bu kichik guruh faqat 180 ° burilish (yarim burilish) yordamida hal qilinishi mumkin boʻlgan barcha konfigurasiyalarni oʻz ichiga oladi. U „kvadratlar guruhi“ deb nomlangan. Uning tartibi quyidagicha:

$(4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2}}\cdot 1=663\,552.$

• $G_{4}=\{1\}.$

Ushbu kichik guruh bitta dastlabki konfigurasiyani oʻz ichiga oladi.

Kosembaning Ikki fazali algoritmi

Kosemba algoritmidagi Rubik kubining oraliq holati. Ikkinchi bosqichda ruxsat etilgan harakatlar "+" va "-" belgilarining joylashuvini saqlab qoladi

Tistlueyta algoritmini 1992-yilda Darmshtadtlik matematika oʻqituvchisi Gerbert Kosemba takomillashtirilgan.

Kosemba algoritm qadamlari sonini ikkitaga qisqartirgan:  :

• $G_{0}=\langle U,D,L,R,F,B\rangle$
• $G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
• $G_{2}=\{1\}$

12 rangli megaminx

Megaminx

Megaminx - Rubik kubining dodekaedr shaklidagi eng oddiy analogidir. 12 rangli Megaminx konfigurasiyasi soni 1,01·10 ⁶⁸ ni tashkil qiladi.

Havolalar

• Qayta nashr etilgan: Rik van Grol „The Quest for God's Number“, . The Best Writing on Mathematics 2011. Princeton University Press, 2011 — 27—34-bet. ISBN 1-400-83954-8, 978-1-400-83954-4. 

• Jaap Scherphuis. „Jaap's Puzzle Page“ (inglizcha). Qaraldi: 20-iyul 2013-yil.
• Herbert Kociemba. „Cube Explorer 5.01“ (inglizcha). Qaraldi: 20-iyul 2013-yil.
• Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. „God's Number is 20“ (inglizcha). Qaraldi: 20-iyul 2013-yil.
• Martin Schönert. „Cube Lovers archives converted to HTML“ (inglizcha). Qaraldi: 20-iyul 2013-yil.
• Mark Longridge. „Domain of the Cube Forum“ (inglizcha). 2013-yil 22-sentyabrda asl nusxadan arxivlangan. Qaraldi: 20-iyul 2013-yil.
• W. D. Joyner. „Lecture notes on the mathematics of the Rubik's cube“ (inglizcha). 2013-yil 5-sentyabrda asl nusxadan arxivlangan. Qaraldi: 22-iyul 2013-yil.
• Tomas Rokicki. „Computers and the Cube (slides)“ (inglizcha) (3-noyabr 2009-yil). Qaraldi: 30-iyul 2013-yil.