11 | s(n) con n in {m-19,...,m+19}

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

11 | s(n) con n in {m-19,...,m+19}

Messaggio da jordan » 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.
The only goal of science is the honor of the human spirit.

Porky
Messaggi: 9
Iscritto il: 24 mar 2011, 23:23
Località: Belluno
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da Porky » 07 apr 2012, 14:16

È la prima dimostrazione che posto su questo forum, quindi accetto qualunque critica costruttiva.
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.
È un po' lunghetta (ammesso che sia giusta), quindi mi è sorto un dubbio: se mi trovo con una soluzione del genere a Cesenatico (cioè una che ci sta forse in 3 facciate, ma sarebbe meglio 4), posso "allegare" qualche foglio a quelli che mi consegnano, se lo spazio non mi basta?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da jordan » 07 apr 2012, 16:02

Personalmente impiegherei quei 40 minuti disponibili per ogni problema solo a copiarla quella soluzione :roll:
Comunque hai dimostrato più del necessario, ma mi pare le idee ci sono tutte..scrivo sotto la mia:

Sia $A$ l'insieme fissato di $39$ interi positivi consecutivi. Il più piccolo intero positivo tale che $11 \mid s(n)$ e' $n=29$, per cui assumiamo $\min\{A\}\ge 30$. Definito $S(n):=\{10n,10n+1,...,10n+9\}$ per ogni intero $n>0$, deve esistere un intero $n_0>0$ tale che $\left(S(n_0) \cup S(n_0+1) \cup S(n_0+2)\right) \subseteq A$ (infatti se non esistesse tale $n_0$ sarebbe valida $|A|\le 2\cdot 10+ 2\cdot 9 = 38$ ). Dato che per ogni $n$ l'insieme $S(n)$ contiene $10$ distinti residui modulo $11$, allora, se la tesi fosse falsa, sarebbe valida: $s(10n_0) \equiv s(10(n_0+1)) \equiv s(10(n_0+2)) \equiv 1 \pmod{11}$, cioè $s(n_0) \equiv s(n_0+1) \equiv s(n_0+2)$ modulo 11, che e' chiaramente impossibile. []
The only goal of science is the honor of the human spirit.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da dario2994 » 09 apr 2012, 11:20

Bonus con le tette al vento: Trovare tutti gli $ n $ tali che in $ \{n,n+1,\dots n+37\} $ non ci sono numeri con somma delle cifre divisibile per $11$.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da jordan » 09 apr 2012, 15:22

dario2994 ha scritto:Bonus con le tette al vento: Trovare tutti gli $ n $ tali che in $ \{n,n+1,\dots n+37\} $ non ci sono numeri con somma delle cifre divisibile per $11$.
Con la notazione di sopra, condizione necessaria e sufficiente per il tuo bonus è $s(n_0-1)+1\equiv s(n_0) \equiv s(n_0+1) \equiv s(n_0+2)-1 \equiv 1 \pmod{11}$; non ci vuole molto a concludere che il più piccolo insieme di questo tipo e' $\{999981, 999982,...,1000018\}$..
The only goal of science is the honor of the human spirit.

Porky
Messaggi: 9
Iscritto il: 24 mar 2011, 23:23
Località: Belluno
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da Porky » 09 apr 2012, 18:28

Parto dall'ultimo caso della mia dimostrazione e uso la stessa notazione (mi dispiace per chi non ha voglia di leggerla tutta).
È evidente che $m = S(n-1) \equiv 0 (mod 11)$.
L'unico caso in cui si "perde" una classe di congruenza è quello in cui $c=10$ (nel terzo caso della mia dimostrazione); manca la classe di congruenza $(m+c+2k_{c+10})$, cioè $-1+2k_{20}$. Manca la classe congruente a 0 modulo 11 se
$-1+2k_{20} \equiv 0 (mod 11)$
$k_{20} \equiv 6 (mod 11)$

Quindi vanno bene tutti gli insiemi tali che la più grande potenza di 10 che divide $n+19$ "abbia un numero di zeri" congruente a 6 modulo 11.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da jordan » 09 apr 2012, 21:04

Porky ha scritto: Quindi vanno bene tutti gli insiemi tali che la più grande potenza di 10 che divide $n+19$ "abbia un numero di zeri" congruente a 6 modulo 11.
Dici? Prova n=811999981
The only goal of science is the honor of the human spirit.

Porky
Messaggi: 9
Iscritto il: 24 mar 2011, 23:23
Località: Belluno
Contatta:

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da Porky » 09 apr 2012, 21:14

jordan ha scritto:
Porky ha scritto: Quindi vanno bene tutti gli insiemi tali che la più grande potenza di 10 che divide $n+19$ "abbia un numero di zeri" congruente a 6 modulo 11.
Dici? Prova n=811999981
Giusto... deve anche essere vero che $S(n-1) \equiv 0 (mod 11)$

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: 11 | s(n) con n in {m-19,...,m+19}

Messaggio da Karl Zsigmondy » 10 apr 2012, 09:22

dario2994 ha scritto:Bonus con le tette al vento: Trovare tutti gli $ n $ tali che in $ \{n,n+1,\dots n+37\} $ non ci sono numeri con somma delle cifre divisibile per $11$.
E' un bonus parecchio gucciniano...
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Rispondi