Caramba! Errinho idiota...
A boa notícia é que, nesse caso, o raciocínio que eu usei pra construir o contra-exemplo furado fornece a demonstração:
Seja X uma sequência arbitrária de 39 naturais consecutivos.
Se o menor termo de X é <= 38, então acabou pois nesse caso 38 pertencerá a X e S(38) = 11.
Assim, suponhamos que o menor termo de X seja >= 39.
Seja N o termo de X que termina com o maior número possível de algarismos 9 (digamos k algarismos 9, com k >= 1).
Se k >= 2, então N será o único termo de X com esta propriedade.
Consideremos a sequência dos naturais de N-38 até N+38 e as respectivas somas de seus algarismos.
X será uma subsequência desta sequência, uma vez que N pertence a X e X tem 39 termos.
Pondo S(N) = S e usando o lema, achamos que:
S(N-38) = S-11
...
S(N-31) = S-4
S(N-30) = S-3
S(N-29) = S-11
...
S(N-21) = S-3
S(N-20) = S-2
S(N-19) = S-10
...
S(N-11) = S-2
S(N-10) = S-1
S(N-9) = S-9
...
S(N-1) = S-1
S(N) = S
S(N+1) = S-9k+1
...
S(N+9) = S-9k+9
S(N+10) = S-9k+10
S(N+11) = S-9k+2
...
S(N+19) = S-9k+10
S(N+20) = S-9k+11
S(N+21) = S-9k+3
...
S(N+29) = S-9k+11
S(N+30) = S-9k+12
S(N+31) = S-9k+4
...
S(N+38) = S-9k+11
Repare que S(x) mod 11 com N-29 <= x <= N-10 assume todos os 11 valores possíveis (S-11 a S-1).
Idem para S(x) mod 11 com:
N-19 <= x <= N (S-10 a S)
e
N+1 <= x <= N+20 (S-9k+1 a S-9k+11);
Vamos agora separar em casos, de acordo com t = termo inicial de X, o qual pertence, necessariamente, ao conjunto {N-38, N-37, ..., N-1, N}.
Caso 1: N-38 <= t <= N-29.
Nesse caso X engloba o intervalo de N-29 a N-10 e, portanto, possui um termo x tal que S(x) == 0 (mod 11).
Caso 2: N-28 <= t <= N-19.
Nesse caso, X engloba o intervalo de N-19 a N e, portanto, possui um termo x tal que S(x) == 0 (mod 11).
Caso 3: N-18 <= t <= N.
Nesse caso, X engloba o intervalo de N+1 a N+20 e, portanto, também possui um termo x tal que S(x) == 0 (mod 11).
Em suma, qualquer que seja t = termo inicial de X, vai existir um termo de X cuja soma dos algarismos é divisível por 11.
[]s,
Claudio.
| De: | [EMAIL PROTECTED] |
| Para: | obm-l@mat.puc-rio.br |
| Cópia: |
| Data: | Tue, 29 Mar 2005 15:50:46 -0500 |
| Assunto: | Re:[obm-l] Principio das Gavetas |
> Vc comprovou a minha solucao anterior... o seu exemplo e justamente o worse
> case scenario:
>
> 39000019 tem como soma de algarismos 22 que e divisivel por 11
>
> >From: "claudio.buffara" <[EMAIL PROTECTED]>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: "obm-l"
> >Subject: Re:[obm-l] Principio das Gavetas
> >Date: Tue, 29 Mar 2005 15:40:21 -0300
> >
> >
> >De:[EMAIL PROTECTED]
> >
> >Para:obm-l@mat.puc-rio.br
> >
> >Cópia:
> >
> >Data:Tue, 29 Mar 2005 08:44:28 -0300
> >
> >Assunto:[obm-l] Principio das Gavetas
> >
> > > Aproveitando a oportunidade, gostaria de uma sugestão no problema
> > > seguinte: "Prove que em qualquer seqüência de 39 números naturais
> > > consecutivos existe ao menos um número cuja soma dos algarismos é
> > > divisível por 11."
> > >
> > > []s,
> > >
> > > Márcio.
> > >
> >
> >A afirmativa não é verdadeira.
> >Contra-exemplo:
> >38999981, 38999982, ..., 39000019.
> >
> >Por outro lado, acho que com 40 naturais consecutivos o resultado é
> >verdadeiro.
> >
> >Minha idéia foi considerar o termo da sequência que termina com o maior
> >número possível de algarismos 9 (digamos k algarismos 9, com k >= 1).
> >Chamando este termo de N e a soma de seus algarismos de S(N), eu descobri o
> >contra-exemplo no caso em que S(N) == 10 e k == 6 (mod 11).
> >
> >O seguinte lema (fácil de provar) foi útil:
> >Se N é um número natural que termina por k algarismos 9 (k >= 0) e se S(N)
> >é a soma dos algarismos de N, então S(N+1) = S(N) - 9k + 1.
> >
> >[]s,
> >Claudio.
>
>
