Un problema della gara a squadre

[talpuz]

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.

[HumanTorch]

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

[talpuz]

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:

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.

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

[HiTLeuLeR]

In nome di Frobenius, che modi son mai questi, Talpuzio caro?!?

[frengo]

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

[talpuz]

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

[Azarus]

altre soluzioni? (in particolare, qualcuno ha capito la soluzione dell'ungherese? )

Davvero strepitosa, gli ungheresi sono proprio una spanna sopra

[frengo]

... soluzione dell'ungherese?
di cosa stiamo parlando?

[Boll]

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

[pps]

a un certo punto della dimostrazione dell'ungherese mi sono perso... però era bellissima...

[frengo]

noooo...sono troppo curioso....
se qualcuno se le ricorda (anche in parte) LO PREGO DI POSTARLA!!!

Ciao a tutti

[Simo_the_wolf]

purtroppo era un po' complicata la dimostrazione e io personalmente non sono riuscito molto a seguire... dato anche lo stentato italiano dell'ungherese...
Comunque nel forum di combinatoria potete sbizzarrirvi a completare la dimostrazione del problema delle batterie!!!