Un problema della gara a squadre
Un problema della gara a squadre
visto che se ne è parlato in questi giorni, lo ripropongo qua, chiedendo ovviamente una dimostrazione, non il solo risultato .
pregherei gentilmente gli "esperti" (leggi:(in particolare)euler) di non postare subito una soluzione, ma di lasciare un po' di tempo ai "meno esperti" per fare qualche tentativo.
dati $ a $ e $ b $ interi positivi, diciamo anche $ \geq2 $, tali che $ MCD(a,b)=1 $, determinare, se esiste, il più grande intero positivo non esprimibile nella forma $ ax+by $, con $ x $ e $ y $ interi non-negativi.
pregherei gentilmente gli "esperti" (leggi:(in particolare)euler) di non postare subito una soluzione, ma di lasciare un po' di tempo ai "meno esperti" per fare qualche tentativo.
dati $ a $ e $ b $ interi positivi, diciamo anche $ \geq2 $, tali che $ MCD(a,b)=1 $, determinare, se esiste, il più grande intero positivo non esprimibile nella forma $ ax+by $, con $ x $ e $ y $ interi non-negativi.
- HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
Se Supponiamo che tale numero esista: esso è maggiore di tutti gli altri
e lo indichiamo con M; quindi si ha che M+1=A1x+B1y, mentre M+2=A2x+B2y; pertanto M+2-M-1=1=(A2-A1)x+(B2-B1)y=1.
Si può procedere applicando le formula delle frazioni continue sulle congruenze di primo grado con i coefficenti coprimi.
Oppure si può procedere in tal modo, sia per l'omogeneità dell'espressione, x=x e y=x+1.
Sia A2-A1=D1, mentre B2-B1=E1; quindi si ottiene che D1x=1-E1(x+1) (mod n)
Ovviamente D1 e E1 sono coprimi.
(D1+E1)x=1-E1, pertanto essendo x intero, 1=E1 mod (D1+E1).
Devo correre e quindi posterò dopo la concluzione...
P.S. Complimenti vivissimi a Cesenatico-men! e grazie a Talpuz per avermi segnalato l'errore...ahi, la primavera
e lo indichiamo con M; quindi si ha che M+1=A1x+B1y, mentre M+2=A2x+B2y; pertanto M+2-M-1=1=(A2-A1)x+(B2-B1)y=1.
Si può procedere applicando le formula delle frazioni continue sulle congruenze di primo grado con i coefficenti coprimi.
Oppure si può procedere in tal modo, sia per l'omogeneità dell'espressione, x=x e y=x+1.
Sia A2-A1=D1, mentre B2-B1=E1; quindi si ottiene che D1x=1-E1(x+1) (mod n)
Ovviamente D1 e E1 sono coprimi.
(D1+E1)x=1-E1, pertanto essendo x intero, 1=E1 mod (D1+E1).
Devo correre e quindi posterò dopo la concluzione...
P.S. Complimenti vivissimi a Cesenatico-men! e grazie a Talpuz per avermi segnalato l'errore...ahi, la primavera
Ultima modifica di HumanTorch il 09 mag 2005, 18:02, modificato 2 volte in totale.
hmmm
intanto ti faccio notare che nell'espressione $ ax+by $ sono $ x $ e $ y $ che variano, mentre $ a $ e $ b $ sono fissi (mentre mi sembra che tu abbia capito il contrario)
in ogni caso questa deduzione:
intanto ti faccio notare che nell'espressione $ ax+by $ sono $ x $ e $ y $ che variano, mentre $ a $ e $ b $ sono fissi (mentre mi sembra che tu abbia capito il contrario)
in ogni caso questa deduzione:
è sbagliata, perchè è vero che $ x,y>=2 $ (nella tua notazione, in cui hai scambiato a e b con x e y rispetto alla mia), ma $ a_2-a_1 $ e $ b_2-b_1 $ possono benissimo essere negativi..HumanTorch ha scritto:ma, essendo tutti i valori possibili positivi o, comunque,non negativi, 1 può essere ottenuto unicamente 0+1 o 1+0, quindi, essendo sia x che y maggiore di 2 per ipotesi, ciò non si può verificare in N.
questa magari la capirete da grandi...
In nome di Frobenius, che modi son mai questi, Talpuzio caro?!?
il massimo numero non scrivibile è ab-a-b.
1°parte: ab-a-b non è scrivibile come combinazione lineare positiva di a e b.
DIM.
ab-a-b=ax+by
ab=a(x+1)+b(y+1)
ab-b(y+1)=a(x+1)
b(a-y-1)=a(x+1)
dato che a e b sono primi tra loro, a|(a-y-1), e siamo ad un assurdo perchè a-y-1 è più piccolo di a.
2°parte: tutti i numeri>ab-a-b sono scrivibili come combinazione linare positiva di a e b.
DIM.
ax+by=ab-a-b+k
(come prima)
a(x+1)-b(a-y-1)=k
che possiamo ricondurre all'equazione diofantea
aX-bY=k
che noi sappiamo avere soluzioni positive(che si possono trovare anche facilmente) 0<=X<b e 0<=Y<a (la dimostrazione di ciò è nota, se serve in caso poi la posto)
dato che Y<a, con le sostituzioni
x+1=X ==> x=X-1
a-y-1=Y ==> y=a-Y-1
si ottengono i valori di x e y maggiori o uguali a 0 cercati.
Ciao a tutti
FRANCESCO
1°parte: ab-a-b non è scrivibile come combinazione lineare positiva di a e b.
DIM.
ab-a-b=ax+by
ab=a(x+1)+b(y+1)
ab-b(y+1)=a(x+1)
b(a-y-1)=a(x+1)
dato che a e b sono primi tra loro, a|(a-y-1), e siamo ad un assurdo perchè a-y-1 è più piccolo di a.
2°parte: tutti i numeri>ab-a-b sono scrivibili come combinazione linare positiva di a e b.
DIM.
ax+by=ab-a-b+k
(come prima)
a(x+1)-b(a-y-1)=k
che possiamo ricondurre all'equazione diofantea
aX-bY=k
che noi sappiamo avere soluzioni positive(che si possono trovare anche facilmente) 0<=X<b e 0<=Y<a (la dimostrazione di ciò è nota, se serve in caso poi la posto)
dato che Y<a, con le sostituzioni
x+1=X ==> x=X-1
a-y-1=Y ==> y=a-Y-1
si ottengono i valori di x e y maggiori o uguali a 0 cercati.
Ciao a tutti
FRANCESCO
perfetto
c'è solo una quisquillia: se trovi X=0, allora ti viene x=-1, che non è non negativo
cmq è un'idiozia, perchè se viene X=0 vuol dire che k è negativo, e quindi basta
altre soluzioni? (in particolare, qualcuno ha capito la soluzione dell'ungherese? )
@euler: sappi che ho apprezzato il gesto, mi auguro che la tua comprensività non finisca qua
c'è solo una quisquillia: se trovi X=0, allora ti viene x=-1, che non è non negativo
cmq è un'idiozia, perchè se viene X=0 vuol dire che k è negativo, e quindi basta
altre soluzioni? (in particolare, qualcuno ha capito la soluzione dell'ungherese? )
@euler: sappi che ho apprezzato il gesto, mi auguro che la tua comprensività non finisca qua
Nella gara a squadre partecipava anche una squadra di ungheresi "fuori classifica", e risolse quel problema, in verità il caso particolare $ 23x+17y=n $
Comunque c'era stato, se ricordate, un errata corrige, che diceva che i numeri da cercare erano interi positivi quindi, come mi disse Bonizzato dopo la gara, $ 23*17 $,era la risposta, lui aveva fatto una tabella con le congruenze che lo dimostrava e credo proprio avesse ragione.
Tra l'altro non è stato l'unico errore della gara a squadre, ho perso un'ora a stimare $ [253\log_5(253)]+1 $ e non ho concluso perchè il testo era sbagliato e non riportava l'ipotesi che quel numero dovesse finire in zero
Comunque c'era stato, se ricordate, un errata corrige, che diceva che i numeri da cercare erano interi positivi quindi, come mi disse Bonizzato dopo la gara, $ 23*17 $,era la risposta, lui aveva fatto una tabella con le congruenze che lo dimostrava e credo proprio avesse ragione.
Tra l'altro non è stato l'unico errore della gara a squadre, ho perso un'ora a stimare $ [253\log_5(253)]+1 $ e non ho concluso perchè il testo era sbagliato e non riportava l'ipotesi che quel numero dovesse finire in zero
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara