Un Pitone nel labirinto: terza fitta

english

Continuiamo la soluzione del problema dal post precedente.

Dal momento che ONE + ONE = TWO possiamo sperare di vincolare i possibili valori di N ai valori di W in qualche modo. Per cominciare diciamo che a causa della colonna più a destra quando E>4 allora W è dispari per via del riporto, mentre W è pari quando E<5

 1
ONE +
ONE =    quando E è maggiore di 4
-----
TWO

 0
ONE +
ONE =    quando E è minore di 5
-----
TWO

Per dirlo con una tabella:

E W
1 even (0,2,4,6,8)
6 odd (1,3,5,7,9)
2 even (0,2,4,6,8)
7 odd (1,3,5,7,9)

Similmente, c’è una relazione dello stesso genere che lega T e N: se T è dispari allora vuol dire che deve esserci un riporto dalla colonna vicina, per cui N>4, mentre se T è pari allora N<5

1
ONE +
ONE =    quando N è maggiore di 4
-----
TWO

0
ONE +
ONE =    quando N è minore di 5
-----
TWO

In tabella

T N
4 (0,1,2,3,4)
5 (5,6,7,8,9)
8 (0,1,2,3,4)
9 (5,6,7,8,9)

Da notare che ci sono ancora conflitti: questi verranno risolti quando infileremo queste minitabelle nella tabella principale che stiamo costruendo, fra un minuto. Quando W è pari (nessun riporto da E + E) la cifra più a destra di N + N è W (quando W è dispari dobbiamo diminuirlo di 1 naturalmente). Un argomento simile può essere ripetuto per l’ultima tabella. Dal momento che sappiamo che R = 0* possiamo ignorare i casi in cui uno tra W e N è 0, o quelli dove W = N. Ciò ci porta alla tabella

W N
2 1
2 6
4 2
4 7
6 3
6 8
8 4
8 9
1 5
3 1
3 6
5 2
5 7
7 3
7 8
9 4

Se dovessimo inserire questa tabella – che è piuttosto lunga – nella tabella principale, la renderemmo troppo grande perché possa essere gestita a mano; oppure no, dipende da quanto si è pigri: di sicuro lo è per me, per cui dobbiamo trovare qualche trucco abbastanza furbo. La seguente tabella potrebbe essere un punto di partenza, aggiungiamo una colonna per elencare i possibili valori di W

R O T I E W avanzi (incluso W)
0 2 4 5 1 pari (2,4,6,8) 36789
0 2 4 5 6 dispari (1,3,5,7,9) 13789
0 2 5 4 1 pari (2,4,6,8) 36789
0 2 5 4 6 dispari (1,3,5,7,9) 13789
0 4 8 9 2 pari (2,4,6,8) 13567
0 4 8 9 7 dispari (1,3,5,7,9) 12356
0 4 9 8 2 pari (2,4,6,8) 13567
0 4 9 8 7 dispari (1,3,5,7,9) 12356

Adesso dobbiamo escludere i valori di W che vanno in conflitto con le altre lettere, per esempio nella prima riga abbiamo

R O T I E W avanzi (incluso W)
0 2 4 5 1 pari (2,4,6,8) 36789

W non può avere valore 2 o 4, per cui

R O T I E W avanzi (incluso W)
0 2 4 5 1 pari (6,8) 36789

Ora aggiungiamo una colonna per la N a partire dai valori elencati per W

R O T I E W N avanzi (inclusi W e N)
0 2 4 5 1 pari (6,8) (3,8;4,9) 36789

Escludiamo i conflitti anche da questa tabella

R O T I E W N avanzi (inclusi W e N)
0 2 4 5 1 pari (6,8) (3,8;9) 36789

Allora otteniamo la nuova tabella

R O T I E W N avanzi (inclusi W e N)
0 2 4 5 1 pari (6,8) (3,8;9) 36789
0 2 4 5 6 dispari (3,7) (1,6;3,8) 13789
0 2 5 4 1 pari (6,8) (3,8;9) 36789
0 2 5 4 6 dispari (3,7) (1,6;3,8) 13789
0 4 8 9 2 pari (6) (3) 13567
0 4 8 9 7 dispari (1,3,5) (5;1,6;2) 12356
0 4 9 8 2 pari (6) (3) 13567
0 4 9 8 7 dispari (1,3,5) (5;1,6;2) 12356

Ora, poiché

T N
pari (0,1,2,3,4)
dispari (5,6,7,8,9)

otteniamo

R O T I E W N avanzi (inclusi W e N)
0 2 4 5 1 pari (6) (3) 36789
0 2 4 5 6 dispari (3,7) (1;3) 13789
0 2 5 4 1 pari (6, 8) (8;9) 36789
0 2 5 4 6 dispari (7) (8) 13789
0 4 8 9 2 pari (6) (3) 13567
0 4 8 9 7 dispari (3, 5) (1;2) 12356
0 4 9 8 2 pari (6) () 13567
0 4 9 8 7 dispari (1, 3) (5;6) 12356

(Abbiamo eliminato la penultima riga, dato che era vuota dopo aver eliminato i conflitti)

Ora la tabella principale diventa

R O T I E W N avanzi
0 2 4 5 1 6 3 789
0 2 4 5 6 3 1 789
0 2 4 5 6 7 3 189
0 2 5 4 1 6 8 379
0 2 5 4 1 8 9 367
0 2 5 4 6 7 8 139
0 4 8 9 2 6 3 157
0 4 8 9 7 3 1 256
0 4 8 9 7 5 2 136
0 4 9 8 7 1 5 236
0 4 9 8 7 3 6 125

Ora estraiamo l’ultimo pezzo di informazione dal testo del puzzle:

FOU +
 ON =
-----
FIV

Guardando la colonna più a destra vediamo che

a. la cifra più a destra di U+N è uguale a V
b. quando I è pari non c’è nessun riporto, per cui U+N < 10, d’altro canto quando I è dispari U+N > 9

Possiamo allargare la tabella principale con i valori possibiliper la somma di U e V

R O T I E W N spare U+N vincolo
0 2 4 5 1 6 3 789 (10,11,12) U+N>9
0 2 4 5 6 3 1 789 (8,9,10) U+N>9
0 2 4 5 6 7 3 189 (4,11,12) U+N>9
0 2 5 4 1 6 8 379 (11,15,17) U+N<10
0 2 5 4 1 8 9 367 (12,15,16) U+N<10
0 2 5 4 6 7 8 139 (9,11,17) U+N9
0 4 8 9 7 3 1 256 (3,6,7) U+N>9
0 4 8 9 7 5 2 136 (3,5,8) U+N>9
0 4 9 8 7 1 5 236 (7,8,11) U+N<10
0 4 9 8 7 3 6 125 (7,8,11) U+N<10

Possiamo imporre il vincolo, ottenendo

R O T I E W N U+N U V
0 2 4 5 1 6 3 (10,11,12) (7,8,9) (0,1,2)
0 2 4 5 6 3 1 (10) (9) (0)
0 2 4 5 6 7 3 (11,12) (8,9) (1,2)
0 2 5 4 6 7 8 (9) (1) (9)
0 4 8 9 2 6 3 (10) (7) (0)
0 4 9 8 7 1 5 (7,8) (2,3) (7,8)
0 4 9 8 7 3 6 (7,8) (1,2) (7,8)

Se eliminiamo i conflitti cancelliamo la maggiorparte delle righe, arrivando finalmente a

R O T I E W N U V
0 2 4 5 6 7 3 (8) (1)
0 2 5 4 6 7 8 (1) (9)

Da qui leggiamo le uniche due soluzioni

3496 -
3210 =
------
 286 +
 286 =
------
 572

e

9516 -
9280 =
------
 236 +
 236 =
------
 472

Possiamo verificare queste soluzioni usando lo script Python presentato nel primo post della serie.

Un Pitone nel labirinto: seconda fitta

english

Abbiamo precedentemente visto una strategia per risolvere questo puzzle (ogni lettera sta per uno e un solo numero)

FIVE -
FOUR =
------
 ONE +
 ONE =
------
 TWO

Prima abbiamo trovato una rappresentazione comoda dello spazio delle soluzioni possibili, una rappresentazione che possiamo gestire con carta e penna: per fare ciò paradossalmente abbiamo dovuto pensare in maniera algoritmica, come se stessimo per istruire un computer a risolvere il problema – un computer effettivamente molto limitato!…

Chi ben cominicia…

Possiamo riscrivere le operazioni che fanno parte del testo del puzzle per rendere il compito un pò più facile. Per esempio riscrivendo la sottrazione come una addizione

FOUR +
 ONE =
------
FIVE

Da qui segue che l’ultima cifra di R + E deve essere uguale a E. Perché questo sia vero deve essere R = 0. Passiamo all’addizione

ONE +
ONE =
-----
TWO

Ora la colonna più a destra dice che O è la cifra più a destra di E + E. Per cui O deve essere un numero tra 2, 4, 6, 8 (non 0, ricorda la nostra assunzione precedente), vale a dire che TWO è un numero pari. Ma dalla colonna più a sinistra di questa somma sappiamo che o O + O = T oppure (in caso di riporto dalla colonna vicina) O + O + 1 = T, così vediamo che O non può superare 4 (altrimenti ci sarebbe un ulteriore riporto, e il risultato avrebbe quattro cifre anziché tre). Quindi o O = 2 oppure O = 4. Possiamo usare la colonna più a destra della somma per inferire che nel primo caso si ha o E = 1 oppure E = 6, nell’altro o E = 2 oppure E = 7. Infatti se O=2

 1 +       6 +   
 1 =   e   6 =
----      ----
 2        12    (teniamo solo la cifra più a destra 2)

Similmente per O=4

 2 +       7 +   
 2 =   e   7 =
----      ----
 4        14    (teniamo solo la cifra più a destra 4)

Inoltre, facendo riferimento alla somma

ONE +
ONE =
-----
TWO

vediamo che quando O = 2 abbiamo o T = 4 oppure T = 5 (a seconda di se c’e’ riporto dalla colonna centrale o meno); mentre O = 4 implica che o T = 8 oppure T = 9 (sempre per il riporto).

Facciamo adesso un sunto di quanto abbiamo raccolto

R O T E
0 2 4 1
0 2 4 6
0 2 5 1
0 2 5 6
0 4 8 2
0 4 8 7
0 4 9 2
0 4 9 7

Torniamo ora alla sottrazione: visto che R = 0 possiamo riscriverla come segue (“dimenticando” la colonna più a destra)

FOU +
 ON =
-----
FIV

La colonna di mezzo dice che o O + O = I oppure O + O + 1 = I (in caso di riporto, cioè U + N >9). Ma attenzione! Avevamo anche scoperto che o O + O = T oppure O + O + 1 = T! Dal momento che ogni lettera rappresenta una cifra univoca T e I non possono essere uguali. Scriviamo questo fatto in una tabella (usando ciò che sappiamo sulla O)

O T I
2 4 5
2 5 4
4 8 9
4 9 8

Possiamo infilare questa tabella nella tabella più grande

R O T I E avanzi
0 2 4 5 1 36789
0 2 4 5 6 13789
0 2 5 4 1 36789
0 2 5 4 6 13789
0 4 8 9 2 13567
0 4 8 9 7 12356
0 4 9 8 2 13567
0 4 9 8 7 12356

Questa tabella sta iniziando a diventare un po’ grande, ma ci permette ancora di tenere i calcoli entro un limite di grandezza gestibile. Notare che ho anche aggiunto una colonna con le cifre che “avanzano” (cioè cifre che non abbiamo ancora associato ad una lettera). Ricordiamo che restano ancora da determinare le lettere W, N, U, V, F.

E’ il momento di un’altra pausa di riflessione, di nuovo invitando chi legge a provare ad andare avanti per conto proprio. Il resto della storia comparirà in questa colonna tra qualche giorno.

Un Pitone nel labirinto: prima fitta

english

Un puzzle può essere un esercizio divertente per migliorare le tecniche e le conoscenze matematiche. Quando uno poi prende l’abitudine di mischiare programmazione e argomenti matematici o scientifici viene piuttosto naturale usare un approccio ibrido. Dal momento che questo è un blog sulla Matematica e sulla didattica in questo momento mi interessa enfatizzare in che modo è possibile convertire un puzzle in una opportunità per allenare sia le abilità matematiche che quelle di programmazione allo stesso tempo, e come ognuno dei due set di competenze può indurre l’altro ad entrare in funzione. Il puzzle seguente mi è stato proposto da uno studente a lezione.

Ogni lettera sta per una e una sola cifra (possiamo supporre che le cifre/lettere più significative siano diverse da zero, cioè F, O e T non sono uguali a 0):


FIVE -
FOUR =
------
 ONE +
 ONE =
------
 TWO

Risolvere questo problema implica effettuare un certo numero di deduzioni basate sul testo del problema e sulla meccanica di base dell’addizione e della sottrazione (cioè le regole di riporto/prestito).
Di certo per trovare le soluzioni c’è bisogno di utilizzare una certa quantità di logica, ma l’impiego di ciò che viene spesso chiamato il “pensiero computazionale” probabilmente permette di arrivare alle soluzioni in una maniera che sia più conveniente del concatenare una sequenza interminabile (o almeno molto lunga) di proposizioni logiche.

Ma come farebbe una macchina a risolvere questo problema? Una possibilità sarebbe di trovare la strada per uscire dal labirinto tramite forza bruta. Per esempio si potrebbero generare tutte le permutazioni possibili dei valori delle lettere, e vedere per ognuno di loro se i vincoli sono soddisfatti. Una soluzione molto facile potrebbe essere questo script Python molto elementare

from itertools import permutations


def tonum(*a): # convert tuple in numeri interi
    l = len(a)
    res = 0
    for i in xrange(l):
         res += a[i]*10**(l-i-1)
    return res


solutions = [
    (
        tonum(f,i,v,e), 
        tonum(f,o,u,r), 
        tonum(o,n,e), 
        tonum(t, w, o)
    ) for (f, i, v, e, o, u, r, n, t, w) in permutations(range(10)) 
        if tonum(f,i,v,e)-tonum(f,o,u,r)==tonum(o,n,e) and 
            tonum(o, n, e)*2 == tonum(t, w, o)]


# rapporto

print "%d soluzioni trovate:" % (len(solutions), )
print
for five, four, one, two in solutions:
    print "%4d -" % (five,)
    print "%4d =" % (four,)
    print "------"
    print "%4d +" % (one,)
    print "%4d =" % (one,)
    print "------"
    print "%4d" % (two, )
    print

Chiaramente questo programma non è particolarmente veloce o efficiente, dato che genera tutte le 10! permutazioni mantenendo solo “quelle buone“. Ma ci mostra uno schema per risolvere un puzzle combinatorio di questo tipo. Dobbiamo ora solo sviluppare una strategia che ci permetta di tenere manualmente traccia delle possibili soluzioni risparmiando gli sforzi non necessari.

Permutazioni

Procediamo con ordine: come si generano tutte le permutazioni (per esempio) dei numeri 0, 1, 2?
Partiamo dal primo numero (0), in questo modo

livello 0     *
              |
livello 1     0 (1,2) 

Dai numeri che rimangono (quelli nelle parentesi) estraiamo ogni volta il prossimo della serie, continuando in questo modo

livello 0     *
              |
livello 1     0 (1,2)
              |
livello 2     1 (2) 
              |
livello 3     2 ()

Quando consumiamo tutti i numeri allora saliamo di un livello (“backtrack“): torniamo indietro sui nostri passi, tenendo traccia di quello che abbiamo scritto finora, e proviamo tutte le alternative possibili lungo il percorso

livello 0         *
                  |
livello 1         0 (1,2)
               /--'--\
livello 2     1 (2)   2 (1)
              |       |
livello 3     2       1

Continuiamo così

livello 0                        *
                   /-------------|-------------\
livello 1         0 (1,2)        1 (0,2)        2 (0,1)
               /--'--\        /--'--\        /--'--\
livello 2     1 (2)   2 (1)  0 (2)   2 (0)  0 (1)   1 (0)
              |       |      |       |      |       |
livello 3     2       1      2       0      1       0

permutaz.:   012     021    102     120    201     210

Spero che il disegno sia abbastanza chiaro, sostanzialmente costruiamo un albero, usandolo per tenere traccia delle possibilità.

Dall’albero alle tavole (matematica per carpentieri?)

L’albero ha una struttura molto bella e sintetica, ma può essere scomodo da disegnare. Possiamo a questo punto farlo diventare una tabella, come segue:

livello 0 livello 1 livello 2 livello 3 permutazione
* 0 1 2 012
2 1 021
1 0 2 102
2 0 120
2 0 1 201
1 0 210

Ancora una volta spero che la tabella parli da sola: riesci a vedere perché questa tabella è equivalente all’albero disegnato sopra? Useremo tabelle come questa per tenere traccia delle soluzioni candidate, ma cercheremo di evitare tabelle troppo grandi per essere maneggiate con carta e penna, per evitare di perdere il controllo delle cose.

Continueremo il discorso in un post futuro, ma nel frattempo con un po’ di buona volontà consiglio di provare ad andare avanti per conto proprio a partire dal punto in cui siamo arrivati, così da fare un pò di esercizio.

Test a grana fine

Una suite di test con molte strofe

english

Questa serie di test copre la maggior parte delle abilità algebriche che ti si richiede di padroneggiare. Fondamentalmente è una serie di micro-esercizi.
Svolgi ogni esercizio a prescindere da quanto ti possa sembrare semplice, poi controlla il risultato. Ogni esercizio è seguito dal riferimento alla pagina del libro di testo dove viene trovi la teoria relativa all’esercizio. Se la tua soluzione non corrisponde a quella data, vuol dire che ti sei perso qualcosa: prendi il libro e cerca di colmare la lacuna, poi ritenta con gli esercizi. Nel caso tu ancora non riesca a trovare la risposta giusta per conto tuo, chiedi all’insegnante durante la prossima lezione.
Ricorda che non avrai un voto per questi test, sono degli strumenti di diagnosi: usali con saggezza!

[2015-04-08]   Aggiornamento: Test suite aggiornata (errore a pagina 5)

Scarica il file PDF