[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.
>
>