La soluzione completa del problema (come credo
sarà evidente alla fine della risposta) è tutt’altro che
breve e banale. Preferirei quindi suggerire un po’ di strategie per
affrontarlo, lasciando al lettore interessato il compito di
dedicare ai dettagli tutto il tempo che questi richiedono. A tale scopo,
propongo di studiare la situazione in un modo un po’ più generale:
consideriamo un’estrazione di 6 numeri su n e chiediamoci quante
sestine dobbiamo giocare per avere la sicurezza di indovinare almeno un
terno della sestina estratta. La generalizzazione è quindi
davvero minima, dato che consiste nel rimpiazzare il numero 20 della
domanda con un numero intero qualsiasi.
I possibili terni
che si possono realizzare con n numeri sono
n (n – 1) (n – 2) / 6.
Ogni sestina, d’altra parte, contiene 6
54 / 6 = 20 terni, per cui se
riuscissimo a realizzare la situazione ideale in cui ogni terno
viene giocato una sola volta ci sarebbero sufficienti
n (n – 1) (n – 2) / 120
giocate. Perché esista una soluzione ottima a questo problema,
allora, la formula appena vista deve dare un risultato intero; in
effetti, nel caso proposto dal lettore con n = 20,
tale numero è intero e pari a 57.
In realtà,
però, ci si può rendere conto che giocare tutti i
terni è inutile: per essere sicuri di indovinare
almeno un terno nella sestina estratta è in effetti sufficiente
giocare solo i terni che si possono realizzare con numeri da 1 a
n – 3 (perchè la sestina estratta non può
contenere più di tre numeri maggiori di
n – 2). Per capire quante giocate potrebbero essere
sufficienti nel caso di esistenza di una soluzione “ideale”, allora,
basta sostituire n – 3 al posto di n nelle
formule precedenti: anche nel caso n=17, in effetti, la formula
per il numero delle giocate minime dà il valore 34, che è
intero. Sembrerebbe quindi che il problema posto dal lettore
possa avere una soluzione “ideale”; in realtà uno studio
più approfondito dimostra che questo non è vero.
Consideriamo
infatti tutti i terni che contengono un certo numero fissato (per
esempio il numero 1): tali terni sono esattamente
(n – 1) (n – 2) / 2,
e d’altra parte ogni giocata in cui il numero 1 compare “copre” 54 / 2 = 10 terni che
lo contengono. Nella situazione ideale in cui ogni terno viene giocato
esattamente una volta, allora, ogni elemento dovrebbe comparire
esattamente in
(n – 1) (n – 2) / 20
insiemi e quindi anche questo numero deve essere intero. In
particolare, dal momento che i numeri (n – 1) e
(n – 2) sono uno pari e l’altro dispari, ci sono
soltanto due possibilità: o uno dei due è multiplo di 20,
oppure uno dei due è multiplo di 5 e l’altro è multiplo
di 4. Invece di esaminare subito le conseguenze di questa proprietà,
ripetiamo un ragionamento analogo per tutti i terni che contengono
due numeri fissati (per esempio, 1 e 2): tali terni sono
esattamente (n – 2) e ogni insieme in cui compaiono i
numeri 1 e 2 gioca 4 di tali terni. In particolare, allora,
(n – 2) deve essere multiplo di 4 e cioè
n deve essere multiplo di 2 ma non di 4.
Combinando tutti
gli elementi in nostro possesso è possibile capire allora che
n deve essere pari e tale che (n – 2) sia
multiplo di 4; inoltre (dato che (n – 1) (n – 2)
deve essere multiplo di 20), o (n – 2) è
multiplo di 20 oppure (n – 1) è multiplo di 5.
I numeri per cui (n – 2) è multiplo di 20 sono
evidentemente 22, 42, 62, … mentre i numeri per cui
(n – 1) è dispari e multiplo di 5 e
(n – 2) è multiplo di 4 sono esattamente 6, 26,
46, 66, … . In altre parole, una soluzione ottimale può
esistere solo se si sta eseguendo un’estrazione da un’urna che
contiene n numeri con n appartenente all’insieme
{6, 22, 26, 42, 46, …}.
Osserviamo ancora
che tale condizione è necessaria ma non è affatto
detto che sia anche sufficiente: potrebbe essere possibile, per
esempio, che la soluzione ottima esista solo nel caso banale n 6,
oppure che esista solo per alcuni elementi di quell’insieme e non per
altri. Si potrebbero considerare anche alcune proprietà che
devono essere soddisfatte dalle sestine che fanno parte di un “sistema”
ottimo (per esempio, due giocate diverse non possono mai avere più
di due numeri in comune, perché altrimenti almeno un terno verrebbe
giocato due volte): tali proprietà potrebbero permettere di
escludere l’esistenza di una soluzione ottima anche per altri valori di
n. Per dimostrare l’esistenza di una soluzione ottima si
potrebbe invece (con un po’ di attitudine alla programmazione) cercare,
per esempio, di istruire un calcolatore a attuare un metodo simile al
“crivello di Eratostene” per determinare i numeri primi: si decide la
prima giocata e si cancellano tutti i terni che essa contiene, poi si
decide la seconda e si eliminano tutti i terni che essa contiene e
così via. Va da sé che questo algoritmo non è
necessariamente il più semplice e che, a meno che non si trovino
condizioni “intelligenti” per la generazione delle giocate, non dà
nemmeno garanzie di essere corretto: lascerei comunque al lettore il
compito di trovare un algoritmo a questo scopo.
In ogni caso, il
problema posto dal lettore non ammette una soluzione ideale. Va anche
detto d’altra parte che (dato che il numero di terni possibili, per
quanto grande, è pur sempre finito) deve esistere un qualche
numero di sestine che contiene tutti i possibili terni. Trovare tale
numero per via teorica è tuttavia tanto complicato da essere
meno conveniente, dal punto di vista del tempo impiegato, rispetto al
procedimento “per tentativi” ma ciò che abbiamo osservato fin qui
ci permette però lo stesso di dire qualcosa. Da un lato, infatti,
le giocate dovranno essere almeno 34 (cioè il numero “teorico” di
giocate nella situazione ottima); dall’altro, se esistesse un sistema
ottimo per giocare tutti i terni che si possono comporre con più
di 17 numeri, si potrebbe usare lo stesso sistema (sostituendo qualsiasi
altro numero ai numeri più grandi di 17) per giocare anche tutti
i terni che ci interessano. Se insomma si riesce a dimostrare
che 77 sestine sono effettivamente sufficienti per giocare tutti i
terni che si possono comporre con 22 numeri (che è il più
piccolo numero maggiore di 17 contenuto nell’elenco dei numeri “buoni”)
abbiamo evidentemente anche la garanzia che non ci saranno necessarie
più di 77 giocate.