Soluzioni

[axpgn]

Dato $n$ intero positivo, denotiamo con $a_1$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $x+2y=n$, con $a_2$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $2x+3y=n-1$, con $a_3$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $3x+4y=n-2$ e così via fino a denotare con $a_n$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $nx+(n+1)y=1$.

Dimostrare che $a_1+a_2+...+a_n=n$



Cordialmente, Alex

[giammaria]

Possibile che la mia soluzione sia giusta? Mi sembra troppo strana.

Testo nascosto, fai click qui per vederlo

Nell'ultima equazione, un addendo deve valere 0 e l'altro 1. Poiché $n+1>=2$, il secondo addendo non può valere 1 e quindi è 0, ottenibile con $y=0$; ne segue che il primo addendo è 1, ottenibile con $n=x=1$. C'è quindi una sola soluzione, ma $n$ è fisso e la formula da dimostrare si riduce ad $a_n=n=1$.

[dan95]

@giammaria

L'equazione può anche non avere soluzioni in questo caso $a_n=0$ per ogni $n>1$

[Bokonon]

Boh, ho proceduto vincolando le equazioni nell'ipotesi che le coppie di soluzioni debbano soddisfarle tutte (spero di aver capito bene)

Testo nascosto, fai click qui per vederlo

Considero il sistema fra la prima equazione e la k-esima $ { ( x+2y=n ),( kx+(k+1)y=n-k+1 ):} $ con $1<=k<=n$
Moltiplico la prima equazione per $-k$ e la sommo alla seconda, ottenendo $y=n+1 rArr x=-(n+2)$
Questo non è accettabile per ipotesi, pertanto l'unica soluzione per ogni $n$ è che $y=0$ (se fosse $x=0$ varrebbe solo per gli $n$ pari).
Quindi abbiamo una sola soluzione per equazione, ergo $sum_(i=1)^n a_i=n$

[giammaria]

Credo che vada intesa diversamente: ogni equazione ha le sue coppie di soluzioni.
Ad esempio, per $n=2$ abbiamo le due equazioni
$x+2y=2;" " " " 2x+3y=1$
La prima ha come soluzioni le coppie ordinate $(2,0);(0,1)$ mentre la seconda non ha soluzioni, quindi
$a_1=2; a_2=0$ e perciò $a_1+a_2=2$ e la tesi è soddisfatta.
Il difficile è dimostrarlo in generale.

Approfitto dell'occasione per ringraziare dan95 della sua correzione; in primo momento l'avevo fraintesa ma ora l'ho capita ed è giusta.

[axpgn]

Non è un sistema di equazioni ma $n$ equazioni distinte, ognuna con le sue soluzioni (se ce ne sono)

Detto in altro modo ...

Fissato $n$ intero positivo, si hanno $n$ equazioni della forma $kx+(k+1)y=n-k+1$ con $1<=k<=n$.
Detto $a_k$ il numero delle (eventuali) soluzioni $(x,y)$ in interi non negativi della $k$-esima equazione, dimostrare $sum_(k=1)^n a_k=n$

Per esempio, se $n=7$ abbiamo:

$x+2y=7\ \ \ ->\ \ \ 4\text( soluzioni: )(1,3),(3,2),(5,1),(7,0)$
$2x+3y=6\ \ \ ->\ \ \ 2\text( soluzioni: )(3,0),(0,2)$
$3x+4y=5\ \ \ ->\ \ \ 0\text( soluzioni)$
$4x+5y=4\ \ \ ->\ \ \ 1\text( soluzioni: )(1,0)$
$5x+6y=3\ \ \ ->\ \ \ 0\text( soluzioni)$
$6x+7y=2\ \ \ ->\ \ \ 0\text( soluzioni)$
$7x+8y=1\ \ \ ->\ \ \ 0\text( soluzioni)$

e quindi $a_1+a_2+a_3+a_4+a_5+a_6+a_7=4+2+0+1+0+0+0=7$

[3m0o]

Non so se è la buona strada per risolvere il problema ma un pensiero iniziale

Testo nascosto, fai click qui per vederlo

Sia \( g_k(n) \) il numero di modi di rappresentare \(n \) come somma di \(k \) e di \(k+1 \) dove l'ordine conta. Allora abbiamo che
\[ g_k(n) = g_k(n-k) + g_k(n-k-1) \]
con condizioni iniziali
\[ g_k(0)=1, g_k(1) = \ldots = g_k(k-1)=0 , g_k(k)=1 \]

Per noi invece l'ordine non conta, sia quindi \(f_k(n) \) il numero di modi di rappresentare \(n\) come somma di \(k\) e di \(k+1\) dove l'ordine non conta, quindi noi abbiamo che \(a_k=f_k(n-k+1)\). Sia allora \( \ell_k = \operatorname{lcm}(k,k+1)=k(k+1) \).
Abbiamo che
\[ f_k(n)= \left \lfloor \frac{n}{\ell_k} \right \rfloor + f_k(n \mod \ell_k) \]
con condizioni iniziali
\[ f_k(0)=1, f_k(1)= \ldots = f_k(k-1)=0, f_k(k)= f_k(k+1)=1 \]
inoltre se \( k+1 < n < k(k+1)=\ell_k \) allora abbiamo che
\[ f_k(n) \in \{0,1\} \]
dove \( f_k(n) = 1 \) se \( k \mid n \) o \( (k+1) \mid n \) e \(f_k(n)=0 \) altrimenti.

Inoltre sicuramente \( f_1(n) = \left \lfloor \frac{n}{2}+1 \right \rfloor \) e \(f_k(n-k+1) = 0 \) se \( k > \frac{n+1}{2} \)
Edit:
In definitiva dobbiamo dimostrare che
\[ \sum_{k=1}^{n} f_k(n-k+1) = \sum_{k=1}^{ \left \lfloor \frac{n+1}{2} \right \rfloor} f_k(n-k+1) = n \]
o equivalentemente
\[ n = \sum_{k=1}^{ \left \lfloor \frac{n+1}{2} \right \rfloor} \left \lfloor \frac{n-k+1}{k(k+1)} \right \rfloor + \sum_{k=1}^{ \left \lfloor \frac{n+1}{2} \right \rfloor} f_k(n-k+1 \mod k(k+1) ) \]

[axpgn]

Mi sono già perso alla prima riga ...

Testo nascosto, fai click qui per vederlo

Prima di tutto hai una $g_k(n)$ per ogni $k$? Ma soprattutto i modi di rappresentare $n$ come somma di $k$ e $k+1$ sono solo uno se $n$ è dispari ($n=2k+1$) o nessuno se $n$ è pari; intendevi questo o mi sono perso qualcosa?

Piccolo hint:

Testo nascosto, fai click qui per vederlo

Colui che ha trovato la soluzione, ha notato una particolarità nell'esempio che ho riportato e ha pensato che non fosse una coincidenza ...

Cordialmente, Alex

[3m0o]

Testo nascosto, fai click qui per vederlo

No! Non intendevo quello, ad esempio \( g_1(n) = F_{n+1} \) dove \(F_{n} \) è l'\(n\)-esimo numero di fibonacci.

Infatti \(g_1(n) = g_1(n-1) + g_1(n-2) \), infatti i modi di scrivere \( n \) usando soltanto degli \(1\) e dei \(2\) si può ottenere solo se si può scrivere \(n-1\) usando soltanto degli \(1\) e dei \(2\) oppure \(n-2\) usando soltanto degli \(1\) e dei \(2\) e poi sommi \(1\) e \(2\) rispettivamente.

Ad esempio \( g_1(4)= 5 \), perché \( 4 = 1+1+1+1 \), che corrisponde alla soluzione \( (4,0)\) all'equazione \(x+2y=4 \). Le tre soluzioni (distinte), \( 2+1+1=1+2+1= 1+1+2\) corrispondono alla soluzione unica \((2,1) \) e la soluzione \( 2+2 \) corrisponde alla soluzione \( (0,2)\). Il problema è che \(g_k(n) \) considera distinte soluzioni che sono la medesima per l'equazione.
Fondamentalmente per \( g_k(n) \) l'ordine conta, per \(a_k\) l'ordine non conta! Per ordine intendo che le soluzioni negli interi non negativi di \( k x + (k+1) y = n \) rappresentano sommare \(x \)-volte \(k \) e poi sommare \(y\)-volte \(k+1\) per ottenere \(n\). Il problema è che \(a_k\) non conta tutte le permutazioni di in quale ordine sommo le \(x\)-volte \(k\) e le \(y\)-volte \(k+1\) mentre \(g_k(n)\) invece sì.

Edit:

Testo nascosto, fai click qui per vederlo

Inoltre scrivo \(g_k(n) \) perché in realtà gli \(a_j \) dipendono da \(n\) e sarebbe più corretto scrivere \( a_j(n)\) per ogni \( 1 \leq j \leq n \).

[axpgn]

Testo nascosto, fai click qui per vederlo

Allora, se ho capito bene, intendevi dire che $g_k(n)$ conta i modi di rappresentare $n$ usando soltanto $k$ e/o $k+1$; se è così potevo usarlo l'avverbio

Magari poi proseguo per capire il resto ...

Cordialmente, Alex