Staffetta tdn

[jordan]

Problema 12:

Sia $ m \in \mathbb{N}_0 $ e $ (x_0, y_0) \in (\mathbb{N}_0)^2 $ la più piccola soluzione all'equazione $ x^2-3y^2=m $, che per ipotesi esiste. Si trovi trovi un upper bound di $ x_0 $.

Innanzitutto grazie di aver cambiato problema, anche se l'11 mi sembra molto interessante, e mi piacerebbe conoscere la soluzione un giorno..
Detto questo passiamo al tuo problemino, che ho impiegato tutto il pomeriggio per risolverlo

Ho aggiunto comunque al testo quotato l'ipotesi che almeno una soluzione esista, perchè per esempio $ x^2-3y^2=5 $ pare non ne abbia molte (3 non è un residuo quadratico modulo 5, e per la precisione se $ 2<p \mid m $ allora $ 12 \mid p^2-1 \leftrightarrow \left(\frac{3}{p}\right)=1 $) per cui non mi sembrava molto corretto definire un upper bound.

L'idea base comunque si fonda sul fatto che se $ (x_0,y_0) $ è soluzione, allora $ m=x_0^2-3y_0^2=(2x_0+3y_0)^2-3(x_0+2y_0)^2 $ per cui anche $ (2x_0+3y_0,x_0+2y_0) $ lo è. Definiamo per comodità $ z:=x+2y $: proviamo a definire il polinomio in due variabili $ p(t,z)=(z-2t)^2-3t^2-m $ e definiamo la successione degli $ \{a_i\}_{i \in \mathbb{Z}} $ rispetto al polinomio tale che $ a_0=y_0 $, $ a_{-1} \le a_1 $ sono le due radici di $ p(a_0,z) $. Si vede meravigliosamente che $ a_0 $ è una radice di $ p(a_1,z) $: bene, l'altra radice chiamiamola $ a_2 $. Ma anche $ a_1 $ è radice di $ p(a_2,z) $, allora definiamo $ a_3 $ l'altra radice. E così via, sia per indici negativi che positivi. Ma dato che $ 2\alpha-\sqrt{(2\alpha)^2-(\alpha^2-m)}<\alpha<2\alpha+\sqrt{(2\alpha)^2-(\alpha^2-m)} $, allora se $ p(\alpha,z)=0 $ e $ z_1<z_2 $ sono le sue radici sarà vero che $ z_1<\alpha<z_2 $. Ciò è equivalente ad affermare che la successione degli $ \{a_i\}_{i \in \mathbb{Z}} $ è strettamente crescente.
Ma $ a_0=y_0 $ non lo conosciamo, per cui poniamo wlog che sia il più piccolo termine non negativo della successione. Per come è stato definito il polinomio allora $ a_0^2-m=a_{-1}a_1<0 \implies y_0=a_0 < \sqrt{m} $. Ma allora $ x_0= \sqrt{ 3y_0^2+m } < 2\sqrt{m} $.

Aspetto tue notizie.. bel problema

Edit: Un bound un poco migliore qui ..(<-- cancellato sei un grande simo)
Edit2: l'esempio di sopra è addirittura impossibile modulo 3

[Simo_the_wolf]

Perchè inguaiarsi così tanto??

se $ (x_0, y_0) $ è soluzione allora lo è anche $ (2x_0-3y_0,2y_0-x_0) $. Sicuramente $ 2x_0-3y_0>0 $ poichè $ x_0 > \sqrt{3}y_0 $ quindi, per la minimalità della soluzione $ 2x_0-3y_0 \geq x_0 $ da cui ottengo
$ \displaystyle m=x_0^2-3y_0^2 \geq \frac 23 x_0^2 $ da cui la tesi (quella più forte).
L'uguaglianza si verifica nel caso $ m=6 $

[federiko97]

Uhm, beh, l'idea è che $ (x_0+\sqrt{3}y_0)(2-\sqrt{3}) $ è ancora una soluzione (cosa che stw sicuramente conosce ma che non nomina per non far capire al mondo come è arrivato alla sua soluzione..).

@ jordan: sì, scusa, dovevo specificare "nel caso che tale soluzione esista"

Adesso boh, credo che il Lupo abbia il dovere morale di postare un suo problema, o di risolvere quello che avevo postato prima di questo (che, vi assicuro, è abbastanza bellino).

[Simo_the_wolf]

Si ovviamente c'era quello sotto federiko. In realtà non ricordo ma forse è vero in generale che le soluzioni di $ x^2 - ay^2= m $ sono della forma $ x_n + \sqrt{a} y_n = (x_0 + \sqrt{a}y_0)( \chi_1 + \sqrt{a} \chi_2)^n $ dove $ \chi_1 ^ 2 - a \chi_2 ^2 =1 $ soluzione minimale.

Vabbè comunque se tocca a me non so che problema dare... ultimamente non ne so di difficili... Vi do questo in pasto che mi sbranerete subito, inventato oggi per voi:

Trovare tutte le coppie di primi $ p,q $ tali che $ p^2q^2 | p^3+q^3+1 $

Auguri!

[FrancescoVeneziano]

In realtà non ricordo ma forse è vero in generale che le soluzioni di $ x^2 - ay^2= m $ sono della forma $ x_n + \sqrt{a} y_n = (x_0 + \sqrt{a}y_0)( \chi_1 + \sqrt{a} \chi_2)^n $ dove $ \chi_1 ^ 2 - a \chi_2 ^2 =1 $ soluzione minimale.

Non esattamente. Sono tutte nella forma che hai scritto, ovviamente, ma al posto di $ x_0 + \sqrt{a}y_0 $ possono esserci diverse soluzioni particolari (sempre un numero finito, però). Non puoi ricondurti ad una famiglia sola perché il rapporto tra due interi algebrici di norma m ha sì norma 1, ma non è detto che sia ancora un intero algebrico. Puoi però dire che si tratta di un numero finito di famiglie ed anche trovarle in modo esplicito.

[jordan]

Problema 13.
Trovare tutte le coppie di primi $ p,q $ tali che $ p^2q^2 | p^3+q^3+1 $

Se $ p=q $ allora $ p^4 \mid 2p^3+1 $, per cui $ p $ non può essere pari, allora $ p^4 \ge 3p^3=2p^3+p^3>2p^3+1 $, assurdo. Dato che problema è simmetrico assumiamo wlog $ p<q $: se $ p=2 $ allora $ q^2 \mid 2^3+1 $ per cui $ (p,q)=(2,3) $(e simmetrica) è soluzione. Se $ p=3 $ allora $ q^2 \mid 3^3+1=2^2 \cdot 7 $, assurdo dal momento che $ p<q $. Per cui wlog $ 3 < p<q $. Abbiamo in ogni caso che $ q^2 \mid p^3+1=(p+1)(p^2-p+1) $, ma $ (p+1,p^2-p+1)=(p+1,3p) $ per cui i due fattori non avranno mai in comune un fattore $ q>3 $. Ma $ q^2>q>p+1 $ quindi deve essere per forza di cose $ q^2 \mid p^2-p+1 $, ma $ q^2 \le p^2-p+1 < p^2 \le \max\{q+1,q^2-q+1\} $, assurdo.


Problema 14
Trovare tutti gli $ (x,y) \in \mathbb{N}^2 $ tali che $ 2 \cdot 3^x = (1+\sqrt{2})^{2y}+(1-\sqrt{2})^{2y} $.

[jordan]

Problema 11

Siano $ v_1,\dots v_n $ dei vettori di lunghezza k a coefficienti interi. Sia p un primo. Dimostrare che se $ n>(p-1)k $ allora esiste un insieme non vuoto $ I\subseteq \{ 1,\dots ,n\} $ tale che:

$ \displaystyle\sum_{i\in I} v_i \equiv (0,\dots ,0) \pmod p $

vale a dire ciascun coefficiente del vettore somma è un multiplo di p.

Detta $ v_{i,j} $ la $ j $ esima componente del vettore $ v_i $, consideriamo i $ k $ polinomi in $ n $ variabili $ f_j(x_1,x_2,\ldots,x_n):=\displaystyle \sum_i{v_{i,j}x_i^{p-1}} $.
Usando l'hint (vedi qui) e, considerato che $ \vec{0} $ è soluzione, allora ne esiste almeno un'altra non nulla, che è la tesi.

[jordan]

Problema 14
Trovare tutti gli $ (x,y) \in \mathbb{N}^2 $ tali che $ 2 \cdot 3^x = (1+\sqrt{2})^{2y}+(1-\sqrt{2})^{2y} $.

Ok, è passata ben più di una settimana..
Possiamo vedere che RHS corrisponde ai termini della sequenza $ a_0 = 2,a_1 = 6,a_{n + 2} = 6a_{n + 1} - a_n $.
Adesso $ (x,y)=(0,0) \text{ e } (1,1) $ sono soluzioni banali e possiamo vedere che la sequenza ha periodo $ 12 $ modulo 9 e modulo 11.
Ancora meglio, $ 9|a_i $ se e solo se $ 12\mid i \pm 3 $, e anche $ 11 \mid a_i $ se e solo se $ 12\mid i \pm 3 $, bingo.


Abbassiamo il tiro..
Problema 15
Mostrare che se $ n $ è dispari allora l'insieme $ \displaystyle \{\binom{n}{1},\binom{n}{2},\binom{n}{3},\ldots,\binom{n}{\frac{n-1}{2}}\} $ contiene un numero dispari di numeri dispari.

[Gebegb]

La somma di quei binomiali è 2^(n-1) -1, quindi sono dispari in numero dispari.

[Gebegb]

Il collega Jordan mi ha invitato a proporre un nuovo problema.

Sia p un numero primo per il quale esiste almeno un numero naturale x tale che:

1) p divide x^5 + 5
2) p divide (x+1)^5 + 5

Determinare l'unico possibile valore di p.

(Richiede parecchi calcoli, ma alle 2 di notte avevo solo la forza per prendere il quaderno e copiare uno a caso dei vecchi problemi.)

[federiko97]

(Richiede parecchi calcoli, ma alle 2 di notte avevo solo la forza per prendere il quaderno e copiare uno a caso dei vecchi problemi.)

Si accettano "metasoluzioni"?

Per chi non lo sapesse una metasoluzione è una soluzione in cui è lecito dire "si lasciano i calcoli al lettore come utile esercizio".

[fph]

Per chi non lo sapesse una metasoluzione è una soluzione in cui è lecito dire "si lasciano i calcoli al lettore come utile esercizio".

Io la chiamerei metà soluzione.

[Gebegb]

Secondo me ha ragione Fph.
Se si accettano affermazioni del tipo "si lasciano i calcoli al lettore come utile esercizio" allora non è una metasoluzione ma metà soluzione!
I metaproblemi, i metametaproblemi e in generale i (meta)^n problemi sono un argomento tipico della logica matematica.
Sono degli esercizi eccellenti per confondersi, uno dei maestri dei (meta)^n-rompicapi è come sempre il grandissimo logico Raymond Smullyan.
I metaproblemi sono problemi concernenti problemi. Per risolvere un metaproblema ci si basa sul fatto di sapere che un altro problema può essere risolto o no.
Faccio un semplice esempio di metarompicapo (dal libro "Satana, Cantor e l'infinito" di Smullyan).

Il pianeta Og è abitato da due razze: i verdi e i rossi.
Gli abitanti dell'emisfero settentrionale sono molto diversi da quelli dell'emisfero meridionale.
I settentrionali verdi dicono sempre la verità, i settentrionali rossi mentono sempre. I meridionali verdi dicono mentono sempre, i meridionali rossi dicono sempre la verità.
Un logico terrestre visitò il pianeta Og e incontrando un indigeno in una notte buia, gli chiese se fosse un settentrionale verde. L'indigeno rispose si o no ma il logico non fu in grado di determinare cosa l'indigeno fosse.
Un secondo logico incontrò l'indigeno in un'altra notte buia e gli chiese se fosse un meridionale verde. L'indigeno rispose si o no, ma il logico non riuscì a capire cosa fosse.
Un terzo logico incontrò l'indigeno in un'altra notte buia e gli chiese se fosse un meridionale rosso. L'indigeno rispose si o no, ma il logico non riuscì a capire cosa fosse.
Che cos'era l'indigeno?

Per quanto riguarda le metasoluzioni il discorso è più sottile e articolato.
Senza fare discorsi troppo astratti faccio un esempio non logico (altrimenti vengo accusato di parlare solo di logica).

Attraverso il centro di una sfera solida viene fatto un buco cilindrico lungo esattamente 6 cm. Qual'è il volume della sfera?

Una soluzione del problema è la seguente.
Sia R il raggio della sfera. Il raggio del foro cilindrico sarà la radice quadrata di (R^2 - 9). L'altezza delle calotte sferiche su ciascuna estremità del cilindro sarà R-3. Adesso basta sottrarre al volume della sfera, quello del cilindro e delle due calotte. Fatto questo calcolo si ottiene 36 pi greco cm^3.

Una metasoluzione del problema è la seguente.
Il problema non fornisce come dato il raggio della sfera. Significa che è un dato influente e che il problema ha una soluzione che non dipende dal raggio. Allora basta considerare il caso in cui il foro è degenere e il buco viene ridotto ad avere raggio 0. Questo accade in una sfera di raggio 3 quindi la risposta è 36 pigreco cm^3.

Tornando al problema che ho proposto mi accontento anche di una metasoluzione.
Infatti se scrivo "calcolare p" sto tacitamente assumendo che p sia unico e che esista.
Ovviamente nella soluzione completa si dimostra anche questo fatto.

[federiko97]

Uhm, non è chiaro cosa intendevo. Una "metasoluzione" non vuol dire "sparo un risultato senza dimostrarlo", vuol dire invece "Fornisco un procedimento per trovare il risultato - il quale procedimento dimostra anche che il risultato sia giusto e unico. Ma, essendo il procedimento lungo e noioso, evito di eseguirlo".

In questo caso la metasoluzione è questa:

Per Bézout esistono p(x) e q(x) polinomi a coefficienti interi tali che $ p(x)(x^5+5)+q(x)((x+1)^5+5)=c $ con c intero diverso da 0.

Chiaramente il primo che cerchiamo divide c, quindi ci basta cercare tra quelli. Purtroppo per trovare c serve trovare anche i polinomi p e q e l'unico algoritmo che conosco (divisioni euclidee iterate) non è propriamente rapido...

[Gebegb]

Va bene.
In effetti i calcoli sono brutti, io li ho fatti al pc.
Comunque c=7717503920.
(Più che una metasoluzione, la sua si direbbe una soluzione non costruttiva.)