Japan Mathematical Olympiad Finals 2009
Japan Mathematical Olympiad Finals 2009
trovare tutti gli n positivi tali che $ \displaystyle 8^n + n $ è divisibile per $ \displaystyle 2^n + n $
Ci provo...
Riscriviamo nelle seguenti forme:
$ \displaystyle~2^n+n|8^n+n=4^n(2^n+n-n)+n\Rightarrow 2^n+n|n(4^n-1)~~~(1) $
$ \displaystyle~2^n+n|8^n+n=8^n-2^n+2^n+n\Rightarrow 2^n+n|2^n(4^n-1)~~~(2) $
Dalla (2) ricaviamo che, se n è dispari, deve essere $ \displaystyle~2^n+n|4^n-1=2^n(2^n+n-n)-1\Rightarrow 2^n+n|2^n n+1= $$ \displaystyle~n(2^n+n-n)+1\Rightarrow 2^n+n|n^2-1 $, ma $ \displaystyle~n>1\Rightarrow 2^n+n>n^2-1>0 $, quindi se n è dispari 1 è l'unica soluzione.
Se n è pari, si può scrivere $ \displaystyle~n=2^c x $, con x dispari.
Dalla (1) si ha $ \displaystyle~2^n+n|2^c x(4^n-1) $ che, confrontato con la (2), dà $ \displaystyle~2^n+n|2^c(4^n-1)\Rightarrow 2^{n-c}+x|2^{2n}-1 $
Ma $ \displaystyle~2^{2n}-1=2^{n+c}(2^{n-c}+x-x)-1 $, quindi $ \displaystyle~2^{n-c}+x|2^{n+c}x+1=2^{2c}x(2^{n-c}+x-x)+1\Rightarrow 2^{n-c}+x|2^{2c}x^2-1=n^2-1 $
Rimoltiplicando ambo le parti per $ \displaystyle~2^c $ si ottiene $ \displaystyle~2^n+n|2^c(n^2-1) $. Perché abbia senso deve essere $ \displaystyle~2^n+n\le 2^c(n^2-1)\le n(n^2-1)\Rightarrow 2^n\le n(n^2-2) $, che dà n < 10. Si può verificare che $ \displaystyle~n=8 $ non è soluzione.
Le uniche soluzioni sono quindi 1, 2, 4 e 6.
Riscriviamo nelle seguenti forme:
$ \displaystyle~2^n+n|8^n+n=4^n(2^n+n-n)+n\Rightarrow 2^n+n|n(4^n-1)~~~(1) $
$ \displaystyle~2^n+n|8^n+n=8^n-2^n+2^n+n\Rightarrow 2^n+n|2^n(4^n-1)~~~(2) $
Dalla (2) ricaviamo che, se n è dispari, deve essere $ \displaystyle~2^n+n|4^n-1=2^n(2^n+n-n)-1\Rightarrow 2^n+n|2^n n+1= $$ \displaystyle~n(2^n+n-n)+1\Rightarrow 2^n+n|n^2-1 $, ma $ \displaystyle~n>1\Rightarrow 2^n+n>n^2-1>0 $, quindi se n è dispari 1 è l'unica soluzione.
Se n è pari, si può scrivere $ \displaystyle~n=2^c x $, con x dispari.
Dalla (1) si ha $ \displaystyle~2^n+n|2^c x(4^n-1) $ che, confrontato con la (2), dà $ \displaystyle~2^n+n|2^c(4^n-1)\Rightarrow 2^{n-c}+x|2^{2n}-1 $
Ma $ \displaystyle~2^{2n}-1=2^{n+c}(2^{n-c}+x-x)-1 $, quindi $ \displaystyle~2^{n-c}+x|2^{n+c}x+1=2^{2c}x(2^{n-c}+x-x)+1\Rightarrow 2^{n-c}+x|2^{2c}x^2-1=n^2-1 $
Rimoltiplicando ambo le parti per $ \displaystyle~2^c $ si ottiene $ \displaystyle~2^n+n|2^c(n^2-1) $. Perché abbia senso deve essere $ \displaystyle~2^n+n\le 2^c(n^2-1)\le n(n^2-1)\Rightarrow 2^n\le n(n^2-2) $, che dà n < 10. Si può verificare che $ \displaystyle~n=8 $ non è soluzione.
Le uniche soluzioni sono quindi 1, 2, 4 e 6.
Non riesco a capire il modo in cui hai dimostrato questo passaggio. La (2) ci dice che $ 2^n + n|2^n(4^n - 1) $ ma nel nostro caso è $ c < n $ (basta provare per induzione che $ c < 2^c $). Mi puoi aiutare?kn ha scritto: Dalla (1) si ha $ \displaystyle~2^n+n|2^c x(4^n-1) $ che, confrontato con la (2), dà $ \displaystyle~2^n+n|2^c(4^n-1) $
Nessun uomo è un'isola (J. Donne)
Diamo un nome a tutte le equazioni: $ \displaystyle~2^n+n|2^c x(4^n-1)~~~(3) $
La (2) dice che $ \displaystyle~2^n+n|2^n(4^n-1) $, quindi i fattori dispari di $ \displaystyle~2^n+n $ sono già tutti coperti da $ \displaystyle~4^n-1 $ (ovvero $ \displaystyle~4^n-1 $ è multiplo del prodotto dei fattori dispari), di conseguenza x, nella (3), è superfluo.
La (3) quindi si può riscrivere come $ \displaystyle~2^n+n|2^c(4^n-1) $.
Un altro modo per dimostrarlo:
La (3) ci dice che basta $ \displaystyle~2^c $ per coprire (non so qual è il verbo giusto) tutti i fattori 2 di $ \displaystyle~2^n+n $, dato che x e $ \displaystyle~4^n-1 $ sono dispari.
Quindi puoi riscrivere la (2) sempre come sopra.
Un altro modo ancora:
$ \displaystyle~A|B \wedge A|C\Rightarrow A|MCD(B, C) $, con $ \displaystyle~A=2^n+n $, $ \displaystyle~B=2^n(4^n-1) $ e $ \displaystyle~C=2^c x(4^n-1) $
La (2) dice che $ \displaystyle~2^n+n|2^n(4^n-1) $, quindi i fattori dispari di $ \displaystyle~2^n+n $ sono già tutti coperti da $ \displaystyle~4^n-1 $ (ovvero $ \displaystyle~4^n-1 $ è multiplo del prodotto dei fattori dispari), di conseguenza x, nella (3), è superfluo.
La (3) quindi si può riscrivere come $ \displaystyle~2^n+n|2^c(4^n-1) $.
Un altro modo per dimostrarlo:
La (3) ci dice che basta $ \displaystyle~2^c $ per coprire (non so qual è il verbo giusto) tutti i fattori 2 di $ \displaystyle~2^n+n $, dato che x e $ \displaystyle~4^n-1 $ sono dispari.
Quindi puoi riscrivere la (2) sempre come sopra.
Un altro modo ancora:
$ \displaystyle~A|B \wedge A|C\Rightarrow A|MCD(B, C) $, con $ \displaystyle~A=2^n+n $, $ \displaystyle~B=2^n(4^n-1) $ e $ \displaystyle~C=2^c x(4^n-1) $
Ultima modifica di kn il 01 mar 2009, 19:06, modificato 1 volta in totale.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
intendevikn ha scritto:Un altro modo ancora:
$ \displaystyle~A|B \wedge A|C\Rightarrow A|MCD(A, B) $, con $ \displaystyle~A=2^n+n $, $ \displaystyle~B=2^n(4^n-1) $ e $ \displaystyle~C=2^c x(4^n-1) $
$ \displaystyle~A|B \wedge A|C\Rightarrow A|MCD(B, C) $
perche' se $ ~A|B $ allora certo che $ ~A|MCD(A, B)=A $
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Ah ecco cosa mi mancava! Sembra molto utile... Grazie mille, mi stai insegnando un po' di cose ultimamentekn ha scritto:$ \displaystyle~A|B \wedge A|C\Rightarrow A|MCD(B, C) $, con $ \displaystyle~A=2^n+n $, $ \displaystyle~B=2^n(4^n-1) $ e $ \displaystyle~C=2^c x(4^n-1) $
Nessun uomo è un'isola (J. Donne)