Disfida Matematica 2006

Soluzione del problema 21



21
Il baratto.    Bisogna cercare una combinazione del tipo $ a\cdot 560+b\cdot390=20$ con $ a,b$ numeri interi, in modo che la somma dei valori assoluti di $ a$ e $ b$ sia la più piccola possibile. Notiamo che intanto si può dividere tutto per 10, e dunque cerchiamo $ a,b$ per cui $ a\cdot 56+b\cdot39=2$. Un modo brutale ma comunque piuttosto veloce è quello di procedere per tentativi: scriviamo alcuni multipli di 56 e alcuni multipli di 39 e cerchiamo i primi la cui differenza fa $ 2$ o $ -2$:

$\displaystyle \begin{tabular}{c\vert c\vert c} $n$ & $n\cdot 56$ & $n\cdot 39... ... 273\\ 8 & 448 & 312\\ 9 & 504 & 351\\ 10 & 560 & {\bf 390}\\ \end{tabular}$

Abbiamo evidenziato i numeri $ 392=7\cdot 56$ e $ 390=10\cdot 39$ la cui differenza è 2, quindi

$\displaystyle 2=7\cdot 56-10\cdot 39 . $

Quindi il minimo numero di animali da scampiare è $ 7+10$, da cui la risposta \fbox{0017}.

Un modo un po' più rigoroso di procedere è quello di utilizzare una procedura simile al cosiddetto algoritmo di Euclide: se faccio le divisioni successive

$\displaystyle 56:39=1$   col resto di $ 17$    
$\displaystyle 39:17=2$   col resto di $ 5$    
$\displaystyle 17:5=3$   col resto di $ 2$    

mi accorgo che arrivo ad avere un resto 2, quindi posso ricavare

$\displaystyle 17=56-39$    
$\displaystyle 5=39-2\cdot 17 = 39 - 2\cdot(56-39)=-2\cdot 56+3\cdot 39$    
$\displaystyle 2=17-3\cdot 5 =56-39 - 3\cdot(-2\cdot 56+3\cdot 39)= 7\cdot 56-10\cdot 39$    

da cui la soluzione.



Alessandro 2006-04-01