Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 01 lug 2009, 15:26

escluso il caso k=1,
$ n=2^{k-2} $
poichè 5 è un residuo quadratico modulo $ \displaystile{2^k} $, e
$ phi(2^k)=2^{k-1} $

?
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

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

Messaggio da jordan » 01 lug 2009, 15:26

GioacchinoA ha scritto:$ \textbf {Problema 22} $
Per ogni $ k $ intero positivo , trovare il più piccolo $ n $ tale che $ 2^k | 5^n -1 $
Guardiamo il lemma qui per dedurre che $ ord_{2^k}(5)=2^{k-2} $ per ogni k>2. Altrimenti n=1. :o

Edit: qualcuno proponga un nuovo problema..
The only goal of science is the honor of the human spirit.

TBPL
Messaggi: 117
Iscritto il: 20 gen 2008, 23:19

Messaggio da TBPL » 01 lug 2009, 15:41

jordan ha scritto: Edit: qualcuno proponga un nuovo problema..
Siccome credo che sia riferito a me, vado xD (tranquillo Jordan, questo puoi stuprarlo :*)
Problema 23
Sia $ p(x)=ax^2+bx+c $ un polinomio a coefficienti interi e sia $ p $ un primo dispari. Sapendo che $ p(x) $ è un quadrato perfetto per $ p $ valori interi consecutivi, e che esiste un intero $ k $ tale che $ a+kp $ è un quadrato perfetto, dimostrare che $ b^2-4ac\equiv 0 \pmod{p} $

Edit: errore di battitura...
Edit 2: Dimenticata un'ipotesi... odio jordan xD
Ultima modifica di TBPL il 01 lug 2009, 18:30, modificato 2 volte in totale.

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

Messaggio da jordan » 01 lug 2009, 16:42

TBPL ha scritto:Problema 23
Sia $ p(x)=ax^2+bx^2+c $ un polinomio a coefficienti interi e sia $ p $ un primo dispari. Sapendo che $ p(x) $ è un quadrato perfetto per $ p $ valori interi consecutivi, dimostrare che $ b^2-4ac\equiv 0 \pmod{p} $
Sia $ p>2 $ fissato allora consideriamo $ (a,b,c)=(1,(p+1)(p-1),0) $. Abbiamo che $ p(x) $ è un quadrato perfetto per ogni $ x \in \mathbb{Z} $ e che $ p \nmid (p+1)^2(p-1)^2=b^2-4ac $ :? :? :?
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 » 01 lug 2009, 18:09

TBPL ha scritto:Problema 23
Sia $ p(x)=ax^2+bx+c $ un polinomio a coefficienti interi e sia $ p $ un primo dispari. Sapendo che $ p(x) $ è un quadrato perfetto per $ p $ valori interi consecutivi, dimostrare che $ b^2-4ac\equiv 0 \pmod{p} $

Edit: errore di battitura...
Secondo tentativo, $ p(x)=2x(x-1) $ è un quadrato per 0,1,2, ma 3 non divide 4 :?
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 » 01 lug 2009, 19:32

TBPL ha scritto:Edit 2: Dimenticata un'ipotesi... odio jordan xD
:lol:
TBPL ha scritto: Problema 23
Sia $ q(x)=ax^2+bx+c $ un polinomio a coefficienti interi e sia $ p $ un primo dispari. Sapendo che $ q(x) $ è un quadrato perfetto per $ p $ valori interi consecutivi, e che esiste un intero $ k $ tale che $ a+kp $ è un quadrato perfetto, dimostrare che $ b^2-4ac\equiv 0 \pmod{p} $
Se $ p \mid a $ e $ p \nmid b $ allora $ p \mid q(x)-(bx+c) $. Ma $ bx+c $ forma un sistema completo di residui modulo $ p $ se consideriamo $ p $ interi consecutivi, mentre invece $ q(x) $ è sempre un residuo quadratico (e ricordiamo esistono esattamente $ \frac{p-1}{2} $ residui non quadratici). Per cui se $ p\mid a $ allora anche $ p \mid b $ e quindi $ p \mid b^2-4ac $. Assumiamo che $ p \nmid a $ e, dalle ipotesi, che $ (\frac{a}{p})=1 $.

Lemma. Se $ p \nmid a(b^2-4ac) $ allora $ \displaystyle \sum_{x=0}^{p-1}{\left(\frac{ax^2+bx+c}{p}\right)}=-\left(\frac{a}{p}\right) $.

Per cui abbiamo $ -1=\displaystyle -\left(\frac{a}{p}\right)=\sum_{x=0}^{p-1}{\left(\frac{ax^2+bx+c}{p}\right)} \ge 0 $, assurdo, per cui $ p \mid b^2-4ac $.
The only goal of science is the honor of the human spirit.

TBPL
Messaggi: 117
Iscritto il: 20 gen 2008, 23:19

Messaggio da TBPL » 02 lug 2009, 10:16

Jordan è pigro, quindi mi ha incaricato di postare un altro problema 8) (Sperando di non fare di nuovo casini con la traccia :lol: )
Problema 24
E' definita la successione $ a_1,a_2,\cdots $ tale che:
$ \displaystyle a_n=\frac{1}{n}\sum_{i=1}^n{\left\lfloor \frac{n}{i} \right\rfloor} $

a) Dimostrare che ci sono infiniti interi positivi tali che $ a_n>a_{n+1} $
b) Dimostrare che ci sono infiniti interi positivi tali che $ a_n<a_{n+1} $

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 04 lug 2009, 15:13

Lemma (1): $ \displaystyle\sum_{i=1}^n{\left\lfloor\frac{n}{i}\right\rfloor}=\sum_{i=1}^n{\tau(i)} $
Dim. lemma:
Procedo per induzione, suppongo vera la tesi al passo n e la dimostro per n+1: LHS nel passaggio da n ad n+1 incrementa di un'unità per ogni divisore di n+1,
pertanto aumenta di $ \tau(n+1) $, segue la tesi.
Dimostrazione:
(a). Per il lemma (1) posso riscrivere $ a_n>a_{n+1} $ come $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\frac{1}{n+1}(\sum_{i=1}^n{\tau(i)}+\tau(n+1))\Longleftrightarrow\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\tau(n+1) $ .
Ponendo $ n+1=p $ primo si ha $ LHS>(p-1)\tau(p)=2(p-1) $, ma $ LHS\ge 2(p-1)+1 $ per ogni $ p\ge 5 $ (in quanto $ \tau(n)\ge 2,\forall n>1 $), segue la tesi.
(b). Per ogni n chiamo $ X=\{1,\cdots,n\} $; sia $ j $ l'elemento di $ X $ che massimizza $ \tau(i) $ tale che $ \tau(h)<\tau(j) , \forall 1\le h\le j $.
Analogamente al punto precedente, occorre dimostrare che esistono infiniti n tali che $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}<\tau(n+1)\Longleftrightarrow\frac{1}{n+1}\sum_{i=1}^{n+1}{\tau(i)}<\tau(n+1) $, ma dalla disuguaglianza $ AM\{b_i\}\le max\{b_i\} $ ho che $ AM\{\tau(i)\}=LHS<max\{\tau(i)\}=\tau(j) $ (vale in senso stretto poichè gli elementi della somma non sono tutti uguali),
basta quindi porre $ n+1=j $. Segue facilmente la tesi.
Spero che funzioni... (mi scuso inoltre se la soluzione appare un po' confusa, ma è stata scritta molto in fretta).

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 09 lug 2009, 10:54

Problema 25
Siano dati $ p_1<\cdots<p_n $ primi maggiori di 3. Dimostrare che $ \tau(2^{p_1p_2\cdots p_n}+1)\ge 2^{2^{n-1}} $ :D

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

Messaggio da jordan » 09 lug 2009, 20:53

Definito $ \displaystyle D:=\prod_{i=1}^n{p_i} $, è sufficiente provare che $ \omega(2^D+1) \ge 2^{n-1} $. Adesso:
$ \displaystyle 2^D+1=\frac{2^{2D}+1}{2^D-1}=\frac{\prod_{i \mid 2D}{\phi_i(2)}}{\prod_{i \mid D}{\phi_i(2)}}={\prod_{i \mid D}{\phi_{2i}(2)}} $.
Lemma8. Siano dati $ (a,b) \in \mathbb{N}^2 $ tali che $ (\phi_a(x),\phi_b(x))>1 $, allora $ \frac{a}{b} $ è della forma $ p^k $ per qualche $ p \in \mathbb{P} $ e per qualche $ k \in \mathbb{Z} $.
Grazie al lemma possiamo dire che ci è sufficiente trovare $ i_1,i_2,\ldots,i_{2^{n-1}} \in \mathbb{Z} $ tali che $ \prod_{sym}(i_1-i_2)^2>0 $ e $ i_j \mid D $ per ogni $ 1 \le j \le 2^{n-1} $. Ma allora è sufficiente prendere tutti i divisori di D che hanno un numero pari di fattori primi, e, dato che sono in numeri uguali a quelli che hanno un numero dispari di fattori primi, possiamo concludere che ne sono esattamente $ 2^{n-1} $.
Ps. Con qualche altro strambo metodo è possibile che questa stima possa essere ancora migliorata :o
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 » 09 lug 2009, 22:58

Problema 26.
Un intero positivo è bello se è della forma $ n+s(n) $ per qualche intero positivo $ n $ (qui s(n) denota la somma delle cifre di n).
Mostrare che se $ k $ è un intero positivo, allora almeno uno tra $ k $ e $ k+1 $ è bello.
The only goal of science is the honor of the human spirit.

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 10 lug 2009, 16:12

Prendiamo i vettori n_x a x componenti intere:
$ n_x=(n_0,n_1,...,n_{x-1}) $ $ 0\le n_i \le9 $ $ \forall 0\le i \le x-1 $
Definiamo f:N^x -> N così:
$ f(n_x)=\sum(n_i(10^i+1)) $.
Mostriamo che:
$ k=f(n_x) $ oppure $ k+1=f(n_x) $ per qualche vettore $ n_x $.
Ordino ora lo spazio di tutti i vettori n_x nel seguente modo:
assegno tramite $ g(n_x)=\sum 10^in_i $ il numero in base 10 associato a n_x.
Preso un vettore $ n_x $ definisco come suo successore il vettore $ m_x $ o $ m_{x+1} $ tale che $ g(m_x)=g(n_x)+1 $.
Questo ordinamento funziona in quanto prende tutte le possibili x-uple ed è ben definito anche rispetto alla f di sopra:
infatti per la definizione di f e per la definizione dell'ordinamento se $ m_x $ è il successore di $ n_x $ allora $ f(m_x)-f(n_x)\le2 $, e questo segue da:
1)Facendo aumentare n_0 di 1 (fin quando è possibile) f(n_x) aumenta di 2
2)Passando dal vettore n=(9,..,9,z) al vettore m=(0,...,0,z+1) la differenza $ f(m)-f(n)<0 $.
3)Passando dal vettore n=(9,...,9) al vettore m=(0,...,0,1) la differenza $ f(m)-f(n)<0 $.
Una volta provato quindi che $ f(m)-f(n)\le2 $ basta notare che $ f(n_x) $ tende a infinito quando $ g(n_x) $ tende a infinito (poichè ovviamente $ f(n_x)>g(n_x) $) e abbiamo mostrato che la f approssima almeno un numero intero ogni 2.
Mostriamo quindi i fatti 1) 2) e 3):
1) è banale;
2)n:=(9,...,9,z);m=(0,...,0,z+1) ($ z \neq 9 $). Quindi detto w:=numero di componenti di n e di m si ha:
$ f(m)-f(n)=(10^w+1)(z+1)-[z(10^w+1)+9\sum_{i=0}^{w-1}(10^i+1)]=z10^w+z+10^w+1-z10^w-z-9(\frac{10^w-1}{9}+w)=2-w<0 $
3)n:=(9,...,9); m:=(0,...,0,1). Perciò detto w:= numero di componenti di n e w+1 quindi quello di m si ha:
$ f(m)-f(n)=10^{w+1}+1-9\sum_{i=0}^{w}(10^i+1)=10^{w+1}+1-9[\frac{10^{w+1}-1}{9}+(w+1)]=10^{w+1}+1-10^{w+1}+1-9w-9=2-9(w+1)<0 $
Ultima modifica di Giulius il 10 lug 2009, 20:44, modificato 5 volte in totale.
Aboliamo il latino nei licei scientifici!

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 10 lug 2009, 16:29

Tentando di leggere la risposta di Giulius mi sono perso alla prima riga :oops:
Domanda: gli argomenti utilizzati non sono addirittura superiori alla preparazione per le IMO?
Io, a livelli molto più bassi, stavo semplicemente cercando di giocare un po' sul fatto che $ n+s(n) \equiv 2n \pmod{9} $ ma non avevo raggiunto grandi risultati. Ero sulla cattiva strada?

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 10 lug 2009, 16:31

ma lol, che IMO...non ti prendo in giro se ti dico che non ho mai passato le provinciali fino alla quarta =P, certo io sono un po' contorto in effetti....
Aboliamo il latino nei licei scientifici!

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 10 lug 2009, 16:41

Se è per quello neanche io :lol:
Comunque dell'utilizzo di vettori in Tdn non ne ero nemmeno a conoscenza. Conosci qualche dispensa che mi faccia perlomeno intuire cio' che hai scritto?
Grazie.

Rispondi