OliForum Matematico

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.