Prendete le tredici carte di picche – ma vanno bene anche di un altro seme… – mischiatele e mettetele in una bella fila orizzontale. La carta pi\u00f9 a sinistra avr\u00e0 un certo valore numerico, con l’asso pari a 1 e fante donna e re che valgono rispettivamente 11, 12 e 13. Contate tante carte quante indicate da questa carta, e riposizionatele in ordine inverso: se la successione iniziale fosse ad esempio 6KX594827QA3J dove X \u00e8 il 10 otterremmo 495XK6827QA3J. Ripetiamo l’operazione fino a quando la carta pi\u00f9 a sinistra \u00e8 l’asso; a questo punto il gioco, che gi\u00e0 forse non era cos\u00ec entusiasmante, perde del tutto interesse visto che invertire una carta singola non cambia la disposizione. Ma siamo proprio sicuri che prima o poi l’asso trover\u00e0 la sua naturale collocazione in cima al mazzetto? Che ne pensate?
\nLa risposta \u00e8 affermativa: le nostre operazioni termineranno in un numero finito di mosse, e questo \u00e8 vero qualunque sia la dimensione del mazzetto. Dopo il salto vi spiego il perch\u00e9.<\/p>\n
Prima della dimostrazione vera e propria, occorre fare alcune considerazioni che magari a parecchi di voi saranno ovvie, ma sono comunque necessarie. In fin dei conti, in matematica spesso occorre dimostrare l’ovvio… a meno che non lo si accetti come assioma o postulato, si intende! <\/p>\n
Innanzitutto, \u00e8 chiaro che il numero di modi in cui si pu\u00f2 ordinare un insieme di n<\/i> elementi \u00e8 finito. Magari vi ricordate che \u00e8 pari a n<\/i>!, cio\u00e8 al prodotto dei numeri da 1 a n<\/i>; ma anche se non ve lo foste ricordati, in questo caso non ci sarebbe stato nulla di tragico. Ripeto, quello che conta \u00e8 che \u00e8 un numero finito. In secondo luogo, si danno solo due possibilit\u00e0 per la successione degli ordinamenti che troviamo facendo le operazioni di rovesciamento delle parti del mazzetto; o si entra in un ciclo di una ben definita lunghezza, oppure ci si ferma in una specifica configurazione (che poi, se volete, significa continuare a fare un ciclo di lunghezza 1). La ragione di ci\u00f2 \u00e8 semplice. L’operazione di rovesciare la sottosuccessione di carte \u00e8 deteministica: se capita due volte la stessa configurazione, siamo certi che in entrambi i casi eseguendo l’algoritmo si giunger\u00e0 a una stessa configurazione. Inoltre il numero di possibili configurazioni \u00e8 finito, per quanto grande esso sia; diciamo che \u00e8 N<\/i>. Ma allora tra le prime N<\/i>+1 configurazioni ottenute applicando ripetutamente l’algoritmo ce ne devono essere due uguali (\u00e8 il principio dei cassetti all’opera). Scegliamo allora la (o una a caso, se ce ne sono tante) coppia di configurazioni identiche: il ciclo che si pu\u00f2 trovare, e che eventualmente si riduce a un solo elemento, \u00e8 quello che parte dalla prima occorrenza e termina subito prima della seconda.<\/p>\n
Eliminata la possibilit\u00e0 di continuare a vagare senza meta all’infinito, siamo quasi giunti alla fine dalla nostra dimostrazione. (Come? Se non abbiamo ancora iniziato! Certo, ma spesso le dimostrazioni matematiche sono fatte cos\u00ec: si prepara il terreno tutto intorno, poi si schiaccia l’interruttore e le cose miracolosamente si ricompongono) Ci mancano solo un paio di considerazioni finali. Prendiamo il nostro mazzetto di carte, e supponiamo che il re si trovi per caso nell’ultima posizione. Da l\u00ec siamo sicuri che non si schioder\u00e0 piu: al peggio infatti possiamo avere in cima al mazzetto la donna e scambiare di posto dodici carte, ma la tredicesima rimane fissa al suo posto. Lo stesso capita se le tre figure si trovano agli ultimi tre posti, in qualsiasi ordine relativo: non possiamo infatti girare pi\u00f9 di dieci carte.<\/p>\n
E dopo tutti questi lemmi – il nome tecnico delle considerazioni precedenti – eccoci finalmente alla dimostrazione! Abbiamo detto che a furia di rovesciare l’ordine delle carte prima o poi si giunger\u00e0 a un ciclo, eventualmente di lunghezza 1. Consideriamo tutte le carte che appaiono in prima posizione durante il ciclo, prendiamo quella di valore maggiore k<\/i>, e aspettiamo un momento in cui sia in cima al mazzetto; di per s\u00e9 potrebbe capitare anche pi\u00f9 volte nel ciclo, ma non importa. Che succede dopo aver girato le prime k<\/i> carte, come da algoritmo? Beh, che la carta k<\/i> sar\u00e0 nella posizione k<\/i>, e quelle maggiori nelle posizioni successive, in un ordine non meglio determinato. Ma questo significa che da questo momento in poi potranno trovarsi in cima al mazzetto solamente le carte numerate da 1 a k<\/i>−1, e quindi la carta in posizione k<\/i> non apparir\u00e0 pi\u00f9, contrariamente alla nostra ipotesi di partenza. L’unica possibilit\u00e0 \u00e8 pertanto che k<\/i> = 1, come volevasi dimostrare.<\/p>\n
Per la cronaca, nella dimostrazione ho fatto uso di un concetto dal nome astruso ma dal significato tutto sommato semplice: il monovariante<\/b>. Mentre l’invariante \u00e8 qualcosa il cui valore non cambia mai, come ad esempio la differenza tra il numero di caselle bianche e quelle nere di una scacchiera mutilata se le viene ancora tolto un rettangolo 2×2, il valore del monovariante pu\u00f2 cambiare ma in una sola direzione: insomma ci sono i monovarianti non decrescenti e i monovarianti non crescenti. Come avete visto, anche il monovariante, quando lo si riesce a trovare, aiuta a far trovare la risposta ai problemi…<\/p>\n
Il teorema \u00e8 stato doverosamente dimostrato, ma mi resta ancora un dubbio. Esiste una formula che al variare di n<\/i> dia il massimo numero di mosse che si deve fare prima di ottenere l’1 in prima posizione? Probabilmente un po’ di prove a mano per valori piccoli di n<\/i> seguite da un’occhiata all’OEIS potrebbe dare la risposta, ma ho scritto questo post sul mio palmare senza accesso ai potenti mezzi della tecnica. Se qualcuno si vuole cimentare \u00e8 il benvenuto!<\/p>\n","protected":false},"excerpt":{"rendered":"
Una specie di gioco di prestigio matematico: l’asso galleggia sempre e si porta all’inizio del mazzetto di carte…<\/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":false,"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":[68,26],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-combinatoria","tag-problemi"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-38","jetpack-related-posts":[{"id":2580,"url":"https:\/\/xmau.com\/ilpost\/2013\/03\/27\/ricondursi-al-caso-precedente\/","url_meta":{"origin":194,"position":0},"title":"Ricondursi al caso precedente","author":".mau.","date":"27\/03\/2013","format":false,"excerpt":"Quella del titolo \u00e8 una frase tipica da matematico e fa spesso divertire chi matematico non \u00e8, per\u00f2 \u00e8 uno strumento molto potente quando lo si sa usare.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2464,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/09\/morra\/","url_meta":{"origin":194,"position":1},"title":"Morra","author":".mau.","date":"09\/12\/2011","format":false,"excerpt":"Il gioco della morra, compresa la sua variante \"morra cinese\" che a dire il vero c'entra ben poco con l'originale, nasconde alcune interessanti considerazioni matematiche.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"regole della morra, con lucertola e Spock","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2011\/12\/morra.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":184,"url":"https:\/\/xmau.com\/ilpost\/2010\/11\/13\/il-paradosso-di-penney\/","url_meta":{"origin":194,"position":2},"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":770,"url":"https:\/\/xmau.com\/ilpost\/2016\/05\/09\/ausilii-per-le-moltiplicazioni\/","url_meta":{"origin":194,"position":3},"title":"Ausilii per le moltiplicazioni","author":".mau.","date":"09\/05\/2016","format":false,"excerpt":"Come si facevano le moltiplicazioni senza le calcolatrici? A mano. Ma esistevano degli strumenti appositi per semplificare la vita.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"bastoncini di Nepero (da https:\/\/en.wikipedia.org\/wiki\/File:Bones_of_Napier_%28board_and_rods%29.png )","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2016\/05\/Bones_of_Napier_board_and_rods-300x277.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2640,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/25\/matematica-e-liberta\/","url_meta":{"origin":194,"position":4},"title":"Matematica e libert\u00e0","author":".mau.","date":"25\/09\/2013","format":false,"excerpt":"Non ho certo le capacit\u00e0 di interloquire con il papa emerito sui temi teologici, ma forse su quelli pi\u00f9 prettamente matematici qualcosa posso dire.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":585,"url":"https:\/\/xmau.com\/ilpost\/2015\/06\/25\/rompicapi-piu-matematici\/","url_meta":{"origin":194,"position":5},"title":"Rompicapi pi\u00f9 matematici di quanto sembri","author":".mau.","date":"25\/06\/2015","format":false,"excerpt":"Questi quizzini sono molto pi\u00f9 interessanti dal punto di vista matematico e informatico di quanto possa sembrare a prima vista.","rel":"","context":"In \"funzioni\"","block_context":{"text":"funzioni","link":"https:\/\/xmau.com\/ilpost\/tag\/funzioni\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/194","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=194"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":195,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/194\/revisions\/195"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}