Problema n.3 Cesenatico 2014

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Aschie4589
Messaggi: 9
Iscritto il: 15 apr 2014, 21:25

Problema n.3 Cesenatico 2014

Messaggio da 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ò. :D 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
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: Problema n.3 Cesenatico 2014

Messaggio da 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 :D
Ultima modifica di lucaboss98 il 14 mag 2014, 23:16, modificato 1 volta in totale.
Aschie4589
Messaggi: 9
Iscritto il: 15 apr 2014, 21:25

Re: Problema n.3 Cesenatico 2014

Messaggio da 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
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: Problema n.3 Cesenatico 2014

Messaggio da lucaboss98 »

Aschie4589 ha scritto: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
Messaggi: 9
Iscritto il: 15 apr 2014, 21:25

Re: Problema n.3 Cesenatico 2014

Messaggio da 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 :oops:
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Problema n.3 Cesenatico 2014

Messaggio da jordan »

Aschie4589 ha scritto: 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}$.
The only goal of science is the honor of the human spirit.
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Problema n.3 Cesenatico 2014

Messaggio da 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}$
Ultima modifica di gpzes il 17 mag 2014, 04:45, modificato 2 volte in totale.
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: Problema n.3 Cesenatico 2014

Messaggio da lucaboss98 »

gpzes ha scritto:$\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?
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Problema n.3 Cesenatico 2014

Messaggio da gpzes »

.
Ultima modifica di gpzes il 16 mag 2014, 19:03, modificato 3 volte in totale.
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: Problema n.3 Cesenatico 2014

Messaggio da 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.
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Problema n.3 Cesenatico 2014

Messaggio da gpzes »

:oops: 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. \\
$
Rispondi