Visualizza il feed RSS

Titolo provvisorio...

Un (altro) problemino con le addizioni... in compagnia della Susi.

Valuta questo inserimento
di pubblicato il 02-01-2020 alle 13:58 (334 Visite)
Parliamo nuovamente di partizioni di numeri naturali, uno degli argomenti più seguiti e richiesti del presente blog. Lo facciamo, per questa volta, in compagnia del simpatico personaggio della Settimana Enigmistica che propone indovinelli per uno dei più noti e longevi concorsi a premi dell'amata rivista: il "quesito della Susi". Per l'esattezza, si tratta del 964° quesito, pubblicato sulla rivista N° 4577 del 12 dicembre 2019 come 4513° concorso settimanale.

Nelle vignette che presentano il quesito compaiono quattro serie di carte disposte in modo da formare una somma incolonnata di tre addendi, i cui dorsi sono ordinatamente contraddistinti dai seguenti simboli:

Formula LaTeX: \begin{align*} a\ b\ c\ &+ \\ c\ a\ b\ &+ \\ b\ c\ a\ &= \\ \hline ?\ ?\ ?\ ?\ & \end{align*}

Uno dei protagonisti dice a Susi: "Dietro le carte con la stessa lettera è scritta la stessa cifra, e i numeri di tre cifre, sommati, ne danno uno di quattro cifre celato sotto le carte col punto interrogativo.". Susi chiede allora "E qual è la somma totale?". Risposta: "Devi dirmela tu, Susi. Ti dico solo che le quattro cifre che la compongono sono tutte diverse tra loro.".
La spalla recita testualmente: "Nove carte nascondono una somma che sembra messa lì apposta per Susi. Riuscirà, con le poche informazioni, a superare questa nuova sfida? Col vostro aiuto, naturalmente.
Che numero di quattro cifre è celato sotto le quattro carte?"

Risulta immediato rilevare che le lettere a, b, c così disposte formano un quadrato latino: in particolare, uno dei dodici possibili di ordine tre. Tra le meravigliose caratteristiche di queste matrici c'è anche quella di avere somma costante per colonne (e per righe): in questo caso, la costante è s = a + b + c. Ne consegue che il valore della somma dei tre numeri, ricordando dalle scuole elementari come si addizionano i numeretti in colonna per unità, decine, centinaia etc. , sarà dato da 100s + 10s + s. Raccogliendo i termini omogenei, si ha quindi in definitiva che la somma dei tre numeri di tre cifre incogniti è pari a:

Formula LaTeX: (100+10+1)\cdot s = 111\cdot s = 111\cdot(a+b+c)

Il problema si riduce quindi a cercare tra alcuni multipli a quattro cifre di 111 quello composto da tutte cifre distinte. Tali multipli saranno generati da un moltiplicatore s compreso tra 11 (inutile cercare cifre distinte nel risultato di 111*10... ) e rispettivamente 24 e 27, secondo che vogliamo considerare a, b e c necessariamente distinti o meno (il testo non lo specifica in modo chiaro ed esplicito, ricorre solo alla classica formula enigmistica "a simbolo uguale corrisponde numero uguale"). Si tratta quindi di effettuare una manciatina di operazioni elementari alla ricerca di un numero (l'unico in quell'intervallo con le caratteristiche desiderate), per scoprire banalmente che:

Formula LaTeX: 2109\ =\111\cdot 19

Ovviamente fino qui non abbiamo neppure messo mano al computer. Il fatto è che la somma delle cifre desiderata, pari a 19, si può ottenere banalmente assegnando in vari modi diversi i valori nell'intervallo naturale [0, 9] ad a, b e c. In altri termini, non è univoco il modo per ottenere quel totale di 2109. Ecco allora che le partizioni entrano prepotentemente in gioco nel momento in cui una buona mente matematica cerca di rispondere alla domanda: in quanti modi è possibile assegnare le singole cifre tra 0 e 9 ad a, b e c per comporre quella costante 19 e ottenere l'agognata somma?
Per togliersi al volo la curiosità prima di andare a studiare uno di questi testi, niente di meglio che implementare uno degli algoritmi più belli ed efficienti per la generazione di partizioni vincolate, introdotto dal venerabile Knuth nell'arcinoto e mai troppo celebrato TAoCP, volume 4: l'algoritmo H, in questo caso "analogo con modifica" per limitarsi alle partizioni con esattamente 3 elementi e valore massimo pari a 9.

codice:
/* Implementazione dell'algoritmo H di Knuth: "partition n into m parts". */

#include <stdio.h>
#include <stdlib.h>

void GenParts(unsigned n, unsigned m, unsigned u)
{
    unsigned j, s, x;
    unsigned a[16];

    /* [Initialize.] */
H1:
    a[1] = n -m +1;
    a[m+1] = m -1;
    for (j = 2; j < m +1; ++j) {
        a[j] = 1;
    }

    /* [Visit.] */
H2:
    if (a[1] <= u) {
        printf("%d ", a[1]);
        for (j = 2; j < m +1; ++j) {
            printf("+ %d ", a[j]);
        }
        puts("");
    }

    if (a[2] > (a[1] - 2)) {
        goto H4;
    }

    /* [Tweak a[1] and a[2].] */
H3:
    a[1] -= 1;
    a[2] += 1;
    goto H2;

    /* [Find j.] */
H4:
    j = 3;
    s = a[1] + a[2] -1;
    while (a[j] > (a[1] -2)) {
        s += a[j];
        ++j;
    }


    /* [Increase a.] */
H5:
    if (j > m) {
        return;
    } else {
        x = a[j] +1;
        a[j] = x;
        --j;
    }

    /* [Tweak a[1]...a[j].] */
H6:
    while (j > 1) {
        a[j] = x;
        s -= x;
        --j;
    }
    a[1] = s;
    goto H2;
}

#ifdef TEST
int main()
{
    GenParts(19, 3, 9);
}
#endif
/* EOF: Hpart.c */
La banalissima modifica introdotta consiste nell'uso di un terzo parametro e nell'implementazione di un late filtering per visualizzare le sole partizioni la cui parte massima è non superiore a 9, come da vincoli del problema.
Una volta generata ciascuna partizione in formato standard (lessicografico decrescente), vi sono poi per ognuna sei distinti modi di assegnare i valori ad a, b e c, il tutto lasciando a margine la questione dell'unicità delle parti (a, b e c devono essere diversi tra di loro?). Tale semplice lavoro, assieme al codice per la ricerca del multiplo di 111 a cifre distinte nell'intervallo stabilito, è lasciato come banale e divertente esercizio per il lettore (chiaramente usando un array di booleani per il controllo di unicità del multiplo a 4 cifre).