Problema n.3 Cesenatico 2014

[Aschie4589]

Ciao a tutti,
sono ancora nuovo sul forum e vorrei postare il terzo problema di quest'anno di Cesenatico, al quale ho dato una soluzione che però non mi convince. Sono di seconda, probabilmente non capirò tutto quello che proporrete, ma ci proverò. Ecco il testo:

Per ogni intero positivo $ n $, sia $ D_n $ il massimo comune divisore di tutti i numeri della forma $ a^n+(a+1)^n+(a+2)^n $ al variare di $ a $ fra tutti gli interi positivi.
(a) Dimostrare che, per ogni $ n $, $ D_n $ è della forma $ 3^k $ per qualche intero $ k \ge 0 $.
(b) Dimostrare che, per ogni $ k \ge 0 $, esiste un intero $ n $ tale che $ D_n = 3^k $

Grazie in anticipo!

[lucaboss98]

Allora,
Per il punto (a)
Ok visto che $ D_n $ divide tutti i numeri si ha $ a^n + (a+1)^n + (a+2)^n \equiv 0 \mod{D_n} $
Visto che $ a $ può assumere qualsiasi numero intero positivo, sia $ a= D_n $ , allora abbiamo $ D_n^n + (D_n+1)^n + (D_n+2)^n \equiv 0 \mod{D_n} $ e quindi $ 1 + 2^n \equiv 0 \mod{D_n} $.
Sia ora $ a=D_n +1 $ abbiamo $ (D_n+1)^n + (D_n+2)^n + (D_n+3)^n \equiv 0 \mod{D_n} $ e quindi $ 1 + 2^n + 3^n \equiv 0 \mod{D_n} $ , che , unito a quanto detto prima ci restituisce $ 3^n \equiv 0 \mod{D_n} \rightarrow D_n = 3^k $
Per il punto (b) , almeno nella mia soluzione (purtroppo non in gara, non avendola fatta) ho usato LTE (Lifting The Exponent) , quindi ti consiglio di dare un occhiata qui Lemma LTE .
Aperta questa parentesi, torniamo al problema.
Se $ k=0 $ basta prendere $ n=2m $ ed hai $ D_{2m} = 1 =3^0 $.
Ora quindi troviamola per tutti i numeri positivi.
Dimostrerò che $ D_{3^k} = 3^{k+1} $ va bene per induzione su $ a $
Passo base: $ a=1 $ si ha $ 1^{3^k} + (2)^{3^k} + (2)^{3^k} = 1 + 2^{3^k} + 3^{3^k} $ , ma $ 3^{k+1} | 3^{3^k} $ quindi mi rimane $ 1 + 2^{3^k} $
Ora $ V_3(1+2^{3^k})=V_3 (1+2) + V_3 (3^k) = k+1 $ , quindi ok.
Passo induttivo: se divide $ a^{3^k} + (a+1)^{3^k} + (a+2)^{3^k} $ affinchè divida $ (a+1)^{3^k} + (a+2)^{3^k} + (a+3)^{3^k} $ deve dividere $ (a+3)^{3^k} - a^{3^k} $
Ora $ V_3( (a+3)^{3^k} - a^{3^k} ) = V_3 (a+3-a) + V_3 (3^k) = k+1 $ ed è confermato anche il passo induttivo.
Visto che $ D_n=3^j $ si ha la tesi, spero di essere stato chiaro

[Aschie4589]

Si, grazie, molto chiaro! In realtà ho fatto qualcosa di quasi identico, anche se ho considerato un fattore $ p^\alpha $ al posto di $ D_n $ intero. E nella seconda parte ho fatto una cosa simile, dimostrando per induzione che se $ 3^k \mid a^n + (a+1)^n + (a+2)^n $ allora $ 3^{3k}\mid a^{3n}+(a+1)^{3n}+(a+2)^{3n} $. Può essere per questo che non mi hanno dato il punteggio pieno nell'esercizio? Proprio non capisco... e tra l'altro trovo troppo complicata la soluzione ufficiale... mah
Comunque grazie ancora
edit: in realtà ho fatto il discorso con le congruenze, perchè non so se con la divisibilità basta

[lucaboss98]

Si, grazie, molto chiaro! In realtà ho fatto qualcosa di quasi identico, anche se ho considerato un fattore $ p^\alpha $ al posto di $ D_n $ intero. E nella seconda parte ho fatto una cosa simile, dimostrando per induzione che se $ 3^k \mid a^n + (a+1)^n + (a+2)^n $ allora $ 3^{3k}\mid a^{3n}+(a+1)^{3n}+(a+2)^{3n} $. Può essere per questo che non mi hanno dato il punteggio pieno nell'esercizio? Proprio non capisco... e tra l'altro trovo troppo complicata la soluzione ufficiale... mah
Comunque grazie ancora
edit: in realtà ho fatto il discorso con le congruenze, perchè non so se con la divisibilità basta

Che avevi messo come passo base? Comunque non so precisamente tu cosa hai scritto però se vedi la classifica, anche fra gli ori molti hanno preso $ 6 $ punti a questo problema.

[Aschie4589]

Stavo per scrivere il passaggio ma mi rendo conto di non essere più sicuro su come ho fatto appunto il passo base, non mi ricordo bene ma potrei aver posto dei determinati valori ad $ a $ e a $ b $... E non sono sicuro che una cosa del genere vada bene usando l'induzione

[jordan]

E nella seconda parte ho fatto una cosa simile, dimostrando per induzione che se $ 3^k \mid a^n + (a+1)^n + (a+2)^n $ allora $ 3^{3k}\mid a^{3n}+(a+1)^{3n}+(a+2)^{3n} $. Può essere per questo che non mi hanno dato il punteggio pieno nell'esercizio? Proprio non capisco... e tra l'altro trovo troppo complicata la soluzione ufficiale... mah

[Il tuo $3k$ dovrebbe essere sostituito con un $k+1$, no?]

Credo di rispondere anche a nome degli altri correttori dell'esercizio 3: dimostrare che per ogni $k$ esiste un $n$ tale che $3^k$ divide $D_n$ non è equivalente a mostrare che esiste un $n$ tale che $D_n$ è esattamente $3^k$.

Piu' esplicitamente, il passo dell'induzione era del tipo: se $3^k$ divide $a^n+(a+1)^{n}+(a+2)^n$, ma $3^{k+1}$ non divide $a^n+(a+1)^{n}+(a+2)^n$, allora $3^{k+1}$ divide $a^{3n}+(a+1)^{3n}+(a+2)^{3n}$, ma $3^{k+2}$ non divide $a^{3n}+(a+1)^{3n}+(a+2)^{3n}$.

[gpzes]

$\begin{align}
& a) \\
& {{1}^{n}}+{{2}^{n}}+{{3}^{n}}=p\alpha \quad ,p\quad primo\quad divisore\quad di\quad {{D}_{n}}>1. \\
& {{2}^{n}}+{{3}^{n}}+{{4}^{n}}=p\beta \\
& ...\downarrow \\
& {{p}^{n}}+{{(p+1)}^{n}}+{{(p+2)}^{n}}=p\gamma \to \quad {{\equiv }_{p}}0{{\equiv }_{p}}{{1}^{n}}+{{2}^{n}} \\
& \to {{1}^{n}}+{{2}^{n}}+{{3}^{n}}{{\equiv }_{p}}0\to p\left| {{3}^{n}}\to p=3. \right.\Rightarrow {{D}_{n}}={{3}^{k}}\quad per\quad qualche\quad k>0. \\
& \\
& b) \\
& Sia\quad {{D}_{n}}={{3}^{k}}.\quad {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}{{\equiv }_{3}}0. \\
& Se\quad n\quad pari\quad \ge 2\to {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}{{\equiv }_{3}}2\to assurdo!!! \\
& Se\quad n\quad dispari\quad \ge 2\to \quad (a+1)\left| {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}\to \right.(a+1)\left| {{3}^{k}}\quad \forall a.\to assurdo!!! \right. \text{ QUI C'ERA ERRORE!!}\\
& Allora\quad n=1.\to k=1.\to {{D}_{n}}=3. \\
\end{align}$

[lucaboss98]

$\begin{align}
& a) \\
& {{1}^{n}}+{{2}^{n}}+{{3}^{n}}=p\alpha \quad ,p\quad primo\quad divisore\quad di\quad {{D}_{n}}>1. \\
& {{2}^{n}}+{{3}^{n}}+{{4}^{n}}=p\beta \\
& ...\downarrow \\
& {{p}^{n}}+{{(p+1)}^{n}}+{{(p+2)}^{n}}=p\gamma \to \quad {{\equiv }_{p}}0{{\equiv }_{p}}{{1}^{n}}+{{2}^{n}} \\
& \to {{1}^{n}}+{{2}^{n}}+{{3}^{n}}{{\equiv }_{p}}0\to p\left| {{3}^{n}}\to p=3. \right.\Rightarrow {{D}_{n}}={{3}^{k}}\quad per\quad qualche\quad k>0. \\
& \\
& b) \\
& Sia\quad {{D}_{n}}={{3}^{k}}.\quad {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}{{\equiv }_{3}}0. \\
& Se\quad n\quad pari\quad \ge 2\to {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}{{\equiv }_{3}}2\to assurdo!!! \\
& Se\quad n\quad dispari\quad \ge 2\to \quad 2(a+1)\left| {{a}^{n}}+{{(a+1)}^{n}}+{{(a+2)}^{n}}\to \right.(a+1)\left| {{3}^{k}}\quad \forall a.\to assurdo!!! \right. \\
& Allora\quad n=1.\to k=1.\to {{D}_{n}}=3. \\
\end{align}$

Non sto capendo bene cosa hai fatto, ma non ci dovrebbe essere nessun assurdo nel punto (b) e nel punto (a) chi ti dice che tale primo esiste?

[gpzes]

.

[lucaboss98]

Ma il punto (b) ti chiede di dimostrare che per ogni $ k $ esiste un $ D_n $, mi pare tu l'abbia fatto solo per $ k=0,1 $. Comunque per il punto (a) rileggendolo può andare anche perché il caso che non hai trattato, $ D_n=1 $ basta ricordarsi che $ 1=3^0 $ comunque credo vada specificato.

[gpzes]

Si..ho fatto estrema sintesi senza dettagli...ma forse ho male interpretato problema...
chiedo scusa..trovato errore !!
$
a) \\
1^n+2^n+3^n=p\alpha,\text { dove p è un primo divisore di } D_n>1.(p \text{ esisterebbe per teo fond.le aritmetica.)}\\
2^n+3^n+4^n=p\beta \\
....+....+....=p\delta \\
\downarrow \quad \downarrow \quad \downarrow \quad \text{si arriverà a ...} \\
p^n+(p+1)^n+(p+2)^n=p\gamma \to \equiv_p 0 \equiv_p 1^n+2^n \\
\to 1^n+2^n+3^n \equiv_p 0 \to p\left| 3^n \to p=3. \right.\Rightarrow D_n=3^k \quad per\quad qualche\quad k>0. \\
\text{Quindi, se } D_n>1 \text{ allora può avere solo forma } D_n=3^k;\text{ altrimenti è } D_n=1=3^0. \\
b) \\
Sia\quad D_n=3^k.\quad a^n+(a+1)^n+(a+2)^n\equiv_3 0,\text{ se k }\ge 1. \\
\text{Ma se n pari}\ge 2\to a^n+(a+1)^n+(a+2)^n\equiv_3 2, \text{ per ogni a intero positivo }\to assurdo!!! \\
\text{Quindi, per ottenere } D_n=3^0=1 ,\text{ basterebbe prendere un qualsiasi n pari, } n\ge 2. \\

Caso\quad n\quad dispari.\text { Consideriamo due sequenze successive, ossia } (a+1)^n+(a+2)^n+(a+3)^n \text{ e } a^n+(a+1)^n+(a+2)^n. \\
\text{Allora }\quad D_n \text { deve dividere anche la loro differenza: }

\sum\limits_{j=1}^{n}{\left( \begin{align}
n \\
j \\
\end{align} \right) } {a^{n-j}} 3^j. \\

\text{L'idea è di scegliere opportunamente n dispari affinchè } D_n=3^k, \text{ prescindendo dai valori di a!! Ossia concentrandosi sui coefficienti!!! } \\
\text{Allora scegliamo } n=3^{k-1}.\text { Così facendo, comparirebbe un fattore } 3^k \text{ in tutti i termini dello sviluppo della sommatoria.} \\
\text{Inoltre, analizzando il primo termine, che diventerebbe } 3^ka ^{(3^{k-1})-1},\text{ posso osservare che } 3^{k+1} \\
\text{ non potrebbe dividerlo per ogni scelta del valore di a!!} \\
\text{Conclusione: la più alta potenza che dividerebbe } D_n,\text{ per ogni valore di a, sarebbe proprio } 3^k. \\
\text{Quindi, se } n=3^{k-1}, D_{3^{k-1}}=3^k. \\
$