Chiamiamo $ r(k) $ la somma dei resti della divisione di k per: 1,....k-1.Mostrare che esistono infiniti k tali che $ r(k)=r(k-1) $
E' un esercizio carino... Dalla gara Kurschak.
Somme di residui mod (variabile)
Somme di residui mod (variabile)
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
-
exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
perchè sempre le potenze di due???
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
Chiamo $ a_w $ i resti della divisione tra $ k $ e i numeri tra $ 1 $ e $ k-1 $.
$ k=a_{k-1} \hspace{0.2cm}(mod \hspace{0.2cm}k-1) $
$ k=a_{k-2} \hspace{0.2cm}(mod \hspace{0.2cm}k-2) $
$ \cdots $
Si ha quindi che $ r(k)=a_1+\dots+a_{k-1} $.
Analizziamo $ r(k-1) $: per tutti gli $ a_i>0 $ si ha $ k-1=a_i-1(mod \hspace{0.2cm}i) $. Per gli $ a_j=0 $ il resto della divisione per $ k-1 $ sara $ j-1 $. Notiamo inoltre che se un resto e' nullo allora allora $ j_z $ e' un divisore di $ k $ diverso da $ k $.
Abbiamo quindi, con $ i $ che non divide $ k $ e $ j_z $ divisore di $ k $ e chiamando $ C $ il numero dei divisori di $ k $ diversi da $ k $:
$ r(k-1)=\sum{(a_i-1)}+\sum{(j_z-1)} $
$ r(k-1)=\sum{a_i}-((k-1)-C)+\sum{j_z}-C $
$ r(k-1)=\sum{a_i}+\sum{j_z}-k+1 $
Se $ r(k-1)=r(k) $ allora si avrebbe
$ \sum{a_i}+\sum{j_z}-k+1=\sum{a_i} $
$ \sum{j_z}=k-1 $
Dobbiamo trovare i numeri la cui somma dei divisori sia uguale al numero stesso meno uno. Le potenze di due soddisfano queste condizioni. La somma dei divisori per $ 2^x $:
$ 1+2+4+\cdots+2^{x-1}=\frac{2^x-1}{2-1}=2^x-1 $
EDIT: a posto ora. grazie Carlein
$ k=a_{k-1} \hspace{0.2cm}(mod \hspace{0.2cm}k-1) $
$ k=a_{k-2} \hspace{0.2cm}(mod \hspace{0.2cm}k-2) $
$ \cdots $
Si ha quindi che $ r(k)=a_1+\dots+a_{k-1} $.
Analizziamo $ r(k-1) $: per tutti gli $ a_i>0 $ si ha $ k-1=a_i-1(mod \hspace{0.2cm}i) $. Per gli $ a_j=0 $ il resto della divisione per $ k-1 $ sara $ j-1 $. Notiamo inoltre che se un resto e' nullo allora allora $ j_z $ e' un divisore di $ k $ diverso da $ k $.
Abbiamo quindi, con $ i $ che non divide $ k $ e $ j_z $ divisore di $ k $ e chiamando $ C $ il numero dei divisori di $ k $ diversi da $ k $:
$ r(k-1)=\sum{(a_i-1)}+\sum{(j_z-1)} $
$ r(k-1)=\sum{a_i}-((k-1)-C)+\sum{j_z}-C $
$ r(k-1)=\sum{a_i}+\sum{j_z}-k+1 $
Se $ r(k-1)=r(k) $ allora si avrebbe
$ \sum{a_i}+\sum{j_z}-k+1=\sum{a_i} $
$ \sum{j_z}=k-1 $
Dobbiamo trovare i numeri la cui somma dei divisori sia uguale al numero stesso meno uno. Le potenze di due soddisfano queste condizioni. La somma dei divisori per $ 2^x $:
$ 1+2+4+\cdots+2^{x-1}=\frac{2^x-1}{2-1}=2^x-1 $
EDIT: a posto ora. grazie Carlein
Ultima modifica di leonim il 20 lug 2008, 18:25, modificato 1 volta in totale.
durante questo fine settimana mi è venuto in mente come (forse) risolvere questo problema, ora provo a buttare giù la mia soluzione.
consideriamo le potenze di 2. Queste sono congrue a 0 modulo uno e tutte le potenze di due minori di esse. Per qualsiasi altro modulo compreso tra 1 e $ $k-1 $, tali potenze sono congrue a "qualcosa" diverso da 0, e quindi $ $k-1 $ per questi moduli è congruo al residuo corrispondente di $ $k $ meno 1. Inoltre sappiamo che $ $k-1 $ è congruo a $ $-1=2^a-1 (mod 2^a) $ con $ $2^a < k $ . Dunque la somma dei residui mod (variabile) di k-1 sarà uguale alla somma dei residui mod (variabile) di k meno k-x-1 (che sarebbe il numero di moduli non potenze di 2 minori di k e diverse da 1, poichè tutti i numeri sono congrui mod 1) più la somma di tutte le potenze di 2 minori di k diminuite di 1. Se $ $r(k)=r(k-1) $ , allora ponendo $ $r(k)=h $ abbiamo $ $h=h-(k-x-1)+(2+4+8+...+2^{x-1})-(x-1) $ con $ $2^{x-1} $ la più piccola potenza di 2 minore di k. Allora $ $k=2^x $ e, sostituendo, otteniamo $ $(2+4+8+...+2^{x-1})=2^x-2 $ . E' fatto noto che la somma di tutte le potenze di 2 minori o uguali a $ $2^{x-1} $ con esponente naturale è effettivamente uguale a $ $2^x-2 $ , per cui l'uguaglianza è sempre verificata. Dunque $ $r(k)=r(k-1) $ con k=qualsiasi potenza di 2.
Per favore mi potete dire se è giusta? Grazie mille
consideriamo le potenze di 2. Queste sono congrue a 0 modulo uno e tutte le potenze di due minori di esse. Per qualsiasi altro modulo compreso tra 1 e $ $k-1 $, tali potenze sono congrue a "qualcosa" diverso da 0, e quindi $ $k-1 $ per questi moduli è congruo al residuo corrispondente di $ $k $ meno 1. Inoltre sappiamo che $ $k-1 $ è congruo a $ $-1=2^a-1 (mod 2^a) $ con $ $2^a < k $ . Dunque la somma dei residui mod (variabile) di k-1 sarà uguale alla somma dei residui mod (variabile) di k meno k-x-1 (che sarebbe il numero di moduli non potenze di 2 minori di k e diverse da 1, poichè tutti i numeri sono congrui mod 1) più la somma di tutte le potenze di 2 minori di k diminuite di 1. Se $ $r(k)=r(k-1) $ , allora ponendo $ $r(k)=h $ abbiamo $ $h=h-(k-x-1)+(2+4+8+...+2^{x-1})-(x-1) $ con $ $2^{x-1} $ la più piccola potenza di 2 minore di k. Allora $ $k=2^x $ e, sostituendo, otteniamo $ $(2+4+8+...+2^{x-1})=2^x-2 $ . E' fatto noto che la somma di tutte le potenze di 2 minori o uguali a $ $2^{x-1} $ con esponente naturale è effettivamente uguale a $ $2^x-2 $ , per cui l'uguaglianza è sempre verificata. Dunque $ $r(k)=r(k-1) $ con k=qualsiasi potenza di 2.
Per favore mi potete dire se è giusta? Grazie mille
marco
Ma è la stessa cosa che ha scritto leonim.Cioè l'unica differenza sostanziale è che quello che lui ha scritto algebricamente tu l'hai detto a parole 
.
.Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
