Menu schede
Appendice

I sistemi trattati da Fibonacci e da Abu Kamil
(risolti al computer)

Franco Ghione  -  Sandro Moriggi
 Torna a Home


Esempio di Fibonacci [XI.7.13]

x1 + x2 + x3 + x4 = 100
3
x1 + 2
x2 +
1
2
x3 + x4 = 100
Fibonacci tratta il caso x4
=
70 e analizza possibili soluzioni per valori grandi di x4. Noi usiamo il suo metodo e il calcolatore per risolvere il problema in generale.
Poniamo T
=
100
-
x4, e, prima di tutto, andiamo a risolvere l’equazione omogenea
6
x1 + 4
x2 + x3 = 2
(x1 + x2 + x3)
Seguendo la “cultura delle monete” troviamo le due soluzioni particolari P=(1,0,4) e S=(0,1,2) e dunque ogni soluzione razionale dell’equazione omogenea si ottiene come combinazione lineare di P ed S: .
(x1, x2, x3) = a
(1, 0, 4) + b
(0, 1, 2) = (a, b, 4
a
+
2
b)
da cui
x1 = a
x2 = b
x3 = 4
a
+
2
b
Poiché cerchiamo le soluzioni intere e positive a e b devono essere numeri interi positivi. In generale, come vedremo nei problemi successivi, le cose potrebbero complicarsi quando pur essendo le x intere a e b possono essere rotti. Fibonacci, come vedremo più avanti, fa esempi via via più complicati nei quali esamina anche questi casi o ulteriori altre complicazioni.
A questo punto trovate tutte le soluzioni dell’equazione omogenea si impone a queste soluzioni l’ulteriore condizione sulla somma:
x1 + x2 + x3 = T
ovvero
5
a
+
3
b = T
equazione della quale cerchiamo soluzioni a e b intere positive.
Abbiamo due modi per risolvere questo problema: uno diretto che richiede moltissimi calcoli e l’altro “intelligente” che richiede più matematica. Entrambi i metodi si possono applicare facilmente servendosi di un programma e di un calcolatore che lo esegue. Presentiamo i due metodi scrivendo nel modo più elementare possibile i programmi necessari a trovare le soluzioni.

Cominciamo dal metodo “intelligente” che presenta minori difficoltà algoritmiche e che si serve di un procedimento generale col quale risolvere con numeri interi equazioni lineari. Presentiamo questo metodo, probabilmente noto, almeno in qualche caso, ai matematici cinesi, indiani e arabi nei casi particolari coinvolti dai problemi di Fibonacci.
Prima di tutto si devono trovare due numeri a0, b0 interi (positivi o negativi) per i quali
5
a0
+
3
b0 = 1
questa identità è nota come identità di Bezout ed è sempre possibile, se i due coefficienti sono primi tra loro come lo sono 5 e 3, calcolare a0 e b0 usando l’algoritmo euclideo delle divisioni successive col quale si trova il Massimo comun divisore tra i due coefficienti [bezout.py]. Nel nostro caso si vede immediatamente che a0 = -1 e b0 = 2 infatti
5(-1) + 3(2) = 1
a questo punto per ogni numero u abbiamo
5
(-T
+
3
u) + 3
(2
T
-
5
u) = T
proprio perché 5
(-T
) + 3
(2
T) = T e, per ogni numero u, 5
×
(3
u) = 3
×
(5
u).   Dunque
a = -T
+
3
u
b = 2
T
-
5
u

Non è difficile dimostrare che, essendo 5 e 3 primi tra loro, queste sono le sole soluzioni a e b intere (positive e negative) dell’equazione 5
a
+
3
b = T. Poiché noi cerchiamo solo soluzioni intere positive si dovrà avere -T
+
3
u > 0 e 2
T
-
5
u > 0 e quindi avremo una soluzione intera per ogni u compreso nell’intervallo aperto
1
3
T < u <
2
5
T
A questo punto entrano in gioco le nostre capacità con il calcolatore. Per programmare il computer utilizzeremo il linguaggio Python che ci sembra il più semplice e diretto. Prima di tutto introduciamo un contatore n a partire da 1 per contare le soluzioni che via via troveremo; fissiamo x4 =1; e T=100-x4. In questo modo possiamo usare lo stesso programma cambiando solo il valore di x4; scriviamo poi il primo valore di u nell’intervallo di variabilità: u = int(T/3)+1 (ricordiamo che int(X) indica la parte intera del numero X).
Calcoliamo ora a=3*u-T ,  b=2*T-5*u , x1=a ,  x2=b ,  x3=4*a+2*b, e stampiamo la soluzione ottenuta seguendo la grammatica di stampa del linguaggio che abbiamo scelto. Eseguiamo tutte queste istruzioni fino a quando u è minore di 2*T/5. Infine incrementiamo di una unità u e n. Ecco il nostro programma che trova tutte le soluzioni al nostro problema con x4 =1:

Eseguendo il programma troviamo le seguenti 6 soluzioni: [Nota]
le colonne dell'output sono ottenute sostituendo l'istruzione print(.. con le istruzioni:
if (n-1)%3==0: print()
print('soluzione',n,'(',x1,x2,x3,x4,')',end="\t")))


Se vogliamo ora risolvere il problema iniziale non dobbiamo far altro che eseguire queste stesse operazioni per ogni possibile scelta di x4 da 1 a 99. Ovviamente la cosa da fare a mano è sconsigliabile ma il calcolatore non si annoia mai e per ottenere i risultati che cerchiamo basta aggiungere una riga di programma per dirgli di fare queste operazioni per ogni valore intero nell’intervallo [1,100). Ecco il nuovo programma che trova tutte (sono 304) le soluzioni corrette.

Per trovare le soluzioni al problema trattato da Fibonacci
x1 + x2 + x3 = T
3
x1 + 2
x2 +
1
2
x3 = T
con T<31
basterà scrivere nel programma invece di T=100-x4 , T=31-x4 , e chiedere di non stampare x4 ma di stampare T per sapere le soluzioni nei diversi casi. Ecco il programma adattato con le sue soluzioni [Nota]
le colonne dell'output sono ottenute sostituendo l'istruzione print(.. con le istruzioni:
if (n-1)%4==0: print()
print( '(',x1,x2,x3,T,')',end="\t" ))
che naturalmente confermano i calcoli di Fibonacci


Vediamo ora il metodo diretto per risolvere con numeri interi positivi una semplice equazione lineare probabilmente utilizzato da Fibonacci e da Abu Kamil. Cominciamo con l’equazione 5
a
+
3
b = T. Il procedimento è molto semplice: diamo ad a tutti i valori interi positivi fino a quando 5
a
<
T e se T-5
a è divisibile per 3 ((T-5a)%3==0), poniamo b = (T-5
a)/3 ,  x1
=
a,   x2
=
int(b) ,  x3
=
int(4
a+2
b) e diamo l’istruzione di stampa per scrivere (x1 , x2 , x3) e T, altrimenti aggiorniamo a e infine aggiorniamo n. Ecco il programma


Gli esempi successivi riportano tutti il problema ad una equazione lineare in due incognite da risolvere con numeri interi positivi [eqlin2int.py] e saranno risolti con il metodo “intelligente” che penso debba essere patrimonio della cultura matematica di uno studente delle superiori. Ovviamente, come abbiamo fatto in questo caso, non sarà difficile scrivere un programma usando il metodo diretto.


Esempio di Fibonacci [XI.7.14]

x1 + x2 + x3 = 12
2
x1 +
1
2
x2 +
1
4
x3 = 12
L’equazione omogenea he le due soluzioni indipendenti P=(3,0,4) e S=(1,2,0) dunque la soluzione generale sarà data da

(x1, x2 , x3 ) = a
(3,0,4) + b
(1,2,0) = (3
a+b, 2
b, 4
a)
questa relazione non implica che a e b sono interi ma solamente che
b =
x2
2    a =
x3
4    x1 = 3
x3
4 +
x2
2
da cui 4
x1=3
x3 + 2
x2, dunque x3
=
2
p è pari (p intero) e 2
x1
=
3
p + x2 . Sommando le x otteniamo
7
a + 3
b = 7
p
2 + 3
x2
2 = 12   ovvero   7
p + 3
x2 = 24
dove ora le incognite p e x3 sono tutte intere e positive. L’identità di Bezout fornisce la relazione 7(1)+3(-2)=1 quindi 7(24-3u)+3(-48+7u) = 24 per ogni
48
7 < u <
24
3ovvero 6 < u < 8 Otteniamo dunque una sola soluzione per u=7, p=24-21=3 e x3 =6, x2 = 49-48=1 e x1 =
3
p + x22 = 5. Risulta infatti 5+1+6=12 e 10 +
1
2 +
6
4 = 12.
Disponendo di un computer possiamo risolvere il problema di Fibonacci nel caso che gli uccelli siano A invece di 12. Basterà risolvere l’equazione 7
p
+
3
x2
=
2
A Ecco il nostro programma per A=100 che fornisce le 9 soluzioni del problema [Nota]
le colonne dell'output sono ottenute sostituendo l'istruzione print(.. con le istruzioni:
if (n-1)%3==0: print()
print('sol',n,'(',x1,x2,x3,')',end="\t\t"))
.


Esempio di Fibonacci [XI.7.15]

x1 + x2 + x3 + x4 = 30
3
x1 + 2
x2 +
1
2
x3 +
1
4
x4 = 30
L’equazione omogenea diventa
12
x1 + 8
x2 + 2
x3 + x4 = 4
(x1 + x2 + x3 + x4)
e il problema è più complicato degli altri perché ci sono “2 monete” (da 12 e da 8) di valore maggiore del valore della moneta da 4 che si vuole formare. Per fare una “lega” con le monete da 12 e da 8 dobbiamo usare numeri negativi. Con x3 = x4 = 0 abbiamo infatti la soluzione T=(-1,2,0,0). Altre due soluzioni si ottengono come in Fibonacci: P=(0,1,2,0) S=(0,3,0,4). Ogni soluzione razionale si ottiene come combinazione lineare a coefficienti razionali di queste tre soluzioni. Abbiamo dunque
(x1, x2, x3, x4 ) = a
T
+
b
P
+
c
S = (-a, 2
a
+
b
+
3
c, 2
b, 4
c)
da cui
a = -
x1
b =
x3
2
c =
x4
4
e
x2 = -
2
x1 +
x3
2 +
3
4
x4   cioè   4
x2 = -
8
x1
+
2
x3
+
3
x4
dove x1, x2, x3, x4 sono numeri interi positivi. Questa relazione tra interi (positivi e negativi) ci dice che x4 è pari . Poniamo allora
x1 = -
a
x3 = 2
b = p
x4 = 4
c = 2
q
Imponiamo ora la condizione sulla somma:
a +
3
p2 + 7
q
2 = 30  cioè   2
a
+
3
p
+
7
q = 60   ovvero
3
p
+
7
q = 60
+
2
x1
con p e q interi positivi e x1 tale che
4
x1 < p
+
3
q.
Possiamo ora scrivere il nostro programma ponendo A
=
60
+
x1 . Le soluzioni intere positive p e q si ottengono come di consueto a partire dalla identità di Bezout: 3
(-2)
+
7
(1)
=
1
3
(2
A
-
7
u) + 7
(-
A
+
3
u) = A per ogni u tale che
2
A7 <
A
3
Dunque p = 2
A
-
7
u,   q = -
A
+
3
u e le soluzioni x2, x3, x4 come indicato. Nel programma fissiamo in partenza T
=
30 e x1 e aggiorniamo l’istruzione u=u+1 solo se p+3q-4x1 >0. Ecco il programma

e le 19 soluzioni   [nota]
l'output è ottenuto sostituendo
n=1 e print('sol.'+str(n)+': (',x1,x2,x3,x4,')') con
if (n-1)%3 == 0: print()
print(' sol.',n,': (',x1,x2,x3,x4,')',end="\t")



Le soluzioni trovate da Fibonacci sono la 10 e la 19, quella col valore x1 maggiore. Se lanciamo il programma per 100 uccelli invece di 30 [T
=
100], troviamo 238 soluzioni



I 6 problemi dei 100 uccelli di Abu Kamil

  • Problema 1
x1 + x2 + x3 = 100
5
x1 +
1
20
x2 + x3 = 100
Una soluzione.
Si può fare facilmente a mano: la soluzione è (19,80,1) .
  • Problema 2
x1 + x2 + x3 = 100
2
x1 +
1
3
x2 +
1
2
x3 = 100
Le soluzioni dell’equazione omogenea sono generate da a
(2,3,0)
+
b
(1,0,2) con a e b interi positivi. L’equazione è 5
a
+
3
b
=
100 che si risolve facilmente a mano dando ad a i valori per i quali 100
-
5
a è divisibile per 3.
6 soluzioni.
  • Problema 3
x1 + x2 + x3 + x4 = 100
4
x1 +
1
10
x2 +
1
2
x3 + x4 = 100
Poniamo T
=
100
-
x4.
Usando il metodo di Fibonacci abbiamo due soluzioni indipendenti dell’equazione omogenea
40
x1
+
x2
+
5
x3 = 10
(x1
+
x2
+
x3):  P
=
(3,10,0) e S
=
(1,0,6) e quindi ogni soluzione intera si scrive come
(x1, x2, x3) = a
P
+
b
S
cioè
x1 = 3
a + b
x3 = 10
a
x4 = 6
b
con a e b razionali e x1, x2, x3 interi. In particolare x1
=
3
10
x2
+
1
6
x3 è intero e 30
x1
=
9
x2
+
5
x3 da cui ricaviamo che x2 è divisibile per 5 e x3 è divisibile per 3. Abbiamo dunque
x2 = 5
p
x3 = 3
q
   e  
a =
1
2
p
b =
1
2
q
   con p e q interi positivi

2
x1 = 3
p + q

Imponiamo ora la condizione x1 + x2 + x3 + x4 = 100. Essa, sommando le componenti, equivale a

13
p + 7
q = 2
T

Per trovare tali soluzioni si deve, usando l’identità di Bezout, scrivere 13×(-1) + 7×(2) = 1 da cui ricaviamo 13
×(-2
T) + 7
×(4
T) = 2
T e quindi per ogni intero u abbiamo
13(-2
T
+
7
u) + 7(4
T
-
13
u) = 2
T

e le soluzioni intere positive date da
p = 7
u
-
2
T
q = 4
T
13
u

si ottengono dando a u tutti i valori interi positivi per i quali 2
T > 7
u e 13
u > 4
T cioè

2
T7 < u <
4
T13

Ecco il programma:


Abu Kamil trova 96 soluzioni mentre il problema ne ammette 98
  • Problema 4
x1 + x2 + x3 + x4 = 100
2
x1 +
1
2
x2 +
1
3
x3 + x4 = 100
Poniamo T
=
100
-
x4.
Usando il metodo di Fibonacci abbiamo due soluzioni indipendenti dell’equazione omogenea
12
x1
+
3
x2
+
2
x3 = 6(x1
+
x2
+
x3) : P=(1,2,0) e S=(2,0,3) e quindi ogni soluzione intera si scrive come (x1, x2, x3) = a
P
+
b
S. Ragionando come nel caso precedente si trova x2
=2
a, x3=3
b con a e b interi positivi.
La somma =
T  fornisce l’equazione
3a + 5b = T
ha le soluzioni a
=
2
T
-
5
u e b
=
3
u
-
T con
T
3 < u <
2
T
5
Ecco il programma che fornisce 304 soluzioni, lo stesso numero trovato da Abu Kamil.

  • Problema 5
x1 + x2 + x3 = 100
3
x1 +
1
20
x2 +
1
3
x3 = 100
Usando il metodo di Fibonacci abbiamo due soluzioni indipendenti dell’equazione omogenea
120 x1
+
3
x2
+
20
x3 = 60
(x1
+
x2
+
x3) : P
=
(57, 120, 0) e S
=
(1, 0, 3) e quindi ogni soluzione intera si scrive come
(x1, x2, x3) = a
P
+
b
S =
(
57
a
+
b, 120
a, 3
b)
dove a
=
x2
120,  b
=
x3
30 e x1
=
57
120
x2
+
1
3
x3 cioè 120
x1=19
*
9
x2
+
40
x3, da questo si deduce che x2 =
40
p è divisibile per 40 e semplificando abbiamo 3
x1
=
19
*
9
p
+
x3,   x3
=
3
q è quindi un multiplo di 3 dividendo per 3 abbiamo x1
=
57
p
+
q dove p e q sono interi positivi. p è al massimo 1 perché x1
<
100 e per p
=
1 abbiamo x2=
40, x3
=
3
q
>
3 e x1
>
57 e la loro somma è maggiore di 40
+
3
+
57
>
100 il che è impossibile.
  • Problema 6
x1 + x2 + x3 + x4 + x5 = 100
2
x1 +
1
2
x2 +
1
3
x3 +
1
4
x4 +
x5 = 100
Poniamo subito T
=
100
-
x5 e dunque
x1 + x2 + x3 + x4 = T
e l’equazione omogenea diventa
2
x1 +
1
2
x2 +
1
3
x3 +
1
4
x4 = x1 + x2 + x3 + x4
ovvero
24
x1 + 6
x2 + 4
x3 + 3
x4 = 12
(x1 + x2 + x3 + x4)

Risolviamo subito l’equazione omogenea con metodo di Fibonacci: abbiamo tre soluzioni indipendenti  P
=
(1, 2, 0, 0);  S
=
(2, 0, 3, 0),  Q
=
(3, 0, 0, 4). Ogni soluzione dell’equazione omogenea si ottiene come combinazione lineare a coefficienti razionali di queste soluzioni particolari
(x1 + x2 + x3 + x4) = a
P
+
b
S
+
c
Q = (a
+
2
b
+
3
c, 2
a, 3
b, 4
c)

dove x1, x2, x3, x4 sono numeri interi positivi e a, b, c numeri razionali. Abbiamo dunque
a
=
1
2
x2 ,  b
=
1
3
x3 ,  c
=
1
4
x4 ,  x1
=
1
2
x2
+
2
3
x3
+
3
4
x4
dove l’ultima equazione ovvero
12
x1 = 6
x2 + 8
x3 + 9
x4

coinvolge solo numeri interi positivi. Da questa ricaviamo che 9
x4 è pari e dunque
x4 = 2
q    con q intero positivo.

Dividendo per 2 abbiamo 6
x1 = 3
x2 + 4
x3 + 9
q e quindi 4
x4 è divisibile per 3 e dunque
x3 = 3
p    con p intero positivo.

Dividendo per 3 troviamo che x2
+
4
p
+
3
q deve essere pari e
x1 =
x2
+
4
p
+
3
q
2
Imponiamo (solo ora) la condizione sulla somma:
x2
+
4
p
+
3
q
2 + x2 + 3
p + 2
q = T
ovvero
10
p
+
7
q = A = 200
-
2
x5
-
3
x2
(1)

Ogni soluzione intera positiva p, q, x2 , x5 dell’equazione (1) fornisce una soluzione intera positiva X del sistema iniziale data da
X =
x2
+
4
p
+
3
q
2, x2, 3
p, 2
q
(2)

viceversa ogni soluzione intera del sistema mi da una soluzione intera di (1).
Fissiamo un valore per x5 (da 1 a 99) risolviamo le equazioni 10
p
+
7
q = A = 200
-
2
x5
-
3
x2 dando a x2 tutti i valori da 1 a 99 e poi facciamo lo stesso dando a x5 tutti i valori da 1 a 99.
Vediamo intanto come si risolve con numeri interi positivi l’equazione 10
p
+
7
q = A
Abbiamo, usando l’identità di Bezout,
10
(-
2
A
+
7
u) + 7
(3
A
-
10
u) = A.

e le soluzioni intere positive di (2) si trovano in corrispondenza ai valori u interi per i quali

2
7
A < u <
310
A

per ogni tale u abbiamo p
=
7
u
-
2
A e q
=
3
A
-
10
u e la corrispondente soluzione data da (2).

Ecco il programma che fornisce le 2678 soluzioni


Queste poche righe di programma descrivono un processo col quale calcolare le soluzioni. É un modo molto efficiente per compattare una informazione di grandi dimensioni: anziché elencare esplicitamente le 2678 cinquine si trasmette, a un ipotetico fruitore dotato di un calcolatore elettronico, solo il modo di costruirle.