Staffetta tdn

[jordan]

Problema 104 da qui:

Siano $p_1,p_2,..p_n$ numeri primi diversi tra loro e maggiori di 3. Detto $z$ il loro prodotto, si dimostri che $2^z+1$ ha almeno $4^n$ divisori

P.S.: non conosco la soluzione, ma mi sembra alla vostra portata... (non alla mia)

Siano $p_1,p_2,..p_n$ numeri primi diversi tra loro e maggiori di 3. Detto $z$ il loro prodotto, si dimostri che $2^z+1$ ha almeno $4^n$ divisori

P.S.: non conosco la soluzione, ma mi sembra alla vostra portata... (non alla mia)

Dimostramo la tesi per induzione. Se $\omega(z)=1, |\mu(z)|=1$ allora $1<3<\frac{2^z+1}{3}<2^z+1$ dividono $4$ per cui $\sigma_0(2^z+1)\ge 4$.

Supponiamo che abbiamo dimostrato che dato qualunque $z\in \mathbb{N}, |\mu(z)|=1, \omega(z)=n, \text{lpf}(z)\ge 5$ valga $\omega_0(2^z+1)\ge 4^{\omega(z)}$.

Fissato un qualunque $z$, dimostriamo che la tesi vale anche per $zp$, dove $p\ge 5$ è un primo tale che $p\nmid z$.
Abbiamo $\upsilon_3(2^{zp}+1)=\upsilon_3(3)+\upsilon_3(zp)=1$, e che $\text{gcd}(2^z+1, 2^p+1)\mid$ $ \text{gcd}(2^{2z}-1, 2^{2p}-1)=2^{\text{gcd}(2z,2p)}-1=2^2-1$: questo significa che $\text{gcd}(2^z+1,\frac{2^p+1}{3})=1$.

Notiamo anche che $(2^z+1)^2(\frac{2^p+1}{3})^2=\frac{1}{9}(2^{2z}+2^{z+1}+1)(2^{2p}+2^{p+1}+1)< \frac{1}{9}2^{2z+1}2^{2p+1}< 2^{2z+2p} < 2^{zp}+1$. implica che se $d\mid (2^z+1)(\frac{2^p+1}{3})\mid 2^z+1$ allora anche $\frac{2^z+1}{d} \mid 2^z+1$ ed e' distinto da tutti gli altri divisori di $(2^z+1)(\frac{2^p+1}{3})$.

Dato che $2^z+1\mid 2^{zp}+1$ e anche $\frac{2^p+1}{3}\mid 2^{zp}+1$, possiamo allora concludere che $\sigma_0(2^{zp}+1) \ge 2\sigma_0(2^z+1) \sigma_0(\frac{2^p+1}{3})\ge 4^{\omega(z)+1}$. []

[jordan]

Problema 105 da qui:

Sia M un sottoinsieme di {1,2,3,...,15}. Trovare quanto vale al massimo |M|, se per ogni i,j,k distinti in M il prodotto ijk non e' un quadrato.

Ok, risolto..
Esistono 6 insiemi M di cardinalità 10 che vanno bene
Un esempio è

$ M = [4, 5, 6, 7, 9, 10, 11, 12, 13, 14] $

Non ne esistono di cardinalità maggiori

La mia dimostrazione è a casi, quindi vorrei vedere se qualcuno ha una soluzione elegante prima..

Dimostro che il massimo è 10:
Divido in 2 casi:
1) M non contiene quadrati, quindi viste le terne (2,6,12), (7,14,8) e (5,15,3) devo togliere altri 3 numeri e M ha cardinalità minore di 10.
2) M contiene quadrati, date le terne ([],2,8) e ([],3,12) devo togliere 2 numeri (wlog 8 e 12). Infine date le terne (7,14,2), (5,15,3) e (1,4,9) devo eliminare altri 3 numeri e M ha cardinalità massima 10.

Dato che non ho fatto altro che copiare e assemblare le idee precedenti, lascio a Exodd l'onore e l'onere di postare il prossimo problema.

[jordan]

Problema 106 da qui:

Supponiamo che A sia l'insieme di tutti gli interi positivi scrivibili nella forma $ a^2+2b^2 $, con $ a $ e $ b $ interi, e $ b $ diverso da zero
Dimostrare che se $ p^2 $ appartiene ad A, con $ p $ primo, allora $ p $ appartiene ad A

Se $ a^2 + 2b^2 = p^2 $ ho innanzitutto che (a,p)=(b,p)=1, inoltre la relazione iniziale implica che $ 2b^2 = p^2 - a^2 = (p+a)(p-a) $.
Ma (p+a, p-a) = (2p, p-a) = (2p, 2a) = 2(p, a) = 2 e quindi uno fra (p-a) e (p+a) è della forma $ 2x^2 $ e l'altro è della forma $ 2^{2k} \cdot y^2 $ con x e y dispari. Quindi $ 2p = (p+a) + (p-a) = 2x^2 + 2^{2k} \cdot y^2 $ da cui $ p = x^2 + 2 \cdot (2^{k-1} \cdot y)^2 $ da cui la tesi.

[jordan]

Problema 107 da qui:

Detta $ \sigma(k) $ la somma dei divisori interi positivi di k (compresi 1 e k) dimostrare che:
$ \displaystyle \sum_{i=1}^{n}{\frac{\sigma(i)}{i}} \leq 2n $
Per ogni n intero positivo.

Ci avevo pensato anche io... ma non avevo capito quanto potesse essere utile... (ed ecco il perche della zeta! )

Questo mi fa scrivere la somma di partenza come $n+\frac a 2 +\frac b 3+\dots$ dove a è il numero di i divisibili per 2, b è il numero di i divisibili per 3...
Inolte il numero di i divisibili per x è all'incirca $\frac n x$ (devo lavorarci su questo "circa"... )

Dunque riscrivo il LHS come $\displaystyle{\sum_{i=1}^n \frac n {i^2}}$ , che devo dimostrare essere minore di $2n$ ...
cosa non molto difficile, dato che mi basta portare fuori dalla sommatoria $n$, semplificarlo e ci rimane $$\displaystyle{\sum_{i=1}^n \frac 1 {i^2}<\sum_{i=1}^\infty \frac 1 {i^2} = \frac{\pi^2} 6 < 2}$$

L'unica falla di questa pseudo-dimostrazione è quel "all'incirca", che devo cercare di far diventare qualcosa di più preciso...

EDIT: i numeri divisibili per x minori o uguali a n (escluso lo 0) sono $[\frac n x]\leq \frac n x$
Dunque per l'osservazione di prima la somma originale si inserisce in una catena di disuguaglianze così $$\displaystyle{\sum_{i=1}^n \frac{\sigma(i)} i = \sum_{i=1}^n \left[\frac n i\right]\cdot\frac 1 i\leq \sum_{i=1}^n \frac n {i^2}=n\cdot \sum_{i=1}^n \frac 1 {i^2}\leq n\cdot\sum_{i=1}^{\infty} \frac 1 {i^2}=n\cdot\frac{\pi^2} 6 < 2n}$$

Mi pare che quadri tutto...

[jordan]

Problema 108 da qui:

Sia $I_0=\lbrace -1,1\rbrace$ . $I_n$ è definito per ricorsione come l'insieme delle soluzioni dell'equazione $x^2-2xy+y^2-4^n=0$ , dove y varia tra gli elementi di $I_{n-1}$. Determinare l'unione degli insiemi $I_0,I_1...I_n$

Purtroppo non so ancora bene dove andare a pescare buoni problemi, perciò ho preso questo da Viareggio...
Spero vada bene, anche se forse è un po' troppo facile...

Se vogliamo possiamo sempre applicare l'induzione.
La nostra tesi è che sono presenti tutti i dispari compresi tra $ (2^{k+1}-1,-2^{k+1}+1) $ dove $ k $ è il pedice di $ I $.
Siccome è vera per $ I_1 $, supponiamolo vero $ I_n $, dimostriamolo vero per $ n+1 $.
Per la ricorsione:
$ x_{n+1}-y_n=\pm 2^{n+1} \Rightarrow x_{n+1}=\pm 2^{n+1} +y_n $.
Effettivamente variando $ y_n $ tra tutti i dispari compresi $ (2^{n+1},-2^{n+1}) $, il massimo dispari della somma di RHS è $ (2^{n+1}+2^{n+1}-1,-2^{n+1}-2^{n+1}+1) $. Siccome $ 2^{n+1} $ è pari la somma con $ y_n $ è necessariamente dispari. Aggiungendo tutti i numeri dispari consecutivi, partendo da 1, e -1 sino ad $ 2^{n+1} $ e $ -2^{n+1} $, notiamo che la somma ricopre tutti i dispari fino a $ 2^{n+2}-1 $ e, siccome l'equazione è simmetrica fino $ -2^{n+2}+1 $, che è la tesi.
Spero adesso che la soluzione totale vada bene.

[jordan]

Problema 109 da qui:

Trovare tutti i triangoli $ ABC $ con lati di lunghezza intera ed angolo A doppio dell'angolo B.
Bonus: trovare tutti i triangoli con lati di lunghezza intera ed un angolo di 60°.

Noto innanzitutto che l'angolo in $B$ può variare tra 0° e 60° (estremi esclusi), per ovvie ragioni geometriche.
Usando la notazione standard per i triangoli (angolo $\alpha$ nel vertice $A$, $\beta$ in $B$ e $\gamma$ in $C$, lato $a$ opposto ad $A$, $b$

opposto a $B$, $c$ opposto a $C$) so che:
$ \displaystyle \alpha = 2\beta \Rightarrow \sin\alpha = 2\sin\beta\cos\beta $

$ \displaystyle \gamma = 180° - \alpha - \beta = 180° - 3\beta \Rightarrow \sin\gamma = \sin(3\beta) = $
$ \displaystyle = \sin(2\beta)\cos\beta + \cos(2\beta)\sin\beta = \sin\beta (4\cos^2\beta - 1) $

Quindi per il teorema dei seni ho che

$ \displaystyle \frac{a}{2\sin\beta\cos\beta} = \frac{b}{\sin\beta} = \frac{c}{\sin\beta (4\cos^2\beta - 1)} \Rightarrow \frac{a}{2\cos\beta} = b = \frac{c}{4\cos^2\beta - 1} $

Ora definisco $t = \cos\beta$, e noto che $ \displaystyle t \in ] \frac{1}{2}; 1 [ $




Il problema ora è diventato trovare tutte le quaterne composte da 3 interi positivi $a$, $b$, $c$ e un reale $ \displaystyle \frac{1}{2} \lt t \lt 1 $ che soddisfano la catena di uguaglianze:

$ \displaystyle \frac{a}{2t} = b = \frac{c}{4t^2 - 1} $ (1)




Affermo che le soluzioni sono tutte e sole del seguente tipo:
$ \displaystyle b=xy^2 $
$ \displaystyle a=xy^2 + rxy $
$ \displaystyle c=rx(2y+r) $
$ \displaystyle \cos\beta = \frac{1}{2} ( 1 + \frac{r}{y} ) $

al variare di $y$ tra gli interi positivi maggiori di 1, $x$ tra gli interi positivi liberi da quadrati (http://en.wikipedia.org/wiki/Square-free_integer)
e con $r$ intero compreso strettamente tra 0 e $y$ ($0 \lt r \lt y$)

La dimostrazione nel prossimo post perché questo si è fatto un po' lunghino

Mi soffermo sulla prima uguaglianza della catena (1), equivalente a:
$ \displaystyle \frac{a}{b} = 2t \in ]1; 2[ \Rightarrow a \in ]b; 2b[ $

Quindi noto che, fissato $b$ maggiore di 1, posso scegliere $a$ in $(b-1)$ modi diversi e calcolare $t$ di conseguenza in modo che l'uguaglianza sia soddisfatta.
Resta il problema della seconda uguaglianza. Supponiamo di scegliere $a$ casualmente e vediamo cosa succede.

Fissati $a$ e $b$ pongo $ \displaystyle 2t = \frac{a}{b} $

quindi, dalla seconda uguaglianza della (1), ho che

$ \displaystyle c = b(4t^2-1) = b(\frac{a^2}{b^2} - 1) = \frac{a^2}{b} - b $

ed è necessario quindi che $b$ divida $a^2$


Noto subito che $b$ non può essere square-free, perché se lo fosse dovrebbe accadere che $b|a$, in contrasto con l'ipotesi che $a \in ]b; 2b[$

Posso quindi scrivere $b=xy^2$, con $y \gt 1$ e $x$ square-free

Ora il mio obiettivo è trovare tutti gli $a \in ]b; 2b[$ tali che $b|a^2$
oppure, che è equivalente, trovare tutti gli $i \in ]0; b[$ tali che $b|(b+i)^2$, e cioè che la seguente frazione è intera:

$ \displaystyle \frac{(b+i)^2}{b} = \frac{(xy^2+i)^2}{xy^2}= \frac{x^2y^4+2ixy^2+i^2}{xy^2} = xy^2 + 2i + \frac{i^2}{xy^2} $

Ho quindi che $x|i^2$, ma $x$ è square-free e quindi dev'essere $i=kx$. Ricordo però che $kx = i \in ]0; b[ = ]0; xy^2[$ e quindi $0 \lt k \lt

y^2$

Sostituisco e ottengo che $xy^2 | k^2x^2$, e quindi $y^2 | k^2x$
Ragioniamoci. Un generico primo $p$ compare nella fattorizzazione di $y^2$ con esponente pari, diciamo $2n_p$, quindi lo stesso primo deve

comparire nella fattorizzazione di $k^2x$ con esponente maggiore o uguale a $2n_p$.
Ma $x$ è square-free, e questo vuol dire che qualunque primo (compreso $p$) compare nella sua fattorizzazione con esponente minore o uguale a 1.
Quindi $p$ deve avere esponente maggiore o uguale $(2n_p - 1)$ nella fattorizzazione di $k^2$, ma quest'ultimo è un quadrato e quindi ogni

esponente è pari, e cioè $p$ ha esponente uguale almeno a $2n_p$.

Il discorso è generico, vale per ogni primo che divide $y^2$, e quindi ho che $y^2 | k^2$, e quindi $y|k \Rightarrow k=ry$

Ma avevamo osservato che $0 \lt k \lt y^2$, e quindi $0 \lt r \lt y$

Sostituisco tutti i cambi di variabile effettuati e ottengo che DEVE essere:
$ \displaystyle b=xy^2 $ con $y \gt 1$ e $x$ square-free
$ \displaystyle a=xy^2 + rxy $ con $0 \lt r \lt y$
$ \displaystyle c=rx(2y+r) $
$ \displaystyle \cos\beta = \frac{1}{2} ( 1 + \frac{r}{y} ) $
(condizione necessaria)

Ma si verifica facilmente che questi valori soddisfano la catena di uguaglianze (1), ed altrettanto facilmente si osserva che $a, b, c$ sono

interi e che $\frac{1}{2} \lt \cos\beta \lt 1$ (condizione sufficiente)

Quindi le soluzioni cercate sono tutte e sole di questo tipo

Detto c il lato opposto all'angolo di 60° e a, b gli altri due lati ho che per il teorema di Carnot vale $ c^2 = a^2 + b^2 - ab $ da cui è evidente che se due fra a, b, c hanno un fattore in comune ce l'ha anche il terzo, quindi posso supporre WLOG che a, b, c siano coprimi a due a due fra di loro. Ora, dato che sono lati di un triangolo, posso sostituire $ a=\frac{y+z-x}{2} $ e cicliche (ovviamente anche x, y, z sono interi positivi perché x=b+c, y=c+a, z=a+b). Sostituendo nella relazione ottenuta grazie al teorema di Carnot e svolgendo i conti arrivo a dire che $ z=\frac{4xy-x^2-y^2}{x+y}=\frac{6xy}{x+y}-x-y $. Soprattutto dalla prima uguaglianza è evidente che se x e y hanno un fattore in comune ce l'ha anche z, il che andrebbe contro il fatto che a, b, c sono a due a due coprimi fra loro (a meno che il fattore in questione non sia due che se ne va col 2 del denominatore della frazione di sopra). Posso quindi distinguere due casi.
CASO 1: (x,y)=2
Pongo x=2h, y=2k, con (h,k)=1 e h,k interi positivi. Quindi ho che deve essere intera l'espressione $ \frac{12hk}{h+k} $ da cui ho che h+k divide 12. Posso avere solo:
h=k=1, che mi genera tutti i triangoli equilateri
h=2, k=1 (o viceversa) che mi dà però un triangolo degenere
h=3, k=1 (o viceversa) ma i lati non vengono interi
h=5, k=1 (o viceversa) ma mi viene z negativo
h=11, k=1 (o viceversa) ma mi viene z negativo
h=7, k=5 (o viceversa) ma i lati non vengono interi
CASO 2: (x,y)=1
Ho che deve essere intera l'espressione $ \frac{6xy}{x+y} $ da cui ho che x+y divide 6. Posso avere solo:
x=y=1 che non mi dà lati interi
x=2, y=1 (o viceversa) che mi dà un triangolo degenere
x=5, y=1 (o viceversa) ma mi viene z negativo
Quindi l'unico caso ammissibile è quello del triangolo equilatero, che può avere il lato intero con misura qualsiasi.
Ovvero (a, b, c) = (l, l, l) con l qualsiasi negli interi positivi.

[jordan]

Problema 110 da qui:

Data la successione degli $ a_i $ tale che $ a_0=0, \ a_1 = 1, \ a_{n+2} = 2a_{n+1}-pa_n \forall \ n \in \mathbb{N} $, trovare tutti i valori di p (intero positivo primo) per cui $ \exists \ m \in \mathbb{N} : a_m=-1 $.

Se $p=2$ allora $2\mid a_i$ per ogni $i>0$. In $\mathbb{Z}/(p-1)\mathbb{Z}$ vale $a_n=n$, per cui se $a_m=-1$ allora esiste $t>0$ tale che $m=t(p-1)-1$. In $\mathbb{Z}/p\mathbb{Z}$ vale $a_n=2^{n-1}$, per cui se fosse $-1=a_m=a_{t(p-1)-1}$ $=2^{t(p-1)-2}=2^{-2}$ deve valere $p=5$ (e in effetti se $p=5$ allora $a_4=-1$). []

Tanto per info, vale anche $\displaystyle a_n=\sin(n\theta)\sqrt{\frac{p^n}{p-1}}$, dove $\theta =\text{artan}(\sqrt{p-1})\in (0,\pi)$.

[jordan]

Problema 111 da qui:

Per ogni intero $n>0$ dimostrare che esiste un intero $f(n)>0$ tale che $n\mid f(n)$ e $s(f(n))=n$ (dove $s(x)$ indica la somma delle cifre di $x$).

[quote"jordan"]Detto $m:=\displaystyle \frac{n}{2^{\upsilon_2(n)}5^{\upsilon_5(n)}}$ e' sufficiente scegliere $x= \displaystyle 10^n \frac{10^{s(n)\varphi(m)}-1}{10^{\varphi(m)}-1}$. [][/quote]

[jordan]

Problema 112 da qui:

Trovare due numeri naturali consecutivi tali che in entrambi la somma delle cifre è divisibile per 2006.

Mi basta prendere un numero la cui somma delle prime cifre è 2005, e che termina con 223 nove, e il suo successivo.
Per esempio $n = 99\dots 99799\dots 99$ nel quale la prima serie di 9 è lunga 222 e la seconda 223; infatti $s(n)=9\cdot 445 + 7\equiv 0\pmod{2006}$.
Ed $n+1= 99\dots 998\cdot 10^{223}$, dunque $s(n+1)=9\cdot 222+8\equiv 0\pmod{2006}$

EDI: preceduto...

[jordan]

Problema 113 da qui:

Per quali numeri primi $ p $ vale che $ 3^{p-2}+6^{p-2}-2^{p-2} $ è multiplo di $ p $?

Deve essere $p>3$, e in $\mathbb{Z}/p\mathbb{Z}$ vale $0=3^{-1}+6^{-1}-2^{-1}=1$, che e' un'identità..

[jordan]

Problema 114 da qui:

Un numero e' perfetto se $\sigma_1(n)=2n$. Mostrare che per ogni numero perfetto $n$ vale $\displaystyle n<2^{2^{\sigma_0(n)}}$.

Ps. $\sigma_i(n):=\displaystyle \sum_{d\mid n}{d^i}$.

Sia $ k=\sigma_0(n)-2 $. Siano inoltre $ d_1 $, $ d_2 $, ..., $ d_{k} $ tutti i divisori positivi di $ n $ esclusi 1 e $ n $.

$ \displaystyle \sum_{1 \leq i \leq k}{d_i}=n-1 $, quindi, dividendo ambo i termini per $ n $, $ \displaystyle \sum_{1 \leq i \leq k}{{d_i}^{-1}}=1-n^{-1} $.
$ n^{-1}=1-\displaystyle \sum_{1 \leq i \leq k}{{d_i}^{-1}} \geq {t_k}^{-1} $, dove $ t_k $ è il $ k $-esimo termine della successione così definita: $ t_1=2 $, $ t_{m+1}=t_m(t_m+1) $. *
Quindi $ n \leq t_k $: resta da dimostrare che $ t_k<2^{2^{k+2}} $. Dimostreremo per induzione che $ t_k<2^{2^{k+2}}-1 $.
Il passo base è banale. Supponendo ora che $ t_m<2^{2^{m+2}}-1 $, osserviamo che $ t_{m+1}=t_m(t_m+1)<2^{2^{m+2}}(2^{2^{m+2}}-1)=2^{2^{m+3}}-2^{2^{m+2}}<2^{2^{m+3}}-1 $.

*Bisogna dimostrare questa disuguaglianza, corollario dell'altro problema di Jordan (viewtopic.php?f=13&t=16466). Chi lo dimostra, dimostra (quasi) tutto. (appena avrò un po' di tempo in più proverò io stesso, ma nel frattempo lo lascio a tutti)

con allegato

Sia definita la sequenza $x_1:=2, \displaystyle x_{n+1}:=1+\prod_{1\le i\le n}{x_i}$ per ogni $n>0$.

Sia data una sequenza $a_1, a_2, \ldots, a_n$ di interi positivi tali che $\displaystyle \sum_{1\le i\le n}{a_i^{-1}}<1$.

Dimostrare che $\displaystyle \sum_{1\le i\le n}{a_i^{-1}}\le \sum_{1\le i\le n}{x_i^{-1}}<1$.

Visto che nessuno ti ha risposto ci provo io.

Siano $ \displaystyle P_n = \prod_{i=1}^n x_i, S_n = \sum_{i=1}^n \dfrac{1}{x_i} $. E' facile vedere che $ P_{n+1}=P^2_n+P_n $. Mostriamo per induzione che $ S_n = 1 - \dfrac{1}{P_n} $. Per $ n=1 $ è banale. Supposto che la relazione valga per $ n $, si ha $ S_{n+1} = 1 - \dfrac{1}{P_n} + \dfrac{1}{x_{n+1}} = 1 - \dfrac{1}{P_n} + \dfrac{1}{P_n+1} = 1 - \dfrac{1}{P_n(P_n+1)} = 1 - \dfrac{1}{P_{n+1}} $ come volevamo. Ne segue che $ S_n < 1 $. Per l'altra disuguaglianza, se fosse $ \displaystyle S_n < \sum_{i=1}^n \dfrac{1}{a_i} $ si avrebbe $ \displaystyle \min \sum_{i=1}^n \dfrac{1}{a_i} \geq S_{n-1}+\dfrac{1}{x_n-1} = S_{n-1}+\dfrac{1}{P_{n-1}} = 1 $, contro le ipotesi.

[jordan]

Problema 115 da qui:

Siano $ p $ e $ q $ primi con $ q>5 $. Si dimostri che se $ q \mid 2^p+3^p $, allora $ q>p $.

O è molto semplice o ho molto segato

$q\mid 2^p+3^p \iff (2\cdot3^{-1})^p\equiv -1 \pmod{q}$ se q diverso da 2,3, quindi $(2\cdot 3^{-1})^{2p}\equiv 1 \pmod{q}$ e quindi $ord_q{(2\cdot 3^{-1})}\in \{1,2,p,2p\}$
Nel primo caso si trova $3\equiv 2 \pmod {q}$ assurdo, nel secondo $9\equiv 4 \pmod {q}$ assurdo se $q>5$. Negli altri due casi ho ($ord_n(a)\mid \phi(n)$) che $p\mid q-1$ o $2p\mid q-1$ che in entrambi i casi implica $p<q$.

Detto $a:=2\cdot 3^{-1}$ in $\mathbb{Z}/p\mathbb{Z}$, poichè $a^p=-1$ allora $\text{ord}_q(a) \in \{2, 2p\}$ (Sonner, nota che il fattore $2$ ci deve stare..): come hai (giustamente) scritto te, il caso $\text{ord}_q(a)=2$ e' impossibile se $q>5$. L'unico caso rimanente e' $2p=\text{ord}_q(a)\mid \varphi(q)=q-1 \implies q\ge 2p+1$. []

[jordan]

Problema 116 da qui

Dati $a>b>1$ interi positivi, sia $x_n=\frac{a^n-1}{b^n-1}$. Trovare il minimo $d$ tale che per ogni $a,b$ la successione non contiene $d$ numeri primi consecutivi.

Suppongo che per qualche $a$ e $b$ esistano almeno due primi consecutivi nella successione, avrò quindi che $b^n-1\mid a^n-1$ e $b^{n+1}-1\mid a^{n+1}-1$, da cui
$b-1\mid a^n-1$ e $b-1\mid a^{n+1}-1$ e di conseguenza $a^n\equiv 1 \pmod{b-1}$ e $a^{n+1}\equiv 1 \pmod{b-1}$.
Quindi ho che $ord_{b-1}{a}\mid n$ e $ord_{b-1}{a}\mid n+1$ e perciò $ord_{b-1}{a}=1 \Longrightarrow b-1\mid a-1$.

Poichè i due numeri $x_n$ e $x_{n+1}$ devono essere due primi $p$ e $q$, ho che:
$p(b^n-1)=a^n-1\Longrightarrow p(b-1)(b^{n-1}+...+1)=(a-1)(a^{n-1}+...+1)$
Ma $a-1=k(b-1)$, quindi:
$p(b^{n-1}+...+1)=k(a^{n-1}+...+1)$

Ora $p$ divide $k$ oppure divide $a^{n-1}+...+1$.

• Se $p$ divide $a^{n-1}+...+1$, allora $k$ divide $b^{n-1}+...+1$.
  Poi ho che $q(b^{n+1}-1)=a^{n+1}-1 \Longrightarrow q(b^{n}+...+1)=k(a^{n}+...+1)$; se in questo caso $q$ dividesse $k$, dovrei avere che $a^n+...+1$ divide $b^n+...+1$, che è impossibile perchè $b<a$; quindi ho anche che $k$ divide $b^n+...+1$.
  Quindi $k\mid b^{n-1}+...+1$ e $k\mid b^{n}+...+1 \Longrightarrow k\mid b^n$, ma ho anche che $k\mid b^n-1$, quindi dovrei avere $k=1$, che è impossibile perchè otterrei
  $a-1=b-1$.
• Se invece $p$ divide $k$, ho che $a^{n-1}+...+1$ divide $b^{n-1}+...+1$, ma poichè $b<a$, l'unica possibiltà è che $n$ sia uguale a 1.

Quindi se ho che due termini consecutivi della successione sono primi allora il primo è $x_1$ e perciò posso avere al massimo due primi consecutivi.
E posso effettivamente averne due consecutivi, per esempio prendendo $b=2$ e $a=4$, da cui per $n=1$ e $n=2$ ottengo $x_1=3$ e $x_2=5$.

[jordan]

Problema 117 da qui:

Dati $k$ ed $m$ interi positivi con $m$ dispari, dimostrare che esiste $n$ tale che $2^k\mid n^n-m$.

P.S. spero vada bene

Lavorando in $S_n:= (\mathbb{Z}/2^n\mathbb{Z})^*$ (l'insieme dei residui mod $2^n$ e coprimi con esso), e' sufficiente dimostrare che la funzione $f_n(x):= x^x$ e' bigettiva in $S_n$. $f_1(x)$ e' chiaramente bigettiva in $S_1$, e supponiamo lo sia anche in $S_n$. Se in $S_n$ fosse $f_n(x)=y$, allora in $S_{n+1}$ sarà $f_{n+1}(x):=z \in \{y,y+2^n\}$ e $f_{n+1}(x+2^n)=(x+2^n)^{x+2^n}=\displaystyle \sum_{0\le i\le x+2^n}{\binom{x+2^n}{i}2^{ni}x^{x+2^n-i}}$ $=x^{x+2^n}+2^n\left((x+2^n)(x^{x+2^n-1})\right)=x^x\cdot x^{2^n}+2^n=z+2^n \in \{y,y+2^n\}$. Allora $f_{n+1}(x)$ e' bigettiva in $S_{n+1}$. []

Ps. Bel problema! Il prossimo qui

[jordan]

Prblema 118 da qui:

Dato un primo dispari $ p $, mostrare che esistono interi $ 1\le a_1<a_2<\cdots<a_{p-1}<a_p\le 2p^2 $ tali che tutte le somme $ a_i+a_j $ sono distinte, per ogni $ 1\le i<j\le p $.

Dario ci ha dato una soluzione qui..

Vedrò di contattarlo per vedere se e' disponibile a postare il problema seguente alla staffetta..