Problema 20 Gara classi prime 2013

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
dodo3
Messaggi: 13
Iscritto il: 20 ago 2019, 09:50

Problema 20 Gara classi prime 2013

Messaggio da dodo3 » 25 ago 2019, 10:42

Il problema è il seguente:
Data una coppia (a, b) di numeri interi positivi, con a > b, conveniamo di chia- mare riduzione di (a, b), la coppia (b, r) ottenuta prendendo il secondo elemento b della coppia di partenza ed il resto r della divisione tra a e b.
Immaginiamo poi di partire da una coppia di numeri e di operare successive riduzioni, finch ́e questo `e possibile, cio`e finch ́e i due numeri rimangono stretta- mente positivi.
Ad esempio, partendo dalla coppia [math] si riesce ad operare 4 riduzioni perch ́e [math] → (8,3) → (3,2) → (2,1) → (1,0).
Qual `e il massimo numero di riduzioni che si riesce a fare partendo da una coppia (a, b) di interi positivi entrambi minori di 1000?
Non essendo riuscito a risolverlo, ho visto la soluzione ufficiale proposta, che è questa qui:
Testo nascosto:
La soluzione è 14.
[...]
Quello che ci viene chiesto `e essenzialmente di scegliere una coppia di numeri minori di 1000 in modo che, operando successive riduzioni, si arrivi ad una coppia di tipo (a, 0) compiendo piu` passi possibile.
Un modo per farsi un’idea di come operare `e quello di partire dalla fine e provare ad andare a ritroso. Piu` precisamente, prendiamo la coppia (1, 0), che `e la piu` piccola coppia di tipo (a, 0) e cerchiamo la coppia di numeri diversi piu` piccola possibile (in qualche senso) che ridotta mi dia (0, 1).
Dopo un po’ di tentativi probabilmente ci convinceremo che tale coppia `e (2, 1). Ripetendo il tentativo scopriremo poi che la minima coppia riducendo la quale trovo (2, 1) `e (2 + 1, 2), cio`e (3, 2).
Iterando il procedimento, siamo indotti a costruire la sequenza:
... → (pn+1,pn) → (pn,pn−1) → ... → (8,5) → (5,3) → (3,2) → (2,1) → (1,0)
dove la sequenza dei pn `e stata costruita usando la regola pn+1 = pn + pn−1 partendo da p1 = 1 e p2 = 2. L’unica eccezione `e l’ultima coppia che `e (p1, 0). Per come tale sequenza `e stata costruita, abbiamo ovviamente che la riduzione di (pn+1, pn) `e sempre (pn, pn−1), per cui il numero di riduzioni da operare sulla coppia (pn+1, pn) prima di fermarsi `e esattamente n.
Un calcolo esplicito dei pn mostra che p14 = 610, p15 = 987 e p16 = 1597, da cui segue che la piu` grande di tali coppie che ha entrambe le componenti inferiori a 1000 `e (p15,p14), per la quale serve operare esattamente 14 riduzioni prima di fermarsi.
Per completare la soluzione del problema ci rimane da dimostrare che le coppie del tipo descritto sopra sono quelle che si riducono piu` lentamente.
Piu` precisamente dimostriamo che, per ogni intero n ≥ 3, se a e b sono numeri interi tali che 0 < b < a < pn allora sulla coppia (a,b) si possono operare al massimo n − 2 riduzioni. Da questo, ovviamente, segue che se a e b sono entrambi minori di p16, cio`e di 1597, allora sulla coppia (a, b) si possono operare al massimo 14 riduzioni, che `e quanto ci basta per poter completare la soluzione del problema.
Dimostriamo quanto appena affermato per induzione.
La verifica che cio` vale per n = 3 e per n = 4 `e immediata. Osserviamo poi che, nel caso l’affermazione valga per ogni n da 3 fino a k, allora vale anche per n=k+1. Infatti, posto che sia 0<b<a<pk+1, nel caso che sia b<pk, la coppia che si ottiene riducendo (a, b) ha entrambi gli elementi minori di pk e quindi ricade subito nell’ipotesi induttiva. Se invece pk ≤ b < a < pk+1 allora a − b < pk+1 − pk = pk−1, per cui dopo due riduzioni si ottiene una coppia con entrambi gli elementi minori di pk−1, da cui si pu`o ancora concludere grazie all’ipotesi induttiva.
Possiamo quindi concludere, grazie al principio di induzione, che la nostra affermazione vale per ogni n ≥ 3.
(Copiando e incollando direttamente dal testo delle soluzioni i pedici sono tornati a livello della linea di base, ma penso si capisca che per pn, pn+1, p1,... si intende [math] ecc.).

La soluzione l'ho capita tutta fino a dove inizia il grassetto.
Infatti, data una coppia (a;b), con a>b di conseguenza, si ottiene con una riduzione (b;n) e poi (n;m).
Abbiamo quindi [math] e [math], e non capisco da qui come si faccia ad arrivare a dire che [math].
Se qualcuno riuscisse a spiegarmi questo passaggio mi farebbe un grande favore.

matpro98
Messaggi: 457
Iscritto il: 22 feb 2014, 18:42

Re: Problema 20 Gara classi prime 2013

Messaggio da matpro98 » 26 ago 2019, 15:18

Prova a capire quanto vale $n$ in funzione di $a$ e di $b$

dodo3
Messaggi: 13
Iscritto il: 20 ago 2019, 09:50

Re: Problema 20 Gara classi prime 2013

Messaggio da dodo3 » 26 ago 2019, 22:05

Forse ho capito.
In pratica, nella sequenza [math], n è il resto della divisione euclidea tra a e b, per cui, se indichiamo con q il quoziente di a:b :
a=bq+n, da cui n=a-bq, ed essendo q un fattore positivo n<a-b.

Poiché, in base a come sono costruite le coppie, m<n, per proprietà transitiva m<a-b.

È corretto come ragionamento?

matpro98
Messaggi: 457
Iscritto il: 22 feb 2014, 18:42

Re: Problema 20 Gara classi prime 2013

Messaggio da matpro98 » 28 ago 2019, 15:15

Esatto

dodo3
Messaggi: 13
Iscritto il: 20 ago 2019, 09:50

Re: Problema 20 Gara classi prime 2013

Messaggio da dodo3 » 30 ago 2019, 11:01

Ok, grazie mille del suggerimento.

Rispondi