11 | s(n) con n in {m-19,...,m+19}
Inviato: 03 apr 2012, 01:05
Mostrare che, dati 39 interi positivi consecutivi, ne esiste almeno uno la cui somma delle cifre e' divisibile per 11.
Testo nascosto:
Indico con $S(n)$ la somma delle cifre di $n$ ($n \in \mathbb{N}$).
Dimostro che, per ogni numero naturale $n$, $S(n+1)=S(n)+1-9k$, dove $k$ è il più grande numero naturale tale che $10^k \mid n+1$.
Posso scrivere $n+1$ come $h10^k$ ($h \in \mathbb{N}$). La formula risulta vera per $n=0$, suppongo vero per $n-1$ e dimostro per $n$.
$S(h10^k)=S(h10^k-1)+1-9k$
$S(h10^k)$ è banalmente uguale a $S(h)$; riscrivo $1$ come $10^k-9 \sum_{i=0}^{k-1} 10^i$, quindi
$S(h)=S(h10^k-(10^k-9 \displaystyle\sum_{i=0}^{k-1} 10^i ))+1-9k$
$S(h)=S((h-1)10^k+9\displaystyle\sum_{i=0}^{k-1} 10^i)+1-9k$
$S(h)=S(h-1)+9k+1-9k$
$S(h)=S(h-1)+1$
Che risulta vero se $h$ non è un multiplo di $10$, perché da $h$ a $h-1$ diminuisce di 1 la cifra delle unità, mentre tutte le altre cifre restano invariate; ma $h$ non può essere un multiplo di $10$, perché altrimenti $10^{k+1} \mid n + 1$, mentre avevamo detto che $k$ era il più grande intero positivo tale che $10^k \mid n+1$. Quindi la formula risulta vera sempre.
Chiamo $a_1, a_2, ... a_{39}$ la sequenza dei 39 interi positivi e $k_1, k_2, ... k_{39}$ una sequenza di numeri naturali tali che $k_i$ è il più grande numero naturale tale che $10^{k_i} \mid a_i \forall 1 \leq i \leq 39$. Pongo $m=S(a_1-1)$.
Dimostro che $S(a_i)=m+i-9 \displaystyle\sum_{j=1}^i k_j$
È vero per $i=1$, suppongo vero per $i$ e dimostro per $i+1$:
$S(a_{i+1})=m+i+1-9 \displaystyle\sum_{j=1}^{i+1} k_j$
$S(a_{i+1})=m+i+1-9k_{i+1}-9 \displaystyle\sum_{j=1}^i k_j$
$S(a_{i+1})=S(a_i)-9k_{i+1}+1$ Che è vero per quanto dimostrato in precedenza.
Dato che la sequenza $a_1, a_2, ... a_{39}$ è composta da numeri interi consecutivi, uno (e soltanto uno) tra i primi 10 elementi sarà multiplo di 10. Suppongo che questo sia $a_c$ $(1 \leq c \leq 10)$. Gli unici multipli di 10 tra i 39 interi positivi della sequenza saranno quindi $a_c, a_{c+10}, a_{c+20}, a_{c+30}$ (quest'ultimo solo se $c \neq 10$). Di conseguenza, gli unici elementi della sequenza $k_1, k_2, ... k_{39}$ diversi da 0 saranno $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ (quest'ultimo sempre nel caso in cui $c \neq 10$).
Quindi $S(a_i)$ risulta uguale a:
$m+i$ se $1 \leq i < c$ $(c \neq 1)$
$m+i-9k_c$ se $c \leq i < c+10$
$m+i-9(k_c+k_{c+10})$ se $c+10 \leq i < c+20$
$m+i-9(k_c+k_{c+10}+k_{c+20})$ se $c+20 \leq i < c+30$
$m+i-9(k_c+k_{c+10}+k_{c+20}+k_{c+30})$ se $i \geq c+30$ $(c \neq 10)$
Inoltre, soltanto uno tra $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ può essere maggiore di 1:
Pongo $k_x > 1$ e $a_x = h10^{k_x}$ $(h \in \mathbb{N})$.
$a_{x+10y}=h10^{k_x}+10y=10(h10^{k-1}+y)$ $(y \in \mathbb{Z})$
Se $y$ non è un multiplo di 10, che è il nostro caso, allora $k_{x+10y}=1$. Quindi soltanto uno tra $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ può essere maggiore di 1.
Analizzo ora 3 casi separatamente: $k_c=k_{c+10}=1$, $k_c \neq 1$ e $k_{c+10} \neq 1$.
Caso 1: $k_c=k_{c+10}=1$ (Uno solo oppure nessuno tra $k_{c+20}$ e $k_{c+30}$ sarà diverso da 1)
Esamino solo i casi in cui $c \leq i < c+20$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+(i-c)+2$ se $c \leq i < c+10$
B) $m+c+(i-c)+4$ se $c+10 \leq i < c+20$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 0 e 9, estremi inclusi, avremo un elemento di $S(a_c), S(a_{c+1}), ... S(a_{c+9})$ per ogni classe di congruenza modulo 11 $(m+c+2), (m+c+3), ... (m+c+11)$, ovvero tutte tranne la classe $(m+c+1)$. A questa classe appartiene però $S(a_{c+19})$, del caso B). Quindi, indipendentemente dai valori di $m$ e di $c$, almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
Caso 2: $k_c \neq 1$ (di conseguenza $k_{c+10}, k_{c+20}, k_{c+30}$ sono tutti uguali a 1)
Esamino solo i casi in cui $c \leq i < c+20$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+2k_c+(i-c)$ se $c \leq i < c+10$
B) $m+c+2k_c+(i-c)+2$ se $c+10 \leq i < c+20$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 0 e 9, estremi inclusi, avremo un elemento di $S(a_c), S(a_{c+1}), ... S(a_{c+9})$ per ogni classi di congruenza modulo 11 $(m+c+2k_c+2), (m+c+2k_c+3),... (m+c+2k_c+11)$, ovvero tutte tranne la classe $(m+c+2k_c+1)$. A questa classe appartiene però $S(a_{c+19})$, del caso B). Quindi, indipendentemente dai valori di $m$, $c$, e di $k_c$ almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
Caso 3: $k_{c+10} \neq 1$ (di conseguenza $k_c, k_{c+20}, k_{c+30}$ sono tutti uguali a 1)
Esamino solo i casi in cui $c+10 \leq i < c+30$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+2k_{c+10}+(i-c)+2$ se $c+10 \leq i < c+20$
B) $m+c+2k_{c+10}+(i-c)+4$ se $c+20 \leq i < c+30$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 10 e 19, estremi esclusi, avremo un elemento di $S(a_{c+10}), S(a_{c+11})...S(a_{c+19})$ per ogni classe di congruenza modulo 11$(m+c+2k_{c+10}+1), (m+c+2k_{c+10}+2), ... (m+c+2k_{c+10}+10)$, ovvero tutte tranne la classe $(m+c+2k_{c+10})$. A questa classe appartiene però $S(a_{c+29})$, del caso B). Quindi, indipendentemente dai valori di $m$, $c$ e di $k_{c+10}$, almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
Dimostro che, per ogni numero naturale $n$, $S(n+1)=S(n)+1-9k$, dove $k$ è il più grande numero naturale tale che $10^k \mid n+1$.
Posso scrivere $n+1$ come $h10^k$ ($h \in \mathbb{N}$). La formula risulta vera per $n=0$, suppongo vero per $n-1$ e dimostro per $n$.
$S(h10^k)=S(h10^k-1)+1-9k$
$S(h10^k)$ è banalmente uguale a $S(h)$; riscrivo $1$ come $10^k-9 \sum_{i=0}^{k-1} 10^i$, quindi
$S(h)=S(h10^k-(10^k-9 \displaystyle\sum_{i=0}^{k-1} 10^i ))+1-9k$
$S(h)=S((h-1)10^k+9\displaystyle\sum_{i=0}^{k-1} 10^i)+1-9k$
$S(h)=S(h-1)+9k+1-9k$
$S(h)=S(h-1)+1$
Che risulta vero se $h$ non è un multiplo di $10$, perché da $h$ a $h-1$ diminuisce di 1 la cifra delle unità, mentre tutte le altre cifre restano invariate; ma $h$ non può essere un multiplo di $10$, perché altrimenti $10^{k+1} \mid n + 1$, mentre avevamo detto che $k$ era il più grande intero positivo tale che $10^k \mid n+1$. Quindi la formula risulta vera sempre.
Chiamo $a_1, a_2, ... a_{39}$ la sequenza dei 39 interi positivi e $k_1, k_2, ... k_{39}$ una sequenza di numeri naturali tali che $k_i$ è il più grande numero naturale tale che $10^{k_i} \mid a_i \forall 1 \leq i \leq 39$. Pongo $m=S(a_1-1)$.
Dimostro che $S(a_i)=m+i-9 \displaystyle\sum_{j=1}^i k_j$
È vero per $i=1$, suppongo vero per $i$ e dimostro per $i+1$:
$S(a_{i+1})=m+i+1-9 \displaystyle\sum_{j=1}^{i+1} k_j$
$S(a_{i+1})=m+i+1-9k_{i+1}-9 \displaystyle\sum_{j=1}^i k_j$
$S(a_{i+1})=S(a_i)-9k_{i+1}+1$ Che è vero per quanto dimostrato in precedenza.
Dato che la sequenza $a_1, a_2, ... a_{39}$ è composta da numeri interi consecutivi, uno (e soltanto uno) tra i primi 10 elementi sarà multiplo di 10. Suppongo che questo sia $a_c$ $(1 \leq c \leq 10)$. Gli unici multipli di 10 tra i 39 interi positivi della sequenza saranno quindi $a_c, a_{c+10}, a_{c+20}, a_{c+30}$ (quest'ultimo solo se $c \neq 10$). Di conseguenza, gli unici elementi della sequenza $k_1, k_2, ... k_{39}$ diversi da 0 saranno $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ (quest'ultimo sempre nel caso in cui $c \neq 10$).
Quindi $S(a_i)$ risulta uguale a:
$m+i$ se $1 \leq i < c$ $(c \neq 1)$
$m+i-9k_c$ se $c \leq i < c+10$
$m+i-9(k_c+k_{c+10})$ se $c+10 \leq i < c+20$
$m+i-9(k_c+k_{c+10}+k_{c+20})$ se $c+20 \leq i < c+30$
$m+i-9(k_c+k_{c+10}+k_{c+20}+k_{c+30})$ se $i \geq c+30$ $(c \neq 10)$
Inoltre, soltanto uno tra $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ può essere maggiore di 1:
Pongo $k_x > 1$ e $a_x = h10^{k_x}$ $(h \in \mathbb{N})$.
$a_{x+10y}=h10^{k_x}+10y=10(h10^{k-1}+y)$ $(y \in \mathbb{Z})$
Se $y$ non è un multiplo di 10, che è il nostro caso, allora $k_{x+10y}=1$. Quindi soltanto uno tra $k_c, k_{c+10}, k_{c+20}, k_{c+30}$ può essere maggiore di 1.
Analizzo ora 3 casi separatamente: $k_c=k_{c+10}=1$, $k_c \neq 1$ e $k_{c+10} \neq 1$.
Caso 1: $k_c=k_{c+10}=1$ (Uno solo oppure nessuno tra $k_{c+20}$ e $k_{c+30}$ sarà diverso da 1)
Esamino solo i casi in cui $c \leq i < c+20$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+(i-c)+2$ se $c \leq i < c+10$
B) $m+c+(i-c)+4$ se $c+10 \leq i < c+20$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 0 e 9, estremi inclusi, avremo un elemento di $S(a_c), S(a_{c+1}), ... S(a_{c+9})$ per ogni classe di congruenza modulo 11 $(m+c+2), (m+c+3), ... (m+c+11)$, ovvero tutte tranne la classe $(m+c+1)$. A questa classe appartiene però $S(a_{c+19})$, del caso B). Quindi, indipendentemente dai valori di $m$ e di $c$, almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
Caso 2: $k_c \neq 1$ (di conseguenza $k_{c+10}, k_{c+20}, k_{c+30}$ sono tutti uguali a 1)
Esamino solo i casi in cui $c \leq i < c+20$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+2k_c+(i-c)$ se $c \leq i < c+10$
B) $m+c+2k_c+(i-c)+2$ se $c+10 \leq i < c+20$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 0 e 9, estremi inclusi, avremo un elemento di $S(a_c), S(a_{c+1}), ... S(a_{c+9})$ per ogni classi di congruenza modulo 11 $(m+c+2k_c+2), (m+c+2k_c+3),... (m+c+2k_c+11)$, ovvero tutte tranne la classe $(m+c+2k_c+1)$. A questa classe appartiene però $S(a_{c+19})$, del caso B). Quindi, indipendentemente dai valori di $m$, $c$, e di $k_c$ almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
Caso 3: $k_{c+10} \neq 1$ (di conseguenza $k_c, k_{c+20}, k_{c+30}$ sono tutti uguali a 1)
Esamino solo i casi in cui $c+10 \leq i < c+30$. $S(a_i)$ è congruente modulo 11 a:
A) $m+c+2k_{c+10}+(i-c)+2$ se $c+10 \leq i < c+20$
B) $m+c+2k_{c+10}+(i-c)+4$ se $c+20 \leq i < c+30$
Nel caso A), dato che $(i-c)$ assume tutti i valori compresi tra 10 e 19, estremi esclusi, avremo un elemento di $S(a_{c+10}), S(a_{c+11})...S(a_{c+19})$ per ogni classe di congruenza modulo 11$(m+c+2k_{c+10}+1), (m+c+2k_{c+10}+2), ... (m+c+2k_{c+10}+10)$, ovvero tutte tranne la classe $(m+c+2k_{c+10})$. A questa classe appartiene però $S(a_{c+29})$, del caso B). Quindi, indipendentemente dai valori di $m$, $c$ e di $k_{c+10}$, almeno uno tra $S(a_1), S(a_2), ... S(a_{39})$ sarà multiplo di 11.
