[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re:[obm-l] Principio das Gavetas

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: owner-obm-l@mat.puc-rio.br
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"
> >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:owner-obm-l@mat.puc-rio.br
> >
> >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.
>
>