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.

A Python in a maze: third fit

italian

Let’s continue the story from a previous post.

Since ONE + ONE = TWO we can hope to constraint the values of N to the value of W somehow. For starters we can say that because of the rightmost column when E>4 then W is odd because of the carry, while W is even when E<5

 1
ONE +
ONE =    when E is greater than 4
-----
TWO

 0
ONE +
ONE =    when E is less than 5
-----
TWO

In a table this becomes:

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)

Likewise, there is a similar relationship linking T and N: if T is odd there must be some carry from the nearby column, so that N>4, while T even implies N<5. In a table

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)

Notice that there are conflicts: we will resolve them sticking these minitables into the master table we are maintaining, in a moment. When W is even (no carry from E + E) the rightmost digit of N + N is W (when W is odd we must decrease it by 1 of course). A similar argument can be made for the latter table. Since we know that R = 0 we can drop the cases where either W or N are 0, or those where W = N. This leads to the table

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

Were we to inject this table – which is quite long – into the master table that would make it too long to be manageable by hand; or not, depending on your laziness: it saturates mine for sure, so we have to find some smarter trick. The following table could be a starting point, we add columns to list the possible values for W

R O T I E W spare (including W)
0 2 4 5 1 even (2,4,6,8) 36789
0 2 4 5 6 odd (1,3,5,7,9) 13789
0 2 5 4 1 even (2,4,6,8) 36789
0 2 5 4 6 odd (1,3,5,7,9) 13789
0 4 8 9 2 even (2,4,6,8) 13567
0 4 8 9 7 odd (1,3,5,7,9) 12356
0 4 9 8 2 even (2,4,6,8) 13567
0 4 9 8 7 odd (1,3,5,7,9) 12356

We now exclude the values of W that conflict with the other letters, so in example in the first row

R O T I E W spare (including W)
0 2 4 5 1 even (2,4,6,8) 36789

W cannot have the values 2 or 4, so we get

R O T I E W spare (including W)
0 2 4 5 1 even (6,8) 36789

Now we add the column for N starting from the values for W

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;4,9) 36789

We can exclude the conflicts here too

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;9) 36789

Then we get the new table

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;9) 36789
0 2 4 5 6 odd (3,7) (1,6;3,8) 13789
0 2 5 4 1 even (6,8) (3,8;9) 36789
0 2 5 4 6 odd (3,7) (1,6;3,8) 13789
0 4 8 9 2 even (6) (3) 13567
0 4 8 9 7 odd (1,3,5) (5;1,6;2) 12356
0 4 9 8 2 even (6) (3) 13567
0 4 9 8 7 odd (1,3,5) (5;1,6;2) 12356

Now since

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

we obtain

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6) (3) 36789
0 2 4 5 6 odd (3,7) (1;3) 13789
0 2 5 4 1 even (6, 8) (8;9) 36789
0 2 5 4 6 odd (7) (8) 13789
0 4 8 9 2 even (6) (3) 13567
0 4 8 9 7 odd (3, 5) (1;2) 12356
0 4 9 8 2 even (6) () 13567
0 4 9 8 7 odd (1, 3) (5;6) 12356

(Second to last row is empty, so we can drop it)

Now the master table becomes

R O T I E W N spare
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

Now We extract the last bit of information from the statement of the puzzle:

FOU +
 ON =
-----
FIV

Looking the rightmost column we see that

a. the rightmost digit of U+N equals V
b. when I is even there is no carry, hence U+N < 10, on the other hand when I is odd U+N > 9

Let’s augment the master table with the possible values for the sum of U and V

R O T I E W N spare U+N constraint
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

We must enforce the constraint, obtaining

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)

If we eliminate the conflicts we delete most of the rows arriving finally at

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)

This gives the only two solutions

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

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

One can verify these solutions by using the python script presented in the first post of this series.

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.

A Python in a maze: second fit

italian

Previously we saw a strategy to solve this puzzle (each letter stands for one and only one number)

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

First we found a comfortable representation of the space of possible solutions, a representation we could handle with paper and pencil: to do this paradoxically we had to think in an algorithmic manner, as if we were going to instruct a computer to solve the problem – a very limited computer indeed!…

Let’s get started

One can rewrite the operations composing the statement of the puzzle to make the task a little bit easier. For instance rewriting the subtraction

FOUR +
 ONE =
------
FIVE

Therefore the last digit of R + E must equal E. For this to be true R = 0. From the addition

ONE +
ONE =
-----
TWO

Now the rightmost column says that O is the rightmost digit of E + E. Hence O must be one of 2, 4, 6, 8 (not 0, recall our earlier assumption), since TWO is an even number. But from the leftmost column of this sum we know that either O + O = T or (in case of carry from the nearby column) O + O + 1 = T, so that O cannot be greater than 4 (otherwise there would be a carry from the leftmost column, so that the result would be four digits long instead of three). Therefore either O = 2 or O = 4. We can use the rightmost column of the sum to infer that in the former case either E = 1 or E = 6, in the latter either E = 2 or E = 7.
Indeed if O=2

 1 +         6 +
 1 =   and   6 =
----        ----
 2          12  (we keep only the lsd 2)

Likewise for O=4

 2 +       7 +   
 2 =   e   7 =
----      ----
 4        14    (we keep only the lsd 4)

In turn we see from the addition

ONE +
ONE =
-----
TWO

that when O = 2 we can have either T = 4 or T = 5 (according to whether there is carry or not); while O = 4 implies that either T = 8 or T = 9 (again, carry).

To summarize what we’ve found

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

Now let’s go back to the subtraction: since R = 0 we can write it as follows (just “forgetting” the rightmost column)

FOU +
 ON =
-----
FIV

The middle column says that either O + O = I or O + O + 1 = I (in case of carry, i.e. U + N >9). But wait a moment! We also had that either O + O = T or O + O + 1 = T. Since each letter represents a unique digit T and I cannot e equal. Let’s write this with a table (using what we know about O)

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

Put this into the larger table to obtain

R O T I E spare
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

This thing is becoming a bit large, but it enables us to keep the calculation down to a manageable size. I also added a column with the spare digits (i.e. digits we haven’t associated to a letter yet). Recall that we have the letters W, N, U, V, F yet to determine.

Now it’s time enough for another pause to reflect a little bit. I invite you to go on the path shown in this post, at least for a few steps. The end of the story in a following post.

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.

A Python in a maze: first fit

italian

A puzzle can be a funny exercise for improving mathematical knowledge/technique. When one gets into the habit of mixing coding and maths/science then using a hybrid approach seems quite natural. Since this is a blog on math and teaching now I want to emphasize the way one can turn a puzzle into a chance for training both the maths and the coding skills at once, and also the way one skillset can help the other one to kick in. The following puzzle has been proposed to me by a student in a class.

Each letter stands for a unique one digit number (it is safe to assume that the most significant digits/letters are not zero, i.e. F, O and T are different from zero):


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

Solving this problem involves doing some deduction based on the statement of the problem and the basic mechanics of addition and subtraction (i.e. rules for carry/borrow).
Surely there is some logic involved in the solution, but by employing what someone calls the “computational thinking” probably one can arrive to the solution(s) in a more convenient way than chaining countless (or at least many) clauses.

What would a machine do to solve the problem? One chance would be to brute-force our way out of the maze. In example one could generate all possible permutations of the values of the letters, and see whether each of them fulfills the constraint. An easy solution could be this very basic Python script

from itertools import permutations


def tonum(*a): # convert tuples to integer numbers
    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)]


# report

print "%d solutions found:" % (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

Of course this is not particularly fast/efficient, as it generates all of the 10! permutations and keeps only the good ones. But it teaches us a scheme to solve a combinatorial puzzle like this one. We only have to devise a strategy that allows us to keep track manually of the possibilities saving all unneeded efforts.

Permutations

First things first: how to generate all permutations of (say) the numbers 0, 1, 2?
Start with the first number, like so

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

From the remaining numbers (the ones in parentheses) extract next one, and so on

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

When one consumes all the numbers the backtrack occurs: go back on your steps, keeping track of what you have done so far, and try all the possible alternatives along the way

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

And on again

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

perm:      012     021    102     120    201     210

I hope the drawing is clear enough, we basically build a tree, and use this to keep track of the possibilities.

From trees to tables (math for carpenters?)

The tree has a beautiful and very terse structure, but can be unwieldy to draw. One can then change it into a table, so that the tree above becomes

level 0 level 1 level 2 level 3 permutation
* 0 1 2 012
2 1 021
1 0 2 102
2 0 120
2 0 1 201
1 0 210

Again, I hope the table speaks by itself: can you see why it is equivalent to the tree above? We will use tables like this one to keep track of the possible solutions, but we’ll keep things from spin out of control, trying to avoid tables too big to handle with pencil and paper.

We’ll work on this again in a following post, but in the meanwhile you can try to go on all by yourselves starting from this point, with a bit of good will, just to have some fun with a bit of exercise.