Qui abbiamo monetine da 3-cent.

[Ido Bovski]

In un paese (chissà quale!) ci sono soltanto monetine da $1$, $2$ e $3$ centesimi. Dimostrare che il numero di modi di cambiare $n$ centesimi è esattamente l'intero più vicino a $(n+3)^2/12$.

[Hawk]

In sostanza il problema, che non mi pare per niente semplice, chiede di trovare il numero delle triple (a,b,c) che risolvono $ a+2b+3c=n $?

[Ido Bovski]

In sostanza il problema, che non mi pare per niente semplice, chiede di trovare il numero delle triple (a,b,c) che risolvono $ a+2b+3c=n $?

Sì, con $a, b, c\in\mathbb{N}$.
Hint:

Testo nascosto:

funzioni generatrici

[Hawk]

Grazie per aver risposto. Purtroppo il tuo hint uccide ogni mia speranza di risolvere il problema , non conosco le funzioni generatrici.

[Troleito br00tal]

Tranquillo, esiste un metodo che non le usa

[Drago96]

Ho da poco iniziato a studiare le funzioni generatrici, quindi questo problema potrebbe rivelarsi istruttivo...

Se $x_n$ è la sequenza che ci interessa (il numero di soluzioni di $a+2b+3c=n$) abbiamo che $\displaystyle\text{ogf}(x_n)=(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)=\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^3}=\frac{1}{1+x}\cdot\frac{1}{(1-x)^3}\cdot\frac{1}{1+x+x^2}$

Supponendo che quello che ho scritto finora sia giusto, come posso continuare? Cioè, dovrei spezzare la moltiplicazione in somma e trovare delle costanti adatte, ma il vero problema è dopo, dato che non saprei come espandere $\displaystyle\frac{1}{(1-x)^3}$ o $\displaystyle\frac{1}{1+x+x^2}$
Un aiutino?

EDIT: $\displaystyle\frac{1}{(1-x)^k}=\sum_{n=0}^\infty{\binom{n+k-1}{k-1}x^n}$ quindi questa è a posto
mi manca l'altra, che non saprei come fare dato che non ha radici reali...

[Ido Bovski]

Trova $A, B, C, D, E, F$ tali che $\displaystyle \frac{1}{(1-x)(1-x^2)(1-x^3)}=\frac{A}{(1-x)^3}+\frac{B}{(1-x)^2}+\frac{C}{1-x}+\frac{D}{1+x}+\frac{E}{1-\omega x}+\frac{F}{1-\overline{\omega}x}$.

[auron95]

Premetto che neanch'io conosco le funzioni generatrici, quindi ho provato in altra maniera......

Testo nascosto:

Chiamo $f(n)$ il numero di cambi di n cents possibili, e $g(n)=f(n)-f(n-1)$.
Consideriamo come aumentano i modi di cambiare $n$ cent rispetto a quelli con $n-1$ cent. Per ogni modo di cambiare $n-1$ cent posso associare uno e un solo modo di cambiare $n$ cent semplicemente aggiungendo una moneta da un centesimo. Non posso fare l'inverso, in quanto non in tutti i modi di cambiare $n$ cent ho una moneta da un centesimo da rimuovere: quindi il numero di modi aumenta tanto quanti sono i modi di cambiare $n$ cent utilizzando solo monete da 2 e 3 cent. Questa quantità è $g(n)$.

Cerchiamo ora di determinare $g(n+1)-g(n)$. Come sopra, definisco una relazione che associa elementi dall'insieme delle combinazioni di $n$ cent a elementi dell'insieme di combinazioni di $n+1$ cent, in modo che l'elemento dell'insieme di arrivo abbia una moneta da 3 cent al posto di una da 2 cent rispetto al "collega" dell'insieme di partenza. Restano fuori da questa associazione:
1. nell'insieme degli n cent, tutte le combinazioni formate da solo monete da 3 cent (non ho monete da 2 cent da sostituire)
2. nell'insieme degli n+1 cent, tutte le combinazioni formate da solo monete da 2 cent.
Quindi la differenza tra le cardinalità degli insiemi è $g(n+1)-g(n) = m_2(n+1)-m_3(n)$, dove con $m_k(n)$ indico i modi di cambiare n monete usando solo monete da k cent, e questo vale ovviamente 1 se $k\mid n$, 0 altrimenti.

Comincio ora a scrivere quello che ho trovato:
$g(n+1)-g(n) = m_2(n+1)-m_3(n)$
$g(n+2)-g(n+1) = m_2(n+2)-m_3(n+1)$
.....
$g(n+6)-g(n+5) = m_2(n+6)-m_3(n+5)$

Sommando tutto membro a membro ho che
$g(n+6)-g(n) = \sum_{i=n}^{n+5}m_2(i+1)-m_3(i)$
Siccome prendo 6 valori consecutivi sia di $m_2$ che di $m_3$, è ovvio che nel caso di $m_2$ 3 dei 6 numeri restituiranno 1, e nel caso di $m_3$ 2 dei 6 numeri daranno 1 (in sei numeri consecutivi ci sono tre multipli di due e due multipli di tre).
Quindi rimane $g(n+6)-g(n)=3-2=1$

C'è quindi una certa regolarità nella differenza tra un valore di f(n) e l'altro: basta trovare i primi 6 numeri e poi usare la formula di ricorrenza trovata sopra e quindi abbiamo che la sequenza della funzione $g(n)$ è: 0,1,1,1,1,2, 1,2,2,2,2,3, 2,3,3,3,3,4......

Dopo questo poema Il problemone è: come utilizzare (sempre che sia possibilie) tutto ciò per ricavare la tesi? Bastarebbe dimostrare che la funzione della tesi aumenta come descritto sopra e saremmo a posto, ma non ho la più pallida idea di come fare..... ci devo pensare su ancora un po'...

[auron95]

Basterebbe dimostrare che la funzione della tesi aumenta come descritto sopra e saremmo a posto, ma non ho la più pallida idea di come fare.....

Stavo scherzando, è anche abbastanza semplice:

Testo nascosto:

Sia $h(n)$ la funzione della tesi (coi valori arrotondati).
Calocolo la differenza tra due valori di h(n) distanti 6 unità:
$\displaystyle \frac{(n+3)^2}{12}-\frac{(n-6+3)^2}{12}=\frac{n^2+6n+9-n^2+6n-9}{12}=n$

Calcolando a mano i primi sei valori della funzione $h(n)$ vediamo che sale come quella descritta nel post precedente: utilizzando la relazione sopra,
abbiamo che $h(n)-h(n-6)=n$ e $h(n+1)-h(n-5)=n+1$; sia ora $g'(n)=h(n)-h(n-1)$
Abbiamo che $h(n+1)-h(n)-(h(n-5)-h(n-6))=n+1-n \Rightarrow g'(n+1)-g(n-5)=1$
Quindi la funzione h(n) sale esattamente in modo uguale a $f(n)$, come descritto dalle funzioni $g(n)$ e $g'(n+1)$ che sono uguali, quindi sono anch'esse uguali.

Spero che capiate qualcosa di questi due post che sono un po' incasinati....

[totissimus]

Voglio proporre una soluzione molto terra-terra ( probabilmente errata ).
Preliminarmente calcolo le soluzioni intere non negative dell'equazione \( \displaystyle 2x+3y=n\).
Distinguo 6 casi:

Caso 1 \( n \equiv 0\) \( mod 0\):
abbiamo \( n= 6m\), \( 2x+3y=6m\), \( 2x=3(2m-y)\), \( x=3j, y=2m-2j\) con \( j=0 \cdots,m\)
quindi ci sono \( m+1\) soluzioni

Caso 2 \( n \equiv 1\) \( mod 6\):
abbiamo \( n=6m+1\) e come analogamente al caso precedente troviamo \(m \) soluzioni.

nei rimanenti casi \( n \equiv 2, n \equiv 3, n\equiv 4, n\equiv 5\) mod 6:
troviamo \( m+1\) soluzioni.

Quindi indicato con \( S(n)\) il numero di soluzioni possiamo scrivere:
\(
S(6m+k)=\begin{cases}
m & k=1\\
m+1 & k=0,2,3,4,5
\end{cases}
\).

Il numero \( T(n)\)di soluzioni di \( a+2b+3c=n\) si può esprimere come:

\( T(n) =\sum_{k=0}^{k\leq n}S(k)\).

Calcoliamo i vari casi:

1)\( n \equiv 0 \mbox{ }mod \mbox{ }6\):

\( T(6m)=\sum_{k=0}^{6m}S(k)=\sum_{i=1}^m S(6i) +\sum_{k=1}^5 \sum_{i=0}^{m-1}S(6i+k)\)
\( =\sum_{i=0}^m (i+1)+\sum_{i=0}^{m-1}i + 4 \sum_{i=0}^{m-1}(i+1)=3m^2+3m+1\).

\(\displaystyle \frac{(n+3)^2}{12}=\frac{(6m+3)^2}{12}=3m^2+3m+\frac{3}{4}\)
l'intero più vicino \(\displaystyle \frac{(n+3)^2}{12}\) è uguale a \(T(n)\).

Analogamente si esaminano i rimanenti casi.

[Drago96]

Boh, provo a riprendere il problema...
Facendo i soliti conti (moltiplicando per un denominatore e mettendo x= cosa che annulla) ottengo che
$\displaystyle A=\frac1 6, D=\frac 1 8, E=F=\frac1 9$
e poi imponendo $x=0$ ho $A+B+C+D+E+F=1$ e quindi $B+C=\frac{35}{72}$
Bene, da qua non saprei come trovare $B$ o $C$, dato che hanno lo stesso denominatore di $A$, ma con esponente più piccolo; generatingfunctionology suggerisce di derivare, ma non saprei dove nè soprattutto come...
C'è un modo per trovare 'sti maledetti $B$ e $C$???

[EvaristeG]

Deriva i due membri dell'uguaglianza:
$$\frac{1}{\textrm{roba}}=\textrm{cose note}+\frac{B}{(1-x)^2}+\frac{C}{1-x}$$
avrai
$$-\frac{\textrm{roba}'}{\textrm{roba}^2}=\textrm{cose note}'+\frac{2B}{(1-x)^3}+\frac{C}{(1-x)^2}$$
questo ti darà un'altra condizione su tipo 2B+C o così e otterrai un sistema che sai risolvere.

[Drago96]

Giusto per non far rimanere incompleto questo problema:
partiamo dal post di Ido e moltiplichiamo tutto per $(1-x)^3$ e otteniamo
$$\displaystyle\frac1{1+2x+2x^2+x^3}=A+(1-x)B+(1-x)^2C+(1-x)^3\cdot\text{roba}$$
ora deriviamo e otteniamo $$\displaystyle-\frac{3x^2+4x+2}{(x^3+2x^2+2x+1)^2}=-B+(1-x)\cdot\text{altra roba}$$
E quindi mettiamo $x=1$ (grande dubbio: posso farlo? perchè? perchè no?) e otteniamo miracolosamente $\displaystyle B=\frac1 4$ e di conseguenza $\displaystyle C=\frac{17}{72}$
Unendo tutto quanto otteniamo infine
$$\displaystyle x_n=\frac{6n^2+36n+47+9\cdot(-1)^n+8\cdot(\omega^n+\omega^{2n})}{72}=\\=\frac{(n+3)^2}{12}+E_n$$
dove $\displaystyle E_n=\frac{9\cdot(-1)^n+8\cdot(\omega^n+\omega^{2n})-7}{72}$ e vale
$$\displaystyle E_n=\begin{cases} \frac{1}{4} & n\equiv0\pmod6 \\ -\frac{1}{3} & n\equiv\pm1\pmod6 \\ -\frac{1}{12} & n\equiv\pm2\pmod6 \\ 0 & n\equiv3\pmod6 \end{cases}$$
Boh, direi che ho finito!