Qui abbiamo monetine da 3-cent.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Qui abbiamo monetine da 3-cent.

Messaggio da Ido Bovski » 13 dic 2012, 20:33

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
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Hawk » 05 gen 2013, 19:40

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 $?
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Ido Bovski » 05 gen 2013, 20:11

Hawk ha scritto: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
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Hawk » 05 gen 2013, 21:40

Grazie per aver risposto. Purtroppo il tuo hint uccide ogni mia speranza di risolvere il problema :cry: , non conosco le funzioni generatrici.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »


Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Drago96 » 09 gen 2013, 17:19

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}$ :roll:
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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Ido Bovski » 09 gen 2013, 18:32

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}$.

Avatar utente
auron95
Messaggi: 232
Iscritto il: 08 lug 2012, 12:20

Re: Qui abbiamo monetine da 3-cent.

Messaggio da auron95 » 13 gen 2013, 20:59

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'... :oops:
Ultima modifica di auron95 il 13 gen 2013, 21:52, modificato 1 volta in totale.
This is it. This is your story. It all begins here.

Avatar utente
auron95
Messaggi: 232
Iscritto il: 08 lug 2012, 12:20

Re: Qui abbiamo monetine da 3-cent.

Messaggio da auron95 » 13 gen 2013, 21:34

auron95 ha scritto: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.... :oops: :oops: :oops:
This is it. This is your story. It all begins here.

totissimus
Messaggi: 17
Iscritto il: 25 dic 2012, 16:44
Località: Cefalù

Re: Qui abbiamo monetine da 3-cent.

Messaggio da totissimus » 15 gen 2013, 09:00

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.

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Drago96 » 12 feb 2013, 17:40

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$???
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

EvaristeG
Site Admin
Messaggi: 4759
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Qui abbiamo monetine da 3-cent.

Messaggio da EvaristeG » 12 feb 2013, 20:03

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.

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Qui abbiamo monetine da 3-cent.

Messaggio da Drago96 » 15 mar 2013, 15:47

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! :D
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Rispondi