Soluzioni

[3m0o]

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

[dan95]

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

(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

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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

[3m0o]

Testo nascosto, fai click qui per vederlo

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

[dan95]

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

Testo nascosto, fai click qui per vederlo

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]

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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

Edit:

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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

@dan95

Testo nascosto, fai click qui per vederlo

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

[dan95]

@Alex

Testo nascosto, fai click qui per vederlo

Perplessità 1)

Se $x=0$ allora $x'+y'=y$ da cui se $y-y'=x'<x'+y'$ allora segue che

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

Testo nascosto, fai click qui per vederlo

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:

Codice:

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!