Quizzino della domenica: Divisibilità a cascata

Qual è il numero di dieci cifre tutte diverse abcdefghij tale che sia divisibile per 10, abcdefghi sia divisibile per 9, abcdefgh per 8 e così via fino ad a divisibile per 1?


[abcdefghij]
(trovate un aiutino sul mio sito, alla pagina http://xmau.com/quizzini/p500.html; la risposta verrà postata lì il prossimo mercoledì. Problema pubblicizzato da John Conway, vedi per esempio la rubrica di Alex Bellos.)


8 comments

  1. Intanto complimenti per il quizzino numero 500

    Mi pare che ci siano un paio di refusi: volevi dire “abcdefghi divisibile per 9, abcdefgh divisibile per 8”?

  2. Ci provo, ma è davvero difficile uno per me.

    Sono 10 numeri quindi l’ultimo numero j deve essere 0 e il numero divisibile per 10. Di conseguenza il quinto numero deve avere la lettera e finale ed essere divisibile per 5, quindi il numero abcde deve finire in 5 o 0, ma 0 è già occupato. Quindi e = 5
    I numeri di 2, 4, 6 e 8 cifre devono essere pari, quindi [b d f h] sono i numeri [2 4 6 8] in qualche ordine. Quindi [a c g i] si dividono i numeri [1 3 7 9]

    Il numero abc deve essere divisibile per 3 e abcdef (con e=5) deve essere divisibile per 6, quindi def deve essere anche divisibile per 3. def è un numero d5f con d e f pari e diversi tra loro e ci sono solo 4 possibilità.

    Dato che cd deve essere divisibile per 4, con c dispari, allora d può essere solo 2 o 6 e quindi [2 6]5f divisibile per 6 vuol dire che f è 8 o 4.

    Da qui in avanti sono andato per tentativi perché c’è il fatto che ad un certo punto devo dividere per 7 senza resti, e con un po’ di excel dico che nel numero originale abcdefghij che finisce per 0, la sequenza [b d f h] è una sequenza monotona decrescente, mentre quella [a c e g i] non è una sequenza del tutto monotona crescente, solo dal secondo termine.

    Però mi sono cotto il cervello :-(

  3. Mi accodo a stegal67, e credo di essere giunto allo stesso risultato :-) ecco come l’ho sviluppato:

    Ok, il lato meramente contabile è preponderante rispetto al criterio di calcolo, in questo caso; di buono, c’è che si possono eliminare abbastanza facilmente alcune combinazioni, fin dall’inizio, rendendo inutile dover verificare più di 3 milioni (sarebbero 10!) di combinazioni possibili di cifre diverse.

    Intanto, il criterio di divisibilità per 10 è unico: almeno l’ultima cifra (j) dev’essere 0 (zero), e visto che ce n’è una sola a disposizione la mettiamo da parte.

    Il criterio di divisibilità per 9 è conosciuto, basta che sia divisibile per 9 la somma delle singole cifre, ma visto che a quella posizione (abcdefghi) ci si arriva utilizzando tutte le 9 cifre disponibili (zero escluso, già stabilito prima), si sa che comunque siano disposte quelle cifre andrà bene.

    Arriviamo quindi velocemente dall’altra parte, all’inizio della sequenza: per la prima cifra (a) è banale, divisibile per l’unità lo sono tutte (in teoria anche lo zero, ma già era stato messo da parte quindi non fa parte del gruppo), quindi questo non è utile per ridurre i calcoli.

    La divisibilità per 2 pone un criterio interessante: la cifra b dev’essere pari, quindi può solo essere 2, 4, 6, 8 (zero no, già deciso); ma allora anche per le altre cifre che formano l’unità nei numeri pari (d, f, h) vale il medesimo criterio, e questo già fa comodo, perché di conseguenza nelle posizioni dispari (a, c, e, g, i) ci possono stare solo cifre dispari.

    Cifre dispari sì, ma con criterio: la divisibilità per 5 (e) richiede che ci sia un 5 in quella posizione (ancora una volta, zero non si considera), quindi riepilogando:
    le cifre (a, c, g, i) vanno scelte tra (1, 3, 7, 9);
    le cifre (b, d, f, h) vanno scelte tra (2, 4, 6, 8).

    La prima verifica va fatta sul gruppo abc, che dev’essere divisibile per 3; le combinazioni teoriche sono 48 (4*4*3), ma naturalmente non tutte risultano divisibili, solo una ventina.

    Per ognuna di quelle che soddisfano tale criterio si creano tre ulteriori combinazioni (con le cifre pari ancora disponibili) e si verifica la divisibilità per 4, poi arrivare al 5 è semplice, perché come s’è visto basta accodare solo la cifra 5 alle combinazioni valide per il 4 e se ne ottengono altrettante, in tutto una trentina.

    La divisione per 6 non è complicata, visto che il criterio del numero pari era già stabilito in partenza, e per ogni combinazione da analizzare si sa, per costruzione, che le prime tre cifre sono divisibili per 3, quindi basta che lo siano anche le ultime 3.

    Ci si trova quindi con 18 blocchi di cifre, a cui aggiungere l’una o l’altra delle due sole cifre dispari residue per ottenere 36 numeri di sette cifre divisibili per 7, ma la divisibilità per 7 non si fa facilmente a occhio https://it.wikipedia.org/wiki/Criteri_di_divisibilità (non so se il link va) quindi ho sbrigativamente optato per un foglio di calcolo :-)

    Stavolta riporto anche il risultato, ma avendo sottomano, al momento del calcolo, solo un cordless, quello che avevo trascritto è
    Eu1nkhqbx.
    (sì, scrivendo in rubrica la prima lettera è maiuscola, e per marcare meglio il risultato ogni tasto l’ho premuto il doppio; il puntino finale esce proprio da lì, ma quell’ultima cifra si era già stabilito quale fosse, quindi nessuna sorpresa, anche se si usano tastiere con combinazioni diverse).
    :-)

  4. Mi sembra proprio il problema, forse comparso su Le Scienze, che mi aveva appassionato parecchi anni or sono … direi all’incirca 45.
    Se non ricordo male ci avevo … scatenato ;) la poderosa calcolatrice programmabile Texas Instruments.
    Che divertimento, allora !
    … E un po’ di nostalgia, adesso. :)
    Grazie.

    • direi che è un problema da TI-58 o TI-59 (la TI-57 forse non aveva abbastanza memoria…) ma per buona parte si può procedere a mano!

      • Era una TI-58, e il divertimento era proprio scrivere il programmino.
        Certo avevo escluso quinta e decima cifra … ma non ricordo altro. :|

  5. Mi pare che la risposta sia stata scritta due volte.