Un puzzle di John Horton Conway

Lo scorso aprile il Guardian celebrò nella rubrica Alex Bellos’s monday puzzle il matematico John Horton Conway, scomparso per Covid l’11 aprile. Del geniale matematico inglese venivano ricordati in quell’articolo due puzzle.
Il primo mette alla prova la nostra comprensione di un testo. Rimando alla lettura dell’articolo, per verificare quanto spesso si sia condizionati da assunzioni implicite che portano fuori strada.
Il secondo è invece di logica matematica, ed è abbastanza tosto da risolvere, a meno di ricorrere all’aiuto di un po’ di programmazione.

Il puzzle di Conway

Trovare il numero di 10 cifre, tutte diverse tra loro, abcdefghij, tale che:

a sia divisibile per 1;
ab sia divisibile per 2;
abc sia divisibile per 3;
abcd sia divisibile per 4;
abcde sia divisibile per 5;
abcdef sia divisibile per 6;
abcdefg sia divisibile per 7;
abcdefgh sia divisibile per 8;
abcdefghi sia divisibile per 9;
abcdefghij sia divisibile per 10.

Vale la pena di ricordare anche un’altra delle incredibili eredità del genio di John Horton Conway: il gioco Life, trattato sempre qui su Inchiostro Virtuale, in un altro articolo.

Come si può risolvere il puzzle di Conway

Ci sono essenzialmente tre strade per risolvere il puzzle:

usare carta, penna e neuroni;
affidarsi completamente a un algoritmo computerizzato;
utilizzare un po’ di logica preliminare, per semplificare e velocizzare l’algoritmo computerizzato.

Per i dettagli sulla prima soluzione rimando al citato articolo di Alex Bellos. Al fondo c’è un link che rimanda a un secondo articolo contenente la soluzione di entrambi i puzzle proposti.

Il programma per la seconda soluzione si articolerebbe così:

generare tutti i possibili numeri abcdefghij come permutazioni delle cifre da 0 a 9; sono 10! = 3.628.800 differenti permutazioni, nemmeno tante; in realtà si potrebbe eliminare un decimo delle permutazioni, quelle che cominciano con la cifra 0;
per ogni permutazione verificare se il numero soddisfa le 10 condizioni di divisibilità;
stampare le combinazioni che dovessero superare la verifica.

Ovviamente non c’è confronto tra la soddisfazione raggiungibile con il primo approccio e quella, decisamente più ridotta, del secondo. Ma c’è una terza via.

Un po’ di logica preliminare per il puzzle di Conway

Se si guarda alle condizioni di divisibilità, si può individuare subito qualcosa al riguardo del valore delle cifre a … j:

la cifra finale j deve essere 0, poiché abcdefghij è divisibile per 10;
la cifra e deve valere 5, poiché abcde è divisibile per 5, e lo 0, unica altro valore possibile per e, è già assegnato a j;
le cifre b, d, f, h devono essere pari, quindi a loro vanno assegnate, in qualche ordine da determinare, le cifre 2, 4, 6 e 8 (lo 0 è già stato assegnato a j);
rimangono le quattro cifre a, c, g, i, per le quali rimangono le cifre 1, 3, 7, 9.

Resta un dubbio sulla cifra a: dal testo del puzzle si potrebbe dedurre che, poiché viene rimarcato che è divisibile per 1, la cifra sia un numero primo, il che porterebbe a escludere per a il valore 9; nel dubbio, lascio tutti e quattro i valori 1, 3, 7, 9 anche per a.

Queste semplici informazioni consentono di ridurre a 4! x 4! = 24² = 576 le combinazioni da esplorare.

Per pura pigrizia di programmazione, ho rinunciato ad escludere le combinazioni con cifre ripetute – il programma così viene più semplice da scrivere – e quindi le combinazioni esplorate diventano 4⁴ x 4⁴ = 65.536 (sempre meno di 3.628.800, no?).

Qualche statistica, già che ci siamo

Quando si risolve un problema via algoritmo computerizzato, si ha la possibilità, praticamente agratis, di raccogliere strada facendo qualche statistica, che ci può far scoprire qualcosa in più sulla natura del puzzle.

Nel caso del puzzle di Conway, mi sono venute in mente due cose:

la più banale, contare le combinazioni analizzate, per verificare che tornassero con la previsione di 65.536;
verificare se esistono altre combinazioni che superano le condizioni di divisibilità, ma con cifre ripetute, quindi senza utilizzare tutte e 9 le cifre.

La seconda, tutto sommato, dà un alibi alla mia pigrizia.

Il programma che risolve il puzzle di Conway

L’ho scritto in Ruby, appena installato sul Mac Book Air che mi sono regalato di recente. Ma di questo scriverò magari in un altro articolo.
Ecco il cuore del programma:

$conta_n = 0
$cifre_diff = Hash.new(0)
[2,4,6,8].each do |b|
    [2,4,6,8].each do |d|
        [2,4,6,8].each do |f|
            [2,4,6,8].each do |h|
                [5].each do |e|
                    [0].each do |j|
                        [1,3,7,9].each do |a|
                            [1,3,7,9].each do |c|
                                [1,3,7,9].each do |g|
                                    [1,3,7,9].each do |i|
                                        $trovato = true
                                        $conta_n += 1
                                        $n = 100*a + 10*b + c
                                        if $n % 3 != 0 then $trovato = false end
                                        $n = 10*$n + d
                                        if $n % 4 != 0 then $trovato = false end
                                        $n = 100*$n + 10*e + f
                                        if $n % 6 != 0 then $trovato = false end
                                        $n = 10*$n + g
                                        if $n % 7 != 0 then $trovato = false end
                                        $n = 10*$n + h
                                        if $n % 8 != 0 then $trovato = false end
                                        $n = 10*$n + i
                                        if $n % 9 != 0 then $trovato = false end
                                        $n = 10*$n + j
                                        $cifre_n = [a,b,c,d,e,f,g,h,i,j]
                                    end
                                    if $trovato == true then
                                        if $cifre_n.uniq.count == 10 then print "==>" end
                                        print "\t", $n, " con ",$cifre_n.uniq.count, " cifre diverse\n"
                                        $cifre_diff[$cifre_n.uniq.count] += 1
                                    end
                                 end
                             end
                          end
                    end
                end
            end
        end
    end
end
print "\nEsaminate ",$conta_n, " combinazioni. "
print "Soluzioni per ok divisibilità e differente numero di cifre:"
print "\n", $cifre_diff, "\n\n"

Il risultato

Ecco cosa tira fuori il programma (la soluzione è quella evidenziata con il segno “==>”):

	1292529690 con 6 cifre diverse
	1296547290 con 8 cifre diverse
	3216549690 con 8 cifre diverse
	7412587290 con 8 cifre diverse
	3632587290 con 8 cifre diverse
	1892527290 con 7 cifre diverse
	3812529690 con 8 cifre diverse
==>	3816547290 con 10 cifre diverse

Esaminate 65536 combinazioni. Soluzioni per ok divisibilità e differente numero di cifre:
{6=>1, 8=>5, 7=>1, 10=>1}

Quindi:

la soluzione del puzzle è 3.816.547.290, provare per credere;
sono state esaminate effettivamente 65.536 combinazioni;
ci sono ulteriori soluzioni al puzzle, se si accetta di avere ripetizione di cifre;
quella che utilizza meno cifre diverse tra loro è 1.292.529.690, in cui mancano le cifre 3, 4, 7, 8.

Decisamente più complesso è, invece, risolvere il puzzle di Conway senza appoggiarsi a strumenti di calcolo, ma solo con passaggi logici (vedi articolo di Alex Bellos). E se è difficile risolverlo, allora solo un genio poteva concepirlo. Il genio di John Conway.

L’immagine di apertura è di Gerd Altmann, da Pixabay.