N-am colectat niciodată Cubul lui Rubik. Chiar și în copilărie am avut mereu multe lucruri interesante de făcut. Dar pentru a fi sincer - nu am putut.
Săptămâna trecută a avut loc un eveniment care ma făcut să aflu ce este Algoritmul lui Dumnezeu, Numărul lui Dumnezeu și cum se leagă de cuburi.
Trei câte trei la trei - nu atât de greu
Combinatorica este o ramură a matematicii în care totul poate fi amestecat în diferite moduri. Toată lumea îi place această tulburare, dar vă place să călătoriți, să iubești și să săniți. În combinatorie, toate aceste intermixări sunt de obicei contorizate. Nu este așa de ușor, aproape ca și cum ați aduna Cubul lui Rubik.
Să presupunem că ați găsit trei cuburi Lego diferite colorate într-o cafenea unde așteptați pe cineva, dar acesta întârzie. Începeți să conectați aceste trei cuburi în mod diferit, creând tot felul de combinații ale acestora. Cu siguranță nu-ți pasă, te gândești doar la timp. Dar combinatorica stie - poti colecta 3! configurații unice. 3! acest lucru nu este un triplu, care ar trebui să vă surprindă, este factorial al triplei. 3! = 1 × 2 × 3 = 6. "Mai mult de șase configurații nu vor fi colectate", spune combinatorii, dar nu ne pasă, timpul se scurge.
- 3! variante de permutare a trei cuburi și bărbați puțin A. Dar Lego poate fi asociată cu o cafenea?
Deci, dacă ați fi învârtit Cubul lui Rubik într-o cafenea, ar fi puțin mai lipsit de speranță. Când întoarcem cubul lui Rubik, combinatorii ne spun următoarele:
- Ce poate lua 211 omenire pentru un an întreg, poți cumpăra 30 de ruble. Nu va înceta niciodată să mă uimească.
Și aici Dumnezeu
Algoritmul lui Dumnezeu este un algoritm pe care Cube-ul Rubik îl rezolvă pentru numărul minim de mișcări. Cel mai interesant este că nimeni nu știe chiar dacă acest algoritm există sau nu. Acest lucru, aparent, este singurul lucru pe care îl au în comun cu Dumnezeu.
Numărul lui Dumnezeu pentru Cubul lui Rubik este numărul minim de mișcări pentru care algoritmul lui Dumnezeu va rezolva cu siguranță orice configurație a Cubei. Asta este, există configurații care Algoritmul lui Dumnezeu decide pentru o mișcare. Dar nu există astfel de oameni cărora să le cheltuiască mai mult decât numărul lui Dumnezeu.
Săptămâna trecută, au spus câțiva cercetători. că ei au calculat numărul lui Dumnezeu.
Numărul lui Dumnezeu pentru algoritmul lui Rubik's Cube este 20. Da, este păcat că nu este 42.
20 este un număr destul de comun, dar în contextul lui Cub Rubik nu mai există un număr sarcastic și batjocoritor. Faptul este că în Cubul lui Rubik există 20 de piese în mișcare. Recunoaste-te, disperandu-te cel putin odata ce ai vrut sa dezasamblezi Cube-ul, apoi sa-l aduni cat mai bine si sa te calmezi? În acel moment, numărul de Dumnezeu a râs de tine!
La urma urmei, detaliile sunt de asemenea 20.
Prea multe cifre pentru un articol
Ce ar putea fi mai simplu, rămâne doar să rezolvăm combinațiile. Iată cum au decis să facă acest lucru ***:
- Pentru a rupe 43 252 003 274 489 856 000 de state în 2 217 093 120 subgrupuri
- Reduceți numărul de subseturi la 55 882 296, deoarece unele sunt obținute de la cealaltă prin întoarcerea sau reflexiile oglinzii ale Cubei
- Nu căutați soluția optimă pentru fiecare stat, nu vă mulțumiți cu nici o mișcare mai mare de 20 de mișcări
- Scrieți un program care rezolvă un subset în aproximativ 20 de secunde
Punctul 1) este foarte important pentru a se conforma alineatului (2). Trebuie să fii o vulpe șiretlică pentru a construi subseturi în așa fel încât să fie apoi tăiate.
Nevoia de a căuta cele mai bune căi de la punctul 3) nu este, de asemenea, un capriciu. Cu siguranță, ar putea face acest lucru, dar nu au nevoie - au vrut doar să verifice că numărul de Dumnezeu este de 20 și să nu găsească toate căile optime pentru toate configurațiile.
După ce au procesat toate subseturile, nu au găsit niciun stat care necesită 21 sau mai multe mutări de rezolvat. Așa sa dovedit - numărul lui Dumnezeu pentru Cubul lui Rubik este de 20.
Cum să verificați că înțelegeți totul?
Găsiți numărul lui Dumnezeu nu înseamnă să găsiți Algoritmul lui Dumnezeu. Dacă înțelegeți acest lucru și sunteți de acord, atunci ați înțeles totul. În caz contrar, puteți încerca să citiți din nou definiția algoritmului lui Dumnezeu și numărul lui Dumnezeu.
Cum să frecați nasul băieților?
Le poți decora, nu glumesc. Pentru aceasta, trebuie să veniți cu un algoritm care în pasul 3) va căuta numai mișcări optime. Acesta va fi Algoritmul lui Dumnezeu și probabil că veți fi sărută de picioarele voastre.
Informații interesante despre acest subiect
- Configurațiile cubului, care necesită 20 de mișcări de rezolvat, nu sunt foarte frecvente (aproximativ 0,000000000007% din numărul total de configurații). Primul a fost descoperit la numai 15 ani după apariția luminii cubice.
- Computerele rezolvă Cubul lui Rubik mai repede decât oamenii se uită la ele. Pentru a căuta toate opțiunile, a fost nevoie de 35 de ani-bază. Acest lucru înseamnă că un nucleu al unui computer, pe care s-au făcut calcule, ar fi avut de-a face cu cei 35 de ani. Câte nuclee au avut la dispoziție, cercetătorii nu raportează.
- Capacitatea computerului pentru rezolvarea problemei a fost oferită de Google, în care unul dintre cercetători lucrează.
Uneori, la sfârșitul articolelor, pun întrebarea - de ce? Dar astăzi este o altă poveste, pentru că nu este foarte clar de ce să știm numărul lui Dumnezeu pentru Cubul lui Rubik. Dacă credeți că voi spune "Gotcha", - glumesc despre o glumă și vă spun în mod accidental ce avantaj va aduce această descoperire, atunci vă greșiți. Nu știu de ce. Dar știu ce putem suporta pentru noi înșine din toate astea.
De fapt, de mult timp am luat-o deja pentru noi înșine - dacă împărțim sarcina în subtascuri, atunci soluția sa este mult mai simplă. Întreaga problemă este să se descompună în mod corespunzător.
Și există timpuri noi pentru știință, când unele lucruri devin mai rapide pentru a verifica decât a dovedi. Dar am scris deja despre asta cu o minune.
Împărțiți-vă și cuceriți!
* - într-un număr mare de configurații identice Cub, rotate și reflectate, sunt considerate diferite; iar populația Pământului este înțeleasă a fi de 6,5 miliarde de oameni care nu dorm, nu mănâncă, ci doar privesc la cuburi 24 de ore pe zi
** - în 1799, cel mai neprețuit scriitor mi sa născut, Alexander Sergeevici Pușkin
*** - puncte ". "Și" PROFIT "sunt omise din cauza respectului față de cititor
Articole similare
Trimiteți-le prietenilor: