Quesito con la Susi n. 965

Intanto, buon 2020.

E ora che abbiamo sbrigato le formalità, vediamo questo novecentosessantacinquesimo quesito con la Susi.

Gianni porta Susi a conoscere il professore Silenzio. Il professore Silenzio è un teorico dei numeri. Qualcuno dice che in realtà sia la reincarnazione di Ramanujan, anche se lui più che altro cerca di imitare Einstein.

Quando Gianni e Susi entrano, il professore ha già scritto due moltiplicazioni con il loro risultato:

153846×3 = 461538
153846×4 = 615384

Gianni chiede a Susi cosa nota di strano e subito Susi risponde che i numeri sono composti dalle stesse cifre (senza ripetizioni).

“Esiste un altro numero straordinario, formato dalle cifre 1, 2, 4, 5, 7 e 8. Inserendolo a sinistra delle moltiplicazioni che vedi ottieni ogni volta un numero con le stesse cifre.”

......×2 = ......
......×3 = ......
......×4 = ......
......×5 = ......
......×6 = ......

Il solito piacione che è in Gianni pensa bene di lusingarla con una implicita asserzione dell’unicità della sua eccezionale intelligenza:

“Susi, solo tu puoi trovarlo!”

Ma noi sappiamo qualcosa che Gianni e la stessa Susi ignorano: Susi in realtà è un’entità collettiva composta da tanti cervelli indipendenti!

Intanto il professore Silenzio aspetta la risposta, che è quanto gli manca per completare una ricerca che potrebbe portarlo al Nobel. Quale fortuna aver incontrato Gianni e la sua amica!

Ricerca esaustiva

Come potete immaginare è molto facile trovare la soluzione provando tutte le permutazioni di 124578 (che sono 720). Ed è quello che facciamo, con molta poca fantasia, consapevoli del fatto che per un computer provare 720 numeri non è niente.

Lo faccio in Julia.

# uso il pacchetto Combinatorics, che potete installare
# eseguendo
#
# julia> using Pkg
# julia> Pkg.add("Combinatorics")

using Combinatorics

basesym = [1, 2, 4, 5, 7, 8]

function arr_to_num(ns :: Array{Int,1})
    n = 0
    for e in ns
        n = n * 10 + e
    end
    n
end

function num_to_arr(n :: Int)
    a = Int[]
    while n > 0
        c = n % 10
        push!(a, c)
        n = n ÷ 10
    end
    reverse(a)
end

function check_n(n :: Int, i :: Int)
    sort(num_to_arr(n*i)) == basesym
end

for p in permutations(basesym)
    n = arr_to_num(p)
    if all([check_n(n,2),
            check_n(n, 3),
            check_n(n, 4),
            check_n(n, 5),
            check_n(n, 6)])
        println(n)
        break
    end
end

Come accade per altri esempi fatti in questo gioco di risolvere i quesiti della Susi programmando, anche in questo codice c’è ben poco di prettamente julioso: un po’ di sintassi a parte e la possibilità di usare “qualunque” carattere UTF-8, un po’ come in Raku (già Perl6) — potete vedere l’uso di ÷ per la divisione intera, che avrei potuto scrivere anche con div(n, 10) — non c’è molto altro che non si trovi in altri linguaggi. Non sono un esperto di Julia, perciò credo che si possa scrivere meglio… ma non è questo il punto.

Il codice produce il risultato, che è: 142857.

Soluzione manuale

Per la soluzione manuale la prima idea è quella della paziente ricerca… 720 tentativi sono un po’ tanti, ma possiamo ridurli. Intanto notiamo che la prima cifra non può che essere 1, perché in tutti gli altri casi la moltiplicazione per 6 creerebbe un risultato di 7 cifre. Ci rimangono quindi “solo” 120 casi da provare (per le cinque cifre 2, 4, 5, 7, 8).

1.....×2 = 2.....
1.....×3 = 3..... *
1.....×4 = 4.....
1.....×5 = 5.....
1.....×6 = 6..... *

Osservando questi “parziali” però notiamo a destra dei numeri che non possono comparire; il che significa che in quei casi il prodotto della seconda cifra ci deve aver dato un riporto. Il che significa che la seconda cifra non può essere 2 (per colpa di ×3, non di ×6). Dovrà essere una tra 4, 5, 6, 8.

Se fosse 8,

18....×2 = 36.... *
18....×3 = 54....
18....×4 = 72.... *

non ci sarebbe modo di “correggere” la prima cifra con un altro riporto, quindi già la moltiplicazione per 2 ci dice che la seconda cifra non può essere 8.

Proviamo con il 7.

17....×2 = 34.... *

Stesso discorso. E si vede facilmente che lo stesso vale per il 5, visto che otterremmo di nuovo 3 come prima cifra nella moltiplicazione per 2. Non ci resta che il 4.¹

Nel seguente schema ho segnato le righe sicuramente da correggere e i riporti che avremmo se mettessimo come terza cifra quella indicata (% marca la cifra a cui il riporto si va a sommare).

            %       2578
14....×2 = 28....   0111
14....×3 = 42....   0122  
14....×4 = 56.... * 0223
14....×5 = 70.... * 1234
14....×6 = 84....   1344

Ora notiamo che nella ×2 non possiamo avere un riporto di 1, perché altrimenti la seconda cifra diventerebbe 9, e non c’è modo di aggiustare questa situazione a seconda della scelta delle cifre successive. Il che significa l’unica possibilità è il 2.

             %      578
142...×2 = 284...   111
142...×3 = 426... * 122  
142...×4 = 568... * 223
142...×5 = 710... * 234
142...×6 = 852...   344

Ora le cifre che ci rimangono danno sempre un riporto per tutte le moltiplicazioni.

Dal ×2 non abbiamo niente da scartare (il 5 ottenuto sommando il riporto del prodotto per la quarta cifra va sempre bene); anche dal ×3 non ricaviamo subito informazioni visto che tutte e due i riporti “correggono” la cifra sbagliata (il 6 diventa 7 o 8) e non creano danni irreparabili (almeno al primo sguardo).

Ma il 5 va scartato per via del ×6: il riporto farebbe diventare la terza cifra del risultato 5, che già c’è come seconda cifra (la prima e seconda cifra del ×6 adesso sono intoccabile dai riporti, e 5×6=30, quindi avremmo uno 0 che non può generare o incrementare il riporto sulla cifra alla sua sinistra).

Quindi restano il 7 e l’8, che hanno riporti diversi solo per ×4 e ×5.

Guardando il ×5 però vediamo che il 7 darebbe un riporto di 3, che diventa incorreggibile (potrebbe essere corretto se al 5 risultante potessimo aggiungere un riporto maggiore di 4, ma 4 è proprio il massimo riporto che ci resta scegliendo come quinta cifra l’8). Insomma, non ci resta che l’8.

              %     57
1428..×2 = 2856.. * 11
1428..×3 = 4284.. * 12  
1428..×4 = 5712..   22
1428..×5 = 7140.. * 23
1428..×6 = 8568.. * 34

Queste sono tutte situazioni riparabili… Nel caso ×6 la terza cifra del risultato diventerà sicuramente 7, in ×4 la quarta cifra sarà 4, in ×2 la quarta cifra sarà 7.

Ora, la cifra dell’unità non ha nessuna possibilità di essere corretta da un riporto, perciò non può essere 5 (per via di ×2). Quindi l’ultima cifra deve essere 7 e la quinta sarà 5.

Possiamo dedurlo anche dal ×3, visto che il riporto di 2 ottenuto se la quinta cifra fosse 7, ci darebbe un 6 che non sarebbe correggibile da un successivo riporto.²

A posteriori sarebbe stato meglio scartare da subito le cifre che non potevano stare sull’unità… (8, 5, 1, 2, 4)

In ogni caso il risultato ottenuto è 142857, sicuramente corretto (verificabile dal programma scritto in Julia), … ma è corretto anche il ragionamento? Se trovate errori, segnalateli.

Alternative

Può essere pure che non abbia sbagliato nei processi deduttivi che ci hanno portato alla soluzione manuale, però bisogna dire che non è così elegante.

Sono intuitivamente convinto che esista un altro modo. Però dopo averci pensato un po’ non sono arrivato a niente³, per cui per ora ci rinuncio. Se mi verrà in mente qualcosa aggiornerò la pagina.

---

1. Ho iniziato dalla cifra più alta proprio per avere sicuramente riporti. Avrei potuto iniziare dalla prima cifra che ancora dà riporto anche nel ×2 (5…) ed escludere tutte quelle maggiori: avrei risparmiato un po’ di fatica.↩︎

2. Forse non sono stato chiarissimo in tutta l’esposizione dei ragionamenti fatti. Scelto un moltiplicatore, l’unico modo per far propagare un riporto oltre la cifra immediatamente “a sinistra” è far in modo che la somma di questa cifra con il riporto sia maggiore di 9. Per esempio abbiamo un 68., stiamo generando la cifra che andrà a sostituire il punto, e sappiamo che 6 deve cambiare. Quindi il riporto non può essere minore di 2. In generale, se abbiamo 6n. e vogliamo correggere 6, il riporto ottenuto dalla produzione della cifra “punto” non può essere minore di 10 − n. Date le cifre a disposizione e i moltiplicatori che ci interessano, sappiamo che se la cifra n fosse minore di un tot, non sarebbe possibile correggere il 6. Perciò per esempio nel caso ×2 sappiamo di non poter correggere mai oltre la cifra subito a sinistra (cioè il 6 non sarebbe mai correggibile), perché il riporto massimo che abbiamo è 1 e la cifra maggiore su cui sommare il riporto è l’8 (ottenibile dalla cifra 4).↩︎

3. Ho giocato un po’ con l’espansione in potenze di 10; sviluppando a partire da un’espressione del tipo (a × 10² + b × 10¹ + c × 10⁰) × N, manipolando qui, manipolando là…↩︎