Staffetta tdn

[exodd]

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} $

?

[jordan]

$ \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.

Edit: qualcuno proponga un nuovo problema..

[TBPL]

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

[jordan]

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 $

[jordan]

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

[jordan]

Edit 2: Dimenticata un'ipotesi... odio jordan xD

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 $.

[TBPL]

Jordan è pigro, quindi mi ha incaricato di postare un altro problema (Sperando di non fare di nuovo casini con la traccia )
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]

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]

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}} $

[jordan]

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

[jordan]

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.

[Giulius]

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 $

[ndp15]

Tentando di leggere la risposta di Giulius mi sono perso alla prima riga
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]

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....

[ndp15]

Se è per quello neanche io
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.