{"id":2499,"date":"2012-05-04T03:30:28","date_gmt":"2012-05-04T01:30:28","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2499"},"modified":"2022-10-11T10:45:56","modified_gmt":"2022-10-11T08:45:56","slug":"grandi-numeri","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2012\/05\/04\/grandi-numeri\/","title":{"rendered":"Grandi numeri"},"content":{"rendered":"

La scorsa settimana ho postato sul mio blog uno dei miei soliti quizzini della domenica<\/a>, il cui testo mi era stato inviato da Marcello Semboli<\/a>. Una cassaforte si apre infilando tre schede nelle rispettive serrature. Le schede esternamente sono identiche: quando vengono infilate tutte e tre, quelle messe nella posizione sbagliata chiudono la loro serratura mentre quelle nella posizione giusta ne cambiano lo stato: da aperta a chiusa e viceversa. Noi non possiamo conoscere lo stato delle singole serrature, a meno che non siano tutte aperte e quindi la cassaforte si apra. Stamattina per\u00f2 qualcuno ha giocato con le chiavi: la cassaforte \u00e8 chiusa e le tre chiavi sono sul tavolo, non si sa in che ordine. \u00c8 possibile trovare una successione di mosse che apra la cassaforte?<\/p>\n

La risposta \u00e8 s\u00ec, e potete andare a leggere qua<\/a> qual \u00e8 la successione di mosse necessaria. A me ci \u00e8 voluta una pausa pranzo per risolverlo, your mileage may vary. Ma io, da buon matematico, una volta risolto il problema ho subito pensato alle possibili generalizzazioni: avere N serrature e non solo tre, e avere schede che quando non sono inserite al posto giusto non fanno nulla invece che chiudere la serratura. L’idea di questa seconda generalizzazione nasce vedendo che nella mia dimostrazione avevo sfruttato il fatto che una scheda sbagliata chiude la serratura. Un po’ di studio mi ha fatto trovare una soluzione in entrambi i casi. Il caso con una singola serratura \u00e8 banale; ma anche quello con due lo \u00e8 perch\u00e9 le schede o sono inserite entrambe giuste o entrambe sbagliate, e quindi basta metterle prima in un ordine e poi nell’altro per aprire la cassaforte. No, non \u00e8 l’inizio di una dimostrazione per induzione, non preoccupatevi.<\/p>\n

Nel caso di N serrature con le schede sbagliate che chiudono la loro serratura, numeriamole a 1 a N, e iniziamo a testare se per caso la combinazione corretta sia 1,2,…,N. Per fare ci\u00f2, iniziamo con la combinazione sicuramente sbagliata 2,3,…,N,1, che nella nostra ipotesi chiude tutte le serrature, e poi continuiamo con 1,2,…N. Se la cassaforte non si apre, vuol dire che la nostra ipotesi era errata, e ne proviamo un’altra. Visto che in totale ci sono N! permutazioni dei numeri da 1 a N, ci occorreranno al massimo 2N! tentativi. Uun bel numero, visto che cresce pi\u00f9 che esponenzialmente con N; ma nel secondo caso si fa ben di peggio.<\/p>\n

Supponiamo infatti di avere sempre N serrature, ma dove stavolta le chiavi sbagliate non fanno nulla. Anche in questo caso iniziamo a testare se la combinazione corretta \u00e8 1,2,…,N. Lo stato iniziale delle serrature sar\u00e0 XXX…X, dove X pu\u00f2 essere “aperto” o “chiuso”; ogni X, se si infila la scheda giusta, diventer\u00e0 lo stato opposto Y. Nella nostra ipotesi, lo stato con tutte le serrature aperte sar\u00e0 dato da una combinazione di X e Y: noi possiamo cambiare lo stato di una singola serratura, lasciando la scheda presunta corretta in quella posizione e ruotando le altre. Per esempio, 2,3,…,N−1,1,N cambia lo stato dell’ultima serratura. \u00c8 possibile ottenere tutte le 2N<\/sup> combinazioni di X e Y in esattamente 2N<\/sup> passi in cui si cambia un solo simbolo per volta: cercate “Codice Gray” per ulteriori informazioni, o aspettate che io mi decida a scriverne. Finito tutto il giro, se la cassaforte non si \u00e8 aperta possiamo essere certi che 1,2,…,N non \u00e8 la permutazione giusta: ne abbiamo solo altre N!−1 da provare…<\/p>\n

In questo caso l’algoritmo funziona, ma \u00e8 ancora pi\u00f9 lento, richiedendo 2N<\/sup>×N! passi per essere certi di aprire la cassaforte. Per dare un’idea, con 10 serrature potrebbero occorrere quasi 4 miliardi di tentativi e con 20 serrature ce ne vorrebbero circa 2,5×1024<\/sup>. Indubbiamente la fiamma ossidrica inizia ad avere una sua bella convenienza… Ma un matematico, oltre a non essere molto bravo con la fiamma ossidrica, non si \u00e8 mai curato se un numero \u00e9 grande o piccolo quando dimostra un teorema di esistenza. Il record di numero minimo lo si cercher\u00e0 poi di fare in seguito.<\/p>\n

L’esempio pi\u00f9 famoso di grande numero usato in matematica \u00e8 il numero di Skewes<\/a>. Un minimo di storia: per approssimare il conteggio dei numeri primi inferiori a un numero dato, che si indica con la funzione π(n), Gauss invent\u00f2 una funzione, il logaritmo integrale, che si indica con Li(n). Sembrerebbe che Li(n) sia sempre maggiore di π(n), e anzi la differenza tra i due valori cresce al crescere di n; ma nel 1914 il matematico britannico John Littlewood dimostr\u00f2 che non era cos\u00ec, e le due funzioni continuavano a rincorrersi, passando in testa infinite volte ciascuna. Restava da capire quando avveniva il primo sorpasso, e qui entra in gioco il matematico sudafricano Samuel Skewes.<\/p>\n

Innanzitutto Skewes suppose vera l’ipotesi di Riemann, e quindi che la distribuzione dei numeri primi fosse il meno irregolare possibile: in quel caso nel 1933 dimostr\u00f2 che il sorpasso avviene prima di un numero S1<\/sub>, il primo numero di Skewes<\/b>, pari a eee79<\/sup><\/sup><\/sup>, un numero che non saprei nemmeno come scrivere in altro modo. Non pago di questo numerone, nel 1955 riusc\u00ec a trovare un limite superiore anche nel caso non valga l’ipotesi di Riemann. Questo nuovo limite S2<\/sub>, il secondo numero di Skewes<\/b>, \u00e8 pari a 1010101000<\/sup><\/sup><\/sup> e fa sembrare il precedente numero di Skewes un nanerottolo…<\/p>\n

Per la cronaca, il primo sorpasso avviene molto prima di questi valori: al momento si suppone che sia intorno a 1,37×10316<\/sup>. Non che questo sia un numero “piccolo”, intendiamoci: l’universo contiene un numero di particelle elementari molto, molto inferiore. Insomma nella pratica il logaritmo integrale sar\u00e0 sempre maggiore di π(n); ma quando mai un matematico \u00e8 preoccupato dalla pratica?<\/p>\n","protected":false},"excerpt":{"rendered":"

Quando un matematico cerca una dimostrazione di esistenza non si lascia mica intimorire dalla grandezza dei numeri che ottiene!<\/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-2499","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-Ej","jetpack-related-posts":[{"id":2642,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/07\/il-numero-di-dio\/","url_meta":{"origin":2499,"position":0},"title":"Il Numero di Dio","author":".mau.","date":"07\/10\/2013","format":false,"excerpt":"Il cubo di Rubik pu\u00f2 sermpre essere risolto in al pi\u00f9 venti mosse. Come lo si \u00e8 scoperto? Usando la forza bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"un cubo di Rubik","src":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/a\/a6\/Rubik%27s_cube.svg\/200px-Rubik%27s_cube.svg.png","width":350,"height":200},"classes":[]},{"id":194,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/05\/gira-la-carta\/","url_meta":{"origin":2499,"position":1},"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":[]},{"id":616,"url":"https:\/\/xmau.com\/ilpost\/2015\/08\/12\/cioccolatisti-morigerati\/","url_meta":{"origin":2499,"position":2},"title":"Cioccolatisti morigerati","author":".mau.","date":"12\/08\/2015","format":false,"excerpt":"Un gioco per cui si pu\u00f2 trovare una strategia vincente senza eccessiva fatica.","rel":"","context":"In \"induzione\"","block_context":{"text":"induzione","link":"https:\/\/xmau.com\/ilpost\/tag\/induzione\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":184,"url":"https:\/\/xmau.com\/ilpost\/2010\/11\/13\/il-paradosso-di-penney\/","url_meta":{"origin":2499,"position":3},"title":"Il paradosso di Penney","author":".mau.","date":"13\/11\/2010","format":false,"excerpt":"In generale nei giochi a due persone \u00e8 chi fa la prima mossa a essere avvantaggiato; ma ci sono alcuni casi in cui \u00e8 meglio giocare per secondo, soprattutto se puoi conoscere in anticipo la prima mossa dell'avversario. E questo vale anche se si lancia una moneta!","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[con che probabilit\u00e0 vince il secondo giocatore?]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2010\/11\/penney-prob.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":602,"url":"https:\/\/xmau.com\/ilpost\/2015\/08\/15\/quizzini-per-ferragosto-2015\/","url_meta":{"origin":2499,"position":4},"title":"Quizzini per Ferragosto 2015","author":".mau.","date":"15\/08\/2015","format":false,"excerpt":"Questa volta i quizzini sono tratti dal libro 100 Math Brainteasers di Zbigniew Romanowicz e Bartholomew Dyda, e garantisco che sono tutti facilissimi (tanto che ne ho complicato leggermente qualcuno...) Come sempre, le soluzioni appariranno la settimana prossima. 1. Moltiplicate i puntini Nel disegno qui sotto vedete una moltiplicazione fatta\u2026","rel":"","context":"In \"quizzini\"","block_context":{"text":"quizzini","link":"https:\/\/xmau.com\/ilpost\/tag\/quizzini\/"},"img":{"alt_text":"[63a \u00d7 b = 2?32]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/08\/q1-300x232.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2428,"url":"https:\/\/xmau.com\/ilpost\/2011\/08\/09\/il-paradosso-di-ross-littlewood\/","url_meta":{"origin":2499,"position":5},"title":"Il paradosso di Ross-Littlewood","author":".mau.","date":"09\/08\/2011","format":false,"excerpt":"L'infinito \u00e8 una brutta bestia, su questo credo siano in molti a essere d'accordo. Ma se si immagina di compiere un numero infinito di azioni in un tempo finito, i paradossi aumentano ancora!","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2499","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=2499"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2499\/revisions"}],"predecessor-version":[{"id":2500,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2499\/revisions\/2500"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2499"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2499"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2499"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}