Centesimi

[axpgn]

In quanti modi diversi è possibile comporre un importo di $n$ centesimi usando le monete da $1$, $2$ e $5$ centesimi ?

Cordialmente, Alex

[giammaria]

Ma c'è una soluzione decente? Io trovo un risultato molto brutto, tanto che non lo metto neppure in spoiler; il ragionamento per arrivarci è anche peggio. Sarà almeno giusto?

Posto $n=10k+r$, con $0<=r<=9$, ottengo che il numero di modi diversi è dato da
$5k^2+(r+4)k+a_r" "$ con $" "a_r={(r-1 if 3<=r<=9),(1+[r/2] if 0<=r<=2):}$

Con $[...]$ indico la parte intera del numero in parentesi.

[axpgn]

Sì, esiste una soluzione decente ... ... c'è una formula, anche relativamente semplice che però va arrotondata all'intero più vicino ...

Peraltro, complimenti per la tua soluzione, l'ho verificata per una trentina di valori e funziona

Cordialmente, Alex

[veciorik]

Testo nascosto, fai click qui per vederlo

$ \sum_{i=0}^{\floor(n/5)} \ \floor((2+n-5i)/2) $

[axpgn]

Sì, funziona ma è una sommatoria ... esiste un formula chiusa decisamente più comoda ...

Cordialmente, Alex

[axpgn]

Esatto!
Come la dimostri?

Questa è la mia ...

Testo nascosto, fai click qui per vederlo

Cominciamo dal fatto che se dovessimo usare solo monete da $1$ e $2$ centesimi per comporre un importo di $n$ centesimi, le combinazioni sarebbero $\lfloorn/2\rfloor+1$, questo perché potremmo usare nessuna moneta da $2$ centesimi ma tutto in monete da $1$ oppure una moneta da $2$ e il resto in centesimi oppure due monete da $2$ e il resto in centesimi e così via.

Posto $n=5q+r$ dove $q=\lfloorn/5\rfloor$ e $r=0,1,2,3,4$, possiamo fare la stessa cosa con le monete da $5$ cioè comporre $n$ senza monete da $5$ oppure una sola moneta da $5$ oppure due monete da $5$ e così via.

In sintesi $C=(\lfloorn/2\rfloor+1)+(\lfloor(n-5)/2\rfloor+1)+(\lfloor(n-10)/2\rfloor+1)+...+(\lfloorr/2\rfloor+1)$

Usando l'identità $\lfloorm/2\rfloor=m/2-1/4+(-1)^m/4$ possiamo riscrivere la nostra espressione così

$C=(n/2+3/4+(-1)^n/4)+((n-5)/2+3/4+(-1)^(n-5)/4)+((n-10)/2+3/4+(-1)^(n-10)/4)+...+(r/2+3/4+(-1)^r/4)$

da cui

$3/4(q+1)+((-1)^n/4+(-1)^(n-5)/4+...+(-1)^r/4)+(n/2+(n-5)/2+...+r/2)$.

L'espressione nell'ultima parentesi è una progressione aritmetica pari a $(q+1)/2(n/2+r/2)$.

L'espressione con $(-1)^p$ ha valori alternati e se $n$ e $r$ sono pari vale $+1/4$, se $n$ e $r$ sono dispari vale $-1/4$ e vale $0$ altrimenti; chiamiamo $w$ il valore di questa espressione.

Detto ciò la riscriviamo $C=3/4(q+1)+w+(q+1)/2(n/2+r/2)$

da cui

$C=(q+1)/4(3+n+r)+w=(5q+5)/20(3+n+r)+w=((n-r+5)(n+r+3))/20+w=(n+4)^2/20-(r-1)^2/20+w$

Ora se $r=0,1,2,3$ allora $|-(r-1)^2/20+w|<=4/20+1/4<1/2$

mentre se $r=4$ allora $w>=0$ e $|-(r-1)^2/20+w|<=|-9/20+1/4|<1/2$.

Quindi il numero cercato è $(n+4)^2/20$ arrotondato all'intero più vicino.

Cordialmente, Alex

[axpgn]

L'intuito non è una colpa

Sei grande!

Cordialmente, Alex