Da febbraio2010 con furore

[jordan]

a) Trovare tutti i primi (p,q) tali che $ \displaystyle \frac{p^2+q^2-1}{pq} $ è intero.

b) Esistono infinite coppie di interi (a,b) con 1<a<b tali che $ \displaystyle \frac{a^2+b^2-1}{ab} $ è intero?

c) Con gli stessi vincoli su (a,b) del punto precedente, quali valori interi può assumere $ \displaystyle \frac{a^2+b^2-1}{ab} $ ?

[dario2994]

d): Dato k naturale esistono infinite coppie (a,b) con i soliti vincoli tali che $ $ \frac{a^2+b^2-1}{ab}=k $ ?
e) Trovare tutte le coppie (a,b) tali che $ $ \frac{a^2+b^2-1}{ab}=k $

p.s. il d l'ho risolto, l'è no ma ad occhio si può fare con metodi olimpici o quasi (almeno spero)

[jordan]

I vincoli infatti servono soltanto ad escludere i casi banali E i punti d) ed e) sono fattibili e vengono quasi immediatamente ai precedenti

[ndp15]

b) con la fattorizzazione furba che ho già segnalato nel thread sulla gara di Febbraio (e che poi è la stessa che danno nella soluzione ufficiale), noto che $ a \mid (b-1)(b+1) $ e $ b \mid (a-1)(a+1) $ ; mi basta quindi scegliere $ \displaystyle a $ intero qualsiasi e $ b=a+1 $ ottenendo $ \displaystyle \frac {2a^2+2a}{a^2+a} $ che è ovviamente intero per qualsiasi scelta di $ \displaystyle a $ (ovviamente rispettando le condizioni).

c) sempre ricordando quanto detto nel punto b riguardo la fattorizzazione, provo a porre $ b=a^2-1 $ e vediamo se accade qualcosa di bello: $ \displaystyle \frac {a^2(a^2-1)}{a(a^2-1)}=a $ (*) e questa è cosa buona è giusta.

d)
Non ci sono soluzioni (né tantomeno sono infinite) per il caso $ \displaystyle k=0 $, mentre per $ \displaystyle k \neq 1 $

HO EDITATO

[dario2994]

Uhm... c'è qualcosa che non mi quadra... o ho toppato io completamente oppure ce ne sono proprio infinite... o perlomeno ce ne sono xD
Poi scusa... nel punto c) dici che c'è n'è almeno 1... nel punto d) perchè non c'è ne' più manco 1???

p.s. POTD su Mathlinks oggi
p.p.s. comunque non mi pare che d) ed e) derivino da b,c) tanto banalmente :|

[ndp15]

Uhm... c'è qualcosa che non mi quadra... o ho toppato io completamente oppure ce ne sono proprio infinite... o perlomeno ce ne sono xD
Poi scusa... nel punto c) dici che c'è n'è almeno 1... nel punto d) perchè non c'è ne' più manco 1???

Io non ho detto che non sono infinite, anzi!
Nel punto c ho affermato che se prendo a e b come descritto, la frazione è uguale ad a, quindi è intera come richiesto. (es. a=3 b=8 (3^2+8^2-1)/( 3*8 )=3 ).
Nel punto d ho dimostrato che per ogni k naturale diverso da 0 e 1 esistono infinite soluzioni, costruite come spiegato. Se k=0 non ci sono soluzioni ( ricordando 1<a<b), se k=1 ci devo pensare

[dario2994]

Sono io che ho frainteso una tua frase (perchè ti sei perso un verbo mi sa).
Comunque a me pare che quella frazione cambi... se al posto di a piazzo un suo multiplo :|
In particolare se mando a in ka la frazione diviene di conseguenza ka...

[ndp15]

In particolare se mando a in ka la frazione diviene di conseguenza ka...

E direi che hai anche ragione, anche se mi riservo di ricontrollare tutto (anche i verbi mancanti) più tardi che ora non ho tempo.

[jordan]

e) Trovare tutte le coppie (a,b) tali che $ $ \frac{a^2+b^2-1}{ab}=k $

Sia $ k \in \mathbb{N}_0 $ fissato e $ S_k:=\{(x,y)\in \mathbb{N}_0^2:x^2+y^2=kxy+1\} $. Se $ a=b $ allora $ a^2\mid 2a^2-1\implies a=1 $. Se $ a=1 $ invece abbiamo banalmente $ b=k $ per cui d'ora in poi assumiamo che $ 1<a<b $.

Se $ k=1 $ dovrebbe valere $ a^2+b^2=ab+1 $, che è equivalente a $ 1\le (a-b)^2=a^2+b^2-2ab=1-ab\le 0 $, per cui $ S_1=\{(1,1)\} $.

Se $ k=2 $ dovrebbe valere $ a^2+b^2-1=2ab $ cioè $ (a-b)^2=1 $, per cui $ S_2=\{(x,x+1)\} $ dove $ x \in \mathbb{N}_0 $ varia tra gli interi positivi.

Sia $ k>2 $ fissato. Vogliamo dimostrare che $ (a,b)\in S_k $ (con il vincolo $ a<b $) se e solo se esiste un intero non negativo $ i $ tale che $ a=x_i,b=x_{i+1} $, dove $ x_0=1,x_1=k,x_{n+1}=kx_n-x_{n-1} $.

Innanzitutto la sequenza degli $ \{x_i\}_{i \in \mathbb{N}} $ è strettamente crescente, infatti $ x_0<x_1 $, e supposto che la disuguaglianza $ x_i<x_{i+1} $ sia verificata, abbiamo $ x_{i+1}<x_{i+2}=kx_{i+1}-x_i $ se e solo se $ x_i<(k-1)x_{i+1} $ che è vera per ipotesi induttiva.

Adesso verifichiamo che effettivamente $ (x_i,x_{i+1}) \in S_k $ per ogni $ i \in \mathbb{N}_0 $. Banalmente $ (x_0,x_1)\in S_k $ e supposto che $ (x_i,x_{i+1}) \in S_k $ allora $ x_i^2+x_{i+1}^2=kx_ix_{i+1}+1 $. Adesso $ (x_{i+1},x_{i+2})\in S_k $ se e solo se $ (kx_{i+1}-x_i)^2+x_{i+1}^2=kx_{i+1}(kx_{i+1}-x_i)+1 $ che è equivalente a $ (k^2+1)x_{i+1}^2+x_i^2-2kx_ix_{i+1}=k^2x_{i+1}^2-kx_ix_{i+1}+1 $ cioè esattamente $ (x_i,x_{i+1})\in S_k $ e l'induzione è completa.

Resta da dimostrare che sono effettivamente $ S_k $ non contiene altre coppie $ (a,b) $ che non siano di quella forma: assumiamo che $ (a,b)\in S_k $ con $ 1\le a<b $. Vogliamo dimostrare che anche $ (kb-a,a)\in S_k $. Per ipotesi $ b $ è una radice di $ p(x):=x^2-kxa+a^2-1 $; la somma delle due radici è intera e il prodotto è positivo per cui l'altra radice $ ka-b \in \mathbb{N}_0 $. Inoltre se fosse $ ka-b\ge a $ allora $ a^2+b^2>a^2+b^2-1=kab\ge \frac{a+b}{a}ab=ba+b^2 $ assurdo, per cui $ 1\le ka-b\le a-1 $.

Infine effettivamente vale $ (ka-b,a)\in S_k $, infatti $ (ka-b)^2+a^2=ka(ka-b)+1 $ se e solo se $ (a,b)\in S_k $.

Questo procedimento creerà degli elementi di $ S_k $ sempre più piccoli, e questo algoritmo deve necessariamente terminare nella coppia $ (1,k) $.

Ciò dimostra che quella sequenza ricorsiva è in grado di trovare tutti e soli gli elementi di $ S_k $.

Per andare fino in fondo: il polinomio caratteristico associato a quella ricorsione è $ x^2-kx+1=(x-\frac{k}{2})^2+1-\frac{k^2}{4} $ per cui abbiamo le due radici $ y_1:=\frac{1}{2}(k+\sqrt{k^2-4}),y_2:=\frac{1}{2}(k-\sqrt{k^2-4}) $. Siano $ (\alpha,\beta)\in \mathbb{R}^2 $ la soluzione del sistema:

$ \alpha y_1^0+\beta y_2^0 =x_0=1 $
$ \alpha y_1^1+\beta y_2^1=x_1=k $.

Otteniamo $ \displaystyle (\alpha,\beta)=\left(\frac{\sqrt{k^2-4}+k}{2\sqrt{k^2-4}},\frac{\sqrt{k^2-4}-k}{2\sqrt{k^2-4}}\right) $ da cui :
$ \displaystyle x_n=\left(\frac{\sqrt{k^2-4}+k}{2\sqrt{k^2-4}}\right)\left(\frac{k+\sqrt{k^2-4}}{2}\right)^n+\left(\frac{\sqrt{k^2-4}-k}{2\sqrt{k^2-4}}\right)\left(\frac{k-\sqrt{k^2-4}}{2}\right)^n $, e quindi $ S_k:=\{(x_n,x_{n+1})\} $ dove $ n $ varia in $ \mathbb{N} $.


Ps. Ok, credo di essermi risolto tutti i punti con una botta sola Spero sia utile a qualcuno, e good night!

[dario2994]

Woooooo, complimenti :)
L'idea è uguale alla mia, ma io avevo scomodato le equazioni di Pell senza motivo, questo è molto più figo ed è un metodo che in effetti torna utile spessissimo.
Davvero complimenti :) Tra l'altro è una delle soluzioni più chiare che abbia mai visto (pur essendo tutto fuorchè banale)