backup del Post

Gira la carta

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ù a sinistra avrà 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 è il 10 otterremmo 495XK6827QA3J. Ripetiamo l’operazione fino a quando la carta più a sinistra è l’asso; a questo punto il gioco, che già forse non era così 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à la sua naturale collocazione in cima al mazzetto? Che ne pensate?
La risposta è affermativa: le nostre operazioni termineranno in un numero finito di mosse, e questo è vero qualunque sia la dimensione del mazzetto. Dopo il salto vi spiego il perché.

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!

Innanzitutto, è chiaro che il numero di modi in cui si può ordinare un insieme di n elementi è finito. Magari vi ricordate che è pari a n!, cioè al prodotto dei numeri da 1 a n; ma anche se non ve lo foste ricordati, in questo caso non ci sarebbe stato nulla di tragico. Ripeto, quello che conta è che è un numero finito. In secondo luogo, si danno solo due possibilità 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ò è semplice. L’operazione di rovesciare la sottosuccessione di carte è deteministica: se capita due volte la stessa configurazione, siamo certi che in entrambi i casi eseguendo l’algoritmo si giungerà a una stessa configurazione. Inoltre il numero di possibili configurazioni è finito, per quanto grande esso sia; diciamo che è N. Ma allora tra le prime N+1 configurazioni ottenute applicando ripetutamente l’algoritmo ce ne devono essere due uguali (è 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ò trovare, e che eventualmente si riduce a un solo elemento, è quello che parte dalla prima occorrenza e termina subito prima della seconda.

Eliminata la possibilità 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ì: 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ì siamo sicuri che non si schioderà 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ù di dieci carte.

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à 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, e aspettiamo un momento in cui sia in cima al mazzetto; di per sé potrebbe capitare anche più volte nel ciclo, ma non importa. Che succede dopo aver girato le prime k carte, come da algoritmo? Beh, che la carta k sarà nella posizione k, 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−1, e quindi la carta in posizione k non apparirà più, contrariamente alla nostra ipotesi di partenza. L’unica possibilità è pertanto che k = 1, come volevasi dimostrare.

Per la cronaca, nella dimostrazione ho fatto uso di un concetto dal nome astruso ma dal significato tutto sommato semplice: il monovariante. Mentre l’invariante è 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ò 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…

Il teorema è stato doverosamente dimostrato, ma mi resta ancora un dubbio. Esiste una formula che al variare di n 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 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 è il benvenuto!