Soluzioni

[axpgn]

@dan95

Testo nascosto, fai click qui per vederlo

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

[dan95]

Devo ammetterlo mi sono spiegato molto male...

Testo nascosto, fai click qui per vederlo

però non è dimostrato che per ogni k esista una coppia che sia anche soluzione di una delle equazioni.

Viene dimostrato per induzione.


Ma parliamo della perplessità della dimostrazione per induzione...

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.

Dimostriamo che se $(X,Y)$ con $X \ne 0$ è soluzione dell'equazione

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

Allora $(X-1,Y+1)$ è soluzione dell'equazione

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

Infatti

$k(X-1)+(k+1)(Y+1)=kX-k+(k+1)Y+k+1=kX+(k+1)Y+1=(n+1)-k+1$

E si ha $X-1+Y+1=X+Y$. Quindi come possiamo vedere tutte le soluzioni $(X,Y)$ in $n$ vengono trasformate in $(X-1,Y+1)$ in $n+1$.

Ma le soluzioni del tipo $(0,Y)$? Queste diventano $(Y,0)$ in $n+1$ infatti da

$k\cdot 0 +(k+1)Y=n-k+1$

si ricava

$(k+1) Y + (k+2) \cdot 0 = (n+1)-(k+1)+1$

Ma quante erano le soluzioni nel caso $n$? Erano esattamente $n$ per ipotesi induttiva e da quanto detto almeno $n$ lo sono anche nel caso $n+1$ alle quali si aggiunge $(n+1,0)$.


Torniamo alle somme per dimostrare che queste $n+1$ soluzioni sono esaustive nel caso $n+1$...

Le somme da 1 a n le eredità dal caso $n$ perché

$X-1+Y+1=X+Y$ e $0+Y=Y+0$

a cui si aggiunge la somma $n+1+0=n+1$, quindi con i Claim abbiamo dimostrato che ad ogni soluzione corrisponde una somma non ripetuta (non ci sono due soluzioni che danno la stessa somma) e per ipotesi induttiva ad ogni somma (da 1 a n) corrisponde una soluzione $(X-1,Y+1)$ o $(Y,0)$ in $n+1$ più la somma $n+1$ che corrisponde alla sola soluzione $(n+1,0)$ (Claim). Quindi abbiamo $n+1$ somme che da quanto detto corrispondono alle $n+1$ soluzioni totali poiché chiaramente non esistono soluzioni la cui somma sia maggiore di $n+1$.

[axpgn]

Oh, questa è un gran bella dimostrazione, bravo!

Vedi che non è stato sufficiente assumere per vera l'ipotesi induttiva ma hai dovuto dimostrare che rimanesse vera

Benissimo però ...

Testo nascosto, fai click qui per vederlo

Sarò pignolo, ma rimane ancora il problema dell'esistenza delle soluzioni, a mio parere

Cordialmente, Alex

[dan95]

Testo nascosto, fai click qui per vederlo

L'esistenza è garantita dall'ipotesi induttiva perché le nuove soluzioni le abbiamo costruite partendo dal caso precedente facciamo un esempio:

$n=5$

$x+2y=5 \rightarrow (1,2), (3,1),(5,0)$

$2x+3y=4 \rightarrow (2,0)$

$3x+4y=3 \rightarrow (1,0)$

$4x+5y=2 \rightarrow no\ \ soluzioni$

$5x+6y=1 \rightarrow no\ \ soluzioni$

Caso $n=6$

$x+2y=6 \rightarrow (1-1=0,2+1=3), (3-1=2,1+1=2), (5-1=4,0+1=1),(6,0)$

$2x+3y=5 \rightarrow (2-1=1,0+1=1)$

$3x+4y=4 \rightarrow (1-1=0,0+1=1)$

$4x+5y=3 \rightarrow no\ \ soluzioni$

$5x+6y=2 \rightarrow no\ \ soluzioni$

$6x+7y=1 \rightarrow no\ \ soluzioni$

[axpgn]

Testo nascosto, fai click qui per vederlo

Ma non hai la garanzia che non ce ne siano altre
È un loop

Mi spiego meglio ...
Con l'induzione hai dimostrato che se $n$ equazioni hanno $n$ soluzioni allora $n+1$ equazioni ne hanno sicuramente $n+1$ di soluzioni.
Che siano uniche lo hai dimostrato col claim che però è legato a $k$ perciò per completare occorre dimostrare che per ogni $k$ esiste una soluzione di un'equazione ... insomma siamo in loop ...

Cordialmente, Alex

[dan95]

Testo nascosto, fai click qui per vederlo

occorre dimostrare che per ogni k esiste una soluzione di un'equazione

Ma questo è garantito dall'ipotesi induttiva, infatti se per il caso $n$ ad ogni $k$ da 1 a n corrisponde un soluzione per ipotesi induttiva anche per il cosa $n+1$ perché le soluzioni in questo caso si costruiscono partendo dal caso precedente e le somme si conservano

$(X-1)+(Y+1)=X+Y=k$
$0+Y=Y+0=k$

Con $1 \leq k \leq n$, in aggiunta abbiamo $k=n+1$ con la soluzione nuova $(n+1,0)$. Ce ne sono altre? No, perché dal Claim sappiamo che ad ogni coppia di una soluzione corrisponde una ed una sola somma, tuttavia sappiamo anche che $k=X+Y \leq X+2Y=n+1$ ma con l'ipotesi induttiva abbiamo coperto tutti valori dell'intervallo da 1 a n e con la soluzione nuova anche $k=n+1$, questi valori non si ripetono appunto (Claim).