{"id":2642,"date":"2013-10-07T13:54:01","date_gmt":"2013-10-07T11:54:01","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2642"},"modified":"2022-10-11T12:48:27","modified_gmt":"2022-10-11T10:48:27","slug":"il-numero-di-dio","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2013\/10\/07\/il-numero-di-dio\/","title":{"rendered":"Il Numero di Dio"},"content":{"rendered":"

Non so se e quanto i ragazzi di oggi lo conoscano, ma per chi ha la mia et\u00e0 il Cubo di Rubik \u00e8 stato uno dei pi\u00f9 grandi tormentoni tra i giochi di abilit\u00e0. Un esempio che pi\u00f9 pratico non si pu\u00f2 delle abilit\u00e0 che esistevano al di l\u00e0 della Cortina di ferro; una struttura a prima vista impossibile – come fa il Cubo a non finire a pezzi quando lo si gira? – ma sufficientemente solida; una sensazione di sconforto quando dopo alcune mosse si scopre di non riuscire pi\u00f9 a rimettere il Cubo nella posizione iniziale. Ora \u00e8 facile trovare in rete le istruzioni per riordinarlo<\/a>: ma nel 1980 si poteva solo sperare di trovare una rivista che pubblicasse un apposito inserto (io avevo quello di Pergioco<\/i>), oppure cercare soluzioni creative tipo smontare e rimontare il Cubo. Ma i matematici sono sempre pronti a lavorare su un gioco, soprattutto se hanno la scusa di poter dire che stanno facendo matematica (le mosse sul cubo sono gli elementi di un gruppo algebrico), ed \u00e8 davvero difficile fermarli… Insomma, cos’hanno scoperto?<\/p>\n

\"un
Cubo di Rubik (da Wikimedia Commons, Rubik%27s_cube.svg)<\/figcaption><\/figure> Per prima cosa, non appena il Cubo \u00e8 stato commercializzato si \u00e8 andati alla ricerca di un modo per risolverlo, nel bene o nel male. In casi come questo si predilige la semplicit\u00e0 all’ottimizzazione; in pratica si imparano alcune combinazioni base di mosse e le si applica pur sapendo che si sta perdendo tempo. Contemporaneamente si \u00e8 dimostrato che il numero minimo di mosse necessarie nel caso peggiore doveva essere almeno 18. Questo \u00e8 stato relativamente facile: si sono contate tutte le possibili posizioni del Cubo, si sono contate tutte le possibili posizioni raggiungibili in al pi\u00f9 17 mosse, e si \u00e8 visto che non ce n’erano a sufficienza. La prima soluzione nota richiedeva nel caso peggiore un’ottantina di mosse; quindi si poteva affermare con certezza che il Cubo poteva sempre essere risolto in N<\/i> mosse, dove N<\/i> era compreso tra 18 e 80. Da qui si \u00e8 iniziato a limare i valori.<\/p>\n

Il valore minimo \u00e8 stato portato a 20 nel 1995, nel modo pi\u00f9 banale possibile: \u00e8 stata esibita una configurazione che non poteva essere risolta in meno di 20 mosse. Il guaio \u00e8 che il numero di posizioni possibili \u00e8 43.252.003.274.489.856.000 (quarantatr\u00e9 miliardi di miliardi e briciole) e mettersi a testarle tutte non sembrerebbe fattibile. Cos\u00ec si \u00e8 andati avanti con una serie di migliorie teoriche, abbassando man mano il limite massimo fino a luglio 2010, quando \u00e8 stato portato a 20 e quindi \u00e8 stata data una risposta definitiva alla domanda. Il sito cube20.org<\/a>, da cui ho preso queste informazioni, spiega come si \u00e8 riusciti ad arrivarci: essenzialmente per forza bruta. Pi\u00f9 precisamente, il gruppo di lavoro:<\/p>\n

    \n
  1. ha suddiviso le posizioni in 2.217.093.120 insiemi di 19.508.428.800 posizioni l’uno;<\/li>\n
  2. per ragioni teoriche, ha dimostrato che in ciascun insieme le posizioni “essenzialmente diverse” erano “solo” 55.882.296;<\/li>\n
  3. per ciascuna posizione non ha cercato una soluzione nel numero minimo di mosse, ma solo una in venti mosse (il che \u00e8 molto pi\u00f9 rapido: in problemi combinatori di questo tipo le soluzioni subottimali sono cos\u00ec tante che \u00e8 relativamente facile trovarne una, e tanto non si poteva scendere sotto le venti mosse);<\/li>\n
  4. ha scritto un programmino che in venti secondi risolveva una data posizione;<\/li>\n
  5. ha distribuito il lavoro su tanti PC, e in 35 “anni macchina” hanno trovato una soluzione per ciascuna posizione.<\/li>\n<\/ol>\n

    \u00c8 chiaro che una soluzione di questo tipo \u00e8 fondamentalmente inutile da un punto di vista pratico: un computer con braccia meccaniche sarebbe comunque pi\u00f9 lento di un essere umano molto bravo, che userebbe qualche mossa in pi\u00f9 ma non perde troppo tempo a pensarci su. Ma la teoria vince sempre sulla pratica. Inoltre il gruppo di lavoro ha scoperto qualcosa a prima vista molto strano: le configurazioni “difficili”, quelle cio\u00e8 che non sono risolvibili in 19 mosse o meno, sono relativamente poche. I ricercatori stimano che siano intorno ai 300 milioni, il che significa che data una configurazione a caso la probabilit\u00e0 che sia “difficile” \u00e8 tra uno e dieci su un miliardo. Nel sito cube20.org \u00e8 indicato il numero di combinazioni diverse a seconda del numero di mosse necessario per risolverle, calcolato esattamente fino a 15 mosse e in seguito stimato. Diciamo che se uno dovesse fare una scommessa sarebbe sostanzialmente sicuro che la posizione casuale sia risolvibile in un numero di mosse compreso tra 16 e 19, con un picco a 18. Insomma, non \u00e8 cos\u00ec facile fare troppo disordine! <\/p>\n","protected":false},"excerpt":{"rendered":"

    Il cubo di Rubik pu\u00f2 sermpre essere risolto in al pi\u00f9 venti mosse. Come lo si \u00e8 scoperto? Usando la forza bruta.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2642","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-GC","jetpack-related-posts":[{"id":2658,"url":"https:\/\/xmau.com\/ilpost\/2017\/06\/30\/4-chilometri-cubi-di-rifiuti\/","url_meta":{"origin":2642,"position":0},"title":"4 chilometri cubi di rifiuti","author":".mau.","date":"30\/06\/2017","format":false,"excerpt":"Roberto Zanasi (che abita a Modena) ha trovato questo titolo su un giornale locale, ed \u00e8 metaforicamente balzato sulla sedia. Riuscite a vedere al volo cosa c'\u00e8 di strano nell'affermazione \"Vasco, previsti 4 km cubi di rifiuti\"? No, il problema non sono le battute sulle attuali qualit\u00e0 musicali del cantante\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"4km3","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/2017\/06\/4km3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":561,"url":"https:\/\/xmau.com\/ilpost\/2015\/05\/07\/dai-numeri-immaginari-ai-quaternioni\/","url_meta":{"origin":2642,"position":1},"title":"Dai numeri immaginari ai quaternioni","author":".mau.","date":"07\/05\/2015","format":false,"excerpt":"Una volta che si cambia punto di vista, si possono avere idee che portano a nuovi sviluppi... basta sapere accorgersi di cosa bisogna buttare via. Anche questo \u00e8 il bello dela matematica.","rel":"","context":"In \"analogie\"","block_context":{"text":"analogie","link":"https:\/\/xmau.com\/ilpost\/tag\/analogie\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":580,"url":"https:\/\/xmau.com\/ilpost\/2015\/06\/19\/maturita-2015-luci-e-ombre\/","url_meta":{"origin":2642,"position":2},"title":"Maturit\u00e0 2015, luci e ombre","author":".mau.","date":"19\/06\/2015","format":false,"excerpt":"Ottima l'idea di avere un esempio pratico, meno buona quella di un quesito \"facile\" troppo generico","rel":"","context":"In \"dematematizzazione\"","block_context":{"text":"dematematizzazione","link":"https:\/\/xmau.com\/ilpost\/tag\/dematematizzazione\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":2642,"position":3},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":619,"url":"https:\/\/xmau.com\/ilpost\/2015\/09\/07\/che-cose-il-caso\/","url_meta":{"origin":2642,"position":4},"title":"Che cos’\u00e8 il caso?","author":".mau.","date":"07\/09\/2015","format":false,"excerpt":"Non \u00e8 facile definire cos'\u00e8 una sequenza casuale, perch\u00e9 non possiamo mai essere certi di avere una piena conoscenza di quello che c'\u00e8 dietro di essa.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":194,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/05\/gira-la-carta\/","url_meta":{"origin":2642,"position":5},"title":"Gira la carta","author":".mau.","date":"05\/09\/2011","format":false,"excerpt":"Una specie di gioco di prestigio matematico: l'asso galleggia sempre e si porta all'inizio del mazzetto di carte...","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2642","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2642"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2642\/revisions"}],"predecessor-version":[{"id":2643,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2642\/revisions\/2643"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2642"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2642"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2642"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}