Un pagamento complicato

Monete

Devo pagare esattamente 5 euro, utilizzando monete da 2 euro, da 1 euro, da 50 centesimi, da 20 centesimi, e da 10 centesimi. Per esempio potrei utilizzare una moneta da 2, quattro da 0,50 e cinque da 0,20. Ma ci sono tanti altri modi per farlo. In quanti modi in tutto potrei pagare?

Diverse riflessioni e soluzioni:

Il primo approccio, più semplice, è quello classico di “forza bruta”: scrivo una tabella e, partendo dal caso con solo 50 monete da 10 centesimi, arrivo fino al caso di due monete da 2€ e una da 1€:

2 € 1 € 0,50 € 0,20 € 0,10 €  Somma
0 0 0 0 50 5,00 €
0 0 0 1 48 5,00 €
0 0 0 2 46 5,00 €
...
2 0 2 0 0 5,00 €
2 1 0 0 0 5,00 €

Completando la tabella, con un po’ di pazienza, si trova la soluzione: 450 modi diversi di pagare 5€. Potete scaricare la tabella Excel completa qui.

Se siete programmatori, potete invece scrivere un breve programma in C++ (grazie a Zulzo per averci inviato questa soluzione).

Come risolvere invece questo problema semlicemente con carta e penna?

Vedo in quanti modi posso fare 5 euro, poi 4,50 euro, poi 4, e così via fino a 0 euro, usando solo monete da 2 euro, 1 euro, e 50 centesimi.

Per semplicità, non scriverò le monete da 0,50, in quanto saranno quelle che servono per completare il pagamento.

Allora 5 euro si possono pagare con 2+2+1, 2+2 (+0,50+0,50, ma non lo scriverò più, come detto), 2+1+1+1, 2+1+1, 2+1, 2, 1+1+1+1+1, 1+1+1+1, 1+1+1, 1+1, 1, 0 (quest’ultimo caso indica 10 monete da 0,50), cioè posso pagare 5 euro in 12 modi diversi.

Ora penso di pagare 4,50 euro, e posso farlo con 2+2, 2+1+1, 2+1, 2, 1+1+1+1, 1+1+1, 1+1, 1, 0, cioè posso pagare 4,50 in 9 modi diversi, e posso completare i 50 centesimi mancanti in 3 modi diversi (cioè con 0, 1 o 2 monete da 20 e il resto da 10), per un totale di 9×3 = 27 modi diversi.

Ora penso di pagare 4 euro, e posso farlo negli stessi 9 modi diversi con cui posso pagare 4,50 (basta togliere una moneta da 0,50), e posso completare l’euro mancante in 6 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 5), per un totale di 9×6 = 54 modi diversi.

Ora penso di pagare 3,50 euro, e posso farlo con 2+1, 2, 1+1+1, 1+1, 1, 0, cioè posso pagare 3,50 in 6 modi diversi, e posso completare gli 1,50 euro mancanti in 8 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 7), per un totale di 6×8 = 48 modi diversi.

Ora penso di pagare 3 euro, e posso farlo negli stessi 6 modi diversi con cui posso pagare 3,50 (basta togliere una moneta da 0,50), e posso completare i 2 euro mancanti in 11 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 10), per un totale di 6×11 = 66 modi diversi.

Ora penso di pagare 2,50 euro, e posso farlo con 2, 1+1, 1, 0, cioè posso pagare 2,50 in 4 modi diversi, e posso completare i 2,50 euro mancanti in 13 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 12), per un totale di 4×13 = 52 modi diversi.

Ora penso di pagare 2 euro, e posso farlo negli stessi 4 modi diversi con cui posso pagare 2,50 (basta togliere una moneta da 0,50), e posso completare i 3 euro mancanti in 16 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 15), per un totale di 4×16 = 64 modi diversi.

Ora penso di pagare 1,50 euro, e posso farlo con 1, 0, cioè posso pagare 1,50 in 2 modi diversi, e posso completare i 3,50 euro mancanti in 18 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 17), per un totale di 2×18 = 36 modi diversi.

Ora penso di pagare 1 euro, e posso farlo negli stessi 2 modi diversi con cui posso pagare 1,50 (basta togliere una moneta da 0,50), e posso completare i 4 euro mancanti in 21 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 20), per un totale di 2×21 = 42 modi diversi.

Ora penso di pagare 0,50 euro, e posso farlo con 0, cioè posso pagare 0,50 in un solo modo, e posso completare i 4,50 euro mancanti in 23 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 22), per un totale di 1×23 = 23 modi diversi.

Ora penso di pagare 0 euro, e posso farlo nello stesso modo con cui posso pagare 0,50 (basta togliere la moneta da 0,50), e posso completare i 5 euro mancanti in 26 modi diversi (cioè con monete da 20 centesimi in numero da 0 a 25), per un totale di 1×26 = 26 modi diversi.

In tutto: 12+27+54+48+66+52+64+36+42+23+26=450.

Penso di averla fatta molto lunga; in realtà quando ho capito il ragionamento, ho semplicemente fatto una tabellina di coppie di numeri che andranno moltiplicati: il primo fattore è il numero di possibilità di fare i vari importi solo con 2, 1, 0,50, e il secondo fattore il numero di possibilità di pagare il resto solo con 0,20 e 0,10. Il secondo fattore segue una semplice regola: una volta aumenta di 2 e una volta di 3 unità (1, 3, 6, 8, 11…)

© Giorgio Dendi

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *