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

[giammaria2]

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

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

[dan952]

@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)

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$

[giammaria2]

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

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

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:

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]

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:

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]

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

[3m0o]

Esatto io invece dell'avverbio ho usato il plurale di \(k\) e di \(k+1\) ma nella mia testa

[dan952]

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

(1,3) == 1+3=4
(3,2) == 3+2=5

Cioè sommando le coppie di soluzioni si ottengono numeri crescenti? È questa la coincidenza?

[3m0o]

dan

Almeno per \(n=7\) sommando le coppie di soluzioni \((x,y)\) di tutte le equazioni si trovano tutti i numeri da 1 a 7 in qualche ordine

[axpgn]

@dan95
Yes

L'autore congettura $x+y=k$ per ogni $1<=k<=n$ e poi va avanti ...

[3m0o]

Fissiamo un \(n\) arbitrario.
Proposizione 1: Sia \( \ell > k \) e siano \((x_1,y_1 ) \) e \((x_2,y_2)\) soluzioni rispettivamente di \( \ell x_1 +(\ell+1)y_1 = n-\ell +1 \) e \( k x_2 +(k+1)y_2 = n-k+1 \) allora \( x_1+y_1 < x_2+y_2 \).

Dimostrazione:
Supponiamo che \(x_1 < x_2 \) allora
\[ \ell x_1 + (\ell +1 ) y_1 < k x_2 + (k+1) y_2 \]
da cui
\[ (\ell+1) x_1 + (\ell +1 ) y_1 < k x_2 + (k+1) y_2 + x_1 < k x_2 + (k+1)y_2 + x_2 \]
da cui
\[ (\ell+1) ( x_1 +y_1) < (k+1)(x_2+y_2) \]
da cui
\[ \frac{x_1+y_1}{x_2+y_2} < \frac{k+1}{\ell+1} < 1 \]
Se invece \(x_1 \geq x_2 \) allora \( y_1 < y_2 \) altrimenti
\[ \ell x_1 + (\ell +1) y_1 \geq \ell x_2 + (\ell + 1) y_2 \geq k x_2 +(k+1)y_2 \]
che è assurdo.
\[ \ell x_1 + \ell y_1 + y_1 < k x_2 + k y_2 + y_1 < kx_2 + ky_2 + y_2 \]
da cui
\[ \ell (x_1+y_2 ) < k(x_2+y_2) \]
pertanto
\[ \frac{x_1+y_1}{x_2+y_2} < \frac{k}{\ell} < 1 \]

Idea:

Ora sia \( a_k := \operatorname{card} \left( \{ (x,y) \in \mathbb{N}^2 : kx+(k+1)y = n-k+1\} \right) \). Sia inoltre \( m_k := \min\{ x+y : kx+(k+1)y = n-k+1\} \} \) se \(a_k \neq 0 \) e \(m_k = 0 \) se \( a_k = 0 \).
\( k_1 := \max_{1 \leq k \leq n} \{ k : a_k \neq 0 \} \) e ricorsivamente \( k_{i} := \max_{ 1 \leq k \leq k_{i-1} } \{ k : a_k \neq 0 \} \). Sia inoltre \( r = \operatorname{card} \{ k : a_k \neq 0 \} \leq n \).
Per la proposizione 1 abbiamo chiaramente \( m_{k_1} < m_{k_2} < \ldots < m_{k_r} \). Inoltre è immediato vedere che per ogni \( 1 \leq k \leq n \) abbiamo che \(1 \leq m_k \leq n \) poiché \(1 \leq x+y \leq kx+(k+1)y \leq n \).

Ad \( (a_1 ,\ldots, a_n ) \) associamo tramite una mappa \( \phi \) una funzione \( f: \{ 1 ,\ldots, n \} \to \{1,\ldots, n\} \)
\[ f(1)= f(1+1)= \ldots = f(n-k_1) = 0 \]
\[ f(n-k_1+1) = \ldots = f(n-k_2) = m_{k_1} \]
e così via
\[f(n-k_{r-1} +1) = \ldots = f(n-k_r) = m_{k_{r-1}} \]
\[ f(n - k_{r} +1 ) = \ldots = f(n)= m_{k_r} \]
Chiaramente \( f : \{ 1 ,\ldots, n\} \to \{ 1 , \ldots, n \} \) è una funzione crescente, inoltre da \(f\) si può passare alla successione \( (a_1,\ldots,a_n) \) via una biiezione \( \psi\) tra le funzioni crescenti \( \{ 1 ,\ldots, n\} \to \{ 1 , \ldots, n \} \) e le soluzioni negli interi non negativi all'equazione \( x_1 + \ldots + x_n = n \) dunque abbiamo che \( a_1 + \ldots + a_n = n \).

Non ho voglia di trovare esplicitamente \( \psi \), ma direi che così funziona.

Edit: nel esempio con \(n = 7\) abbiamo che \( r= 3, k_1 = 4, k_2=2, k_3=1 \) e \(m_{k_1}=1, m_{k_2}=2, m_{k_3} = 4 \) da cui
\[ f(1)=f(2)=f(3)= 0 , f(4)=f(5)=1, f(6)=2, f(7) = 4 \].
e si trova tramite la biiezione
\[ (4,2,0,1,0,0,0) \]

Mi manca da dimostrare che \( a_k = m_k \) per ogni \(1 \leq k \leq n \).

[dan952]

È una bozza ma credo sia la strada giusta...

Claim.

Per due soluzioni diverse
non può valere $x+y=x'+y'$, quindi ogni somma identifica una soluzione.

$kx+(k+1)y=n-k+1$

$k'x'+(k'+1)y'=n-k'+1$

con $k$ e $k'$ non necessariamente diversi

$k(x+y)+y=n-k+1$

$k'(x'+y')+y'=n-k'+1$

Sottraendo la prima alla seconda otteniamo

$(k-k')(x+y)+y-y'=k'-k$

Se $k=k'$ allora $y=y'$

Se $k'>k$ allora il primo membro è negativo in quanto x+y>y e il secondo è positivo. Assurdo. In modo analogo si dimostra che due equazioni diverse non possono avere una stessa soluzione.








Procedo per induzione


Supponiamo che la tesi della "coincidenza" valga per i primi $n$ numeri naturali allora dimostriamo che vale anche per $n+1$.


Consideriamo l'equazione diofantea generica per il caso $n$ e sia $(x,y)$ soluzione, con $x \ne 0$

$kx+(k+1)y=n-k+1$

Da questa possiamo generare una nuova soluzione $(x'=x-1,y'=y+1)$ dell'equazione nel caso $n+1$


$kx+(k+1)y=n+1-k+1$

osserviamo che $x+y=x'+y'$


Quindi tutte le somme si conservano oltre che le soluzioni del tipo $(0,y)$ (ecco questo va dimostrato un po' meglio), infatti sia

$kx+(k+1)y=n-k+1$

l'equazione che ha soluzione $(0,y')$ in $n+1$ questa corrisponde alla soluzione $(y',0)$, infatti

$(k+1)y'+(k+2) 0=n+1-(k+1)+1$


e si aggiunge la soluzione $(n+1,0)$ della prima equazione diofantea

$x+2y=n+1$

Dunque siccome le somme si conservano passando da $n$ a $n+1$ e si aggiunge la soluzione $(n+1,0)$, per ipotesi induttiva si ottiene la tesi in quanto non si hanno più $n$ somme diverse ma $n+1$ e quindi $n+1$ soluzioni in totale.

[3m0o]

"3m0o":

Mi manca da dimostrare che \( a_k = m_k \) per ogni \(1 \leq k \leq n \).

Credo che questo sia immediato dalla definizione di \(f\).

Edit:

E mi manca da dimostrare questa cosa perché credo che la biiezione \( \psi \) mi mappi \( f \) a
\[ (m_n, m_{n-1}, \ldots, m_1 ) \]

[axpgn]

@3m0o

Fino a "Idea" ci sono, per le definizioni ancora ancora ma poi mi perdo definitivamente

@dan95

Ho delle perplessità, per esempio dici $x+y>y$ ma potrebbe essere $x=0$ ma è sull'induzione che ho il dubbio maggiore perché quando passi a $n+1$ non aggiungi solo una nuova equazione ma modifichi TUTTE le precedenti quindi la premessa induttiva non vale più ... IMHO

Cordialmente, Alex

P.S.: Penso che per il futuro dovrò limitarmi a qualcosa di più "semplice" (ossia al mio livello) perché non ce la faccio più a starvi dietro

[dan952]

@Alex

Perplessità 1)

Se $x=0$ allora $x'+y'=y$ da cui se $y-y'=x'
$(k'-k)(x'+y')+x'=k-k' \Rightarrow (x'+y')+\frac{x'}{k'-k}=-1$

Ora per ipotesi vale $k'>k$ quindi al primo membro abbiamo due addendi positivi al secondo -1, assurdo

Altrimenti se $y'=0$ allora $x'=y$ ovvero le soluzioni sono invertite quindi

$(k'-k)x'+x'=k-k'$

e la tesi segue per lo stesso motivo.

Perplessità 2)

Da quanto detto prima le somme identificano una soluzione tuttavia sappiamo dalla prima equazione che una somma non può eccedere il valore $n$ inoltre essendo tutte diverse le somme e i loro valori devono essere compresi tra 1 e n. Questo è vero per ipotesi induttiva cioè le somme (e quindi il numero di soluzioni totali) sono esattamente $n$ nel caso $n$. Dobbiamo dimostrarlo ora per $n+1$ abbiamo visto che anche qui una soluzione $(x,y)$ con $x \ne 0$ nel caso $n$ genera una soluzione $(x',y')$ per $n+1$, e le soluzioni $(0,y)$ si trasformano in $(y,0)$ in $n+1$. Detto questo le soluzioni così generate sono $n$ e per ipotesi induttiva le loro somme vanno da 1 a n senza ripetizioni e quindi non ce ne possono stare altre (perché sono esaustive) se non quella che mi dà come somma n+1 che è proprio (n+1,0).

[Luknik02]

Ciao a tutti. Avendo anche io notato il pattern che sommando le soluzioni si ottengono numeri crescenti, ne propongo un altro che ho notato poco fa importando questo problema su Mathematica.

In particolare, fisso \(\displaystyle n\in\mathbf{N} \) e considero \(\displaystyle a_1(n),a_2(n),\dots,a_n(n) \) come il numero di soluzioni intere non negative rispettivamente delle equazioni:
\(\displaystyle
x+2y=n \)
\(\displaystyle 2x+3y=n-1 \)
\(\displaystyle \vdots \)
\(\displaystyle nx+(n+1)y=1 \)
Allora si ha che:

\(\displaystyle \Bigl|a_k(n)-\frac{n}{k(k+1)}\Bigr|\leq 1 \mbox{ $\forall k\in\mathbf{N}$ tale che $1\leq k\leq n$} \)
Ad esempio, per \(\displaystyle n=10000 \) utilzzando il seguente codice in Mathematica:

f[n_]:=Table[{Dimensions[Solve[k*x+(k+1)*y==n-k+1,{x,y},NonNegativeIntegers]][[1]],k*(k+1),N[Dimensions[Solve[k*x+(k+1)*y==n-k+1,{x,y},NonNegativeIntegers]][[1]]-n/(k*(k+1))]},{k,1,n}]//TableForm

ottengo una tabella dove nella prima colonna ci sono il numero di soluzioni delle rispettive \(\displaystyle n \) equazioni, nella seconda colonna \(\displaystyle k(k+1) \) e nella terza colonna lo scarto fra la prima colonna ed \(\displaystyle \frac{n}{k(k+1)} \). I primi valori approssimati sono:
5001 2 1
1667 6 0.333333
833 12 -0.333333
500 20 0.
334 30 0.666667
238 42 -0.0952381
178 56 -0.571429
139 72 0.111111
111 90 -0.111111
91 110 0.0909091
76 132 0.242424
64 156 -0.102564
55 182 0.0549451
48 210 0.380952
41 240 -0.666667
37 272 0.235294
33 306 0.320261
29 342 -0.239766
26 380 -0.315789
24 420 0.190476
22 462 0.354978

Probabilmente è facilmente dimostrabile, però credo sia una cosa perlomeno simpatica! Buon proseguimento!

[axpgn]

@dan95

Premesso che non sono del tutto convinto, assumendo per vero il tuo claim tu dimostri che se esiste una soluzione $(x,y)$ di una delle equazioni tale per cui sia $x+y=k$ questa è unica per quel $k$, però non è dimostrato che per ogni $k$ esista una coppia che sia anche soluzione di una delle equazioni.

Ma il mio dubbio principale rimane sull'induzione; questa si basa sul fatto che la premessa del passo induttivo (assunzione validità del caso $n$) non cambi quando si analizza il caso $n+1$ o comunque, se cambia, rimanga valida prima di validare il caso $n+1$; e non è così nella tua soluzione ovvero dato che nel caso $n+1$ tutte le prime $n$ equazioni sono diverse da quelle del caso $n$ non puoi supporre a priori che abbiano anch'esse $n$ soluzioni e per di più "ricoprano" ogni $k$ da $1$ a $n$.

IHMO


Cordialmente, Alex