Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Yeah!

Messaggio da jordan » 04 mag 2009, 21:49

federiko97 ha scritto: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 :roll:

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 :o

Edit: Un bound un poco migliore qui ..(<-- cancellato :shock: sei un grande simo)
Edit2: l'esempio di sopra è addirittura impossibile modulo 3 :lol:
Ultima modifica di jordan il 05 mag 2009, 00:32, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

Simo_the_wolf
Moderatore
Messaggi: 1041
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 05 mag 2009, 00:28

Perchè inguaiarsi così tanto?? :P

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 $

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 05 mag 2009, 10:21

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).
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

Simo_the_wolf
Moderatore
Messaggi: 1041
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 06 mag 2009, 15:44

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!

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 06 mag 2009, 16:24

Simo_the_wolf ha scritto: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.
Ultima modifica di FrancescoVeneziano il 06 mag 2009, 17:09, modificato 1 volta in totale.
Wir müssen wissen. Wir werden wissen.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 06 mag 2009, 16:44

Simo_the_wolf ha scritto: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} $.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 25 mag 2009, 14:24

federiko97 ha scritto: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.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 29 mag 2009, 00:55

jordan ha scritto: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.
The only goal of science is the honor of the human spirit.

Gebegb
Messaggi: 28
Iscritto il: 10 apr 2009, 13:59

Messaggio da Gebegb » 29 mag 2009, 01:37

La somma di quei binomiali è 2^(n-1) -1, quindi sono dispari in numero dispari.
Legge di Hofstadter:"Ci vuole sempre più tempo di quanto si pensi, anche tenendo conto della Legge di Hofstadter."
Il segreto dell'immortalità: essere sempre sinceri e dire "Ripeterò questa frase domani." (Raymond Smullyan)

Gebegb
Messaggi: 28
Iscritto il: 10 apr 2009, 13:59

Messaggio da Gebegb » 29 mag 2009, 02:16

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.)
Legge di Hofstadter:"Ci vuole sempre più tempo di quanto si pensi, anche tenendo conto della Legge di Hofstadter."
Il segreto dell'immortalità: essere sempre sinceri e dire "Ripeterò questa frase domani." (Raymond Smullyan)

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 31 mag 2009, 18:35

Gebegb ha scritto:(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"? :P

Per chi non lo sapesse una metasoluzione è una soluzione in cui è lecito dire "si lasciano i calcoli al lettore come utile esercizio".
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

fph
Site Admin
Messaggi: 3763
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 31 mag 2009, 19:27

federiko97 ha scritto: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. :D
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Gebegb
Messaggi: 28
Iscritto il: 10 apr 2009, 13:59

Messaggio da Gebegb » 01 giu 2009, 00:07

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.
Legge di Hofstadter:"Ci vuole sempre più tempo di quanto si pensi, anche tenendo conto della Legge di Hofstadter."
Il segreto dell'immortalità: essere sempre sinceri e dire "Ripeterò questa frase domani." (Raymond Smullyan)

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 01 giu 2009, 15:59

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...
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

Gebegb
Messaggi: 28
Iscritto il: 10 apr 2009, 13:59

Messaggio da Gebegb » 01 giu 2009, 19:59

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.)
Legge di Hofstadter:"Ci vuole sempre più tempo di quanto si pensi, anche tenendo conto della Legge di Hofstadter."
Il segreto dell'immortalità: essere sempre sinceri e dire "Ripeterò questa frase domani." (Raymond Smullyan)

Rispondi