Re: [obm-l] russos

["Ralph Teixeira" <ralph@xxxxxx>]

>1)Prove que em qualquer sequencia de 39 numeros naturais consecutivos
>existe ao menos  um numero cuja a soma dos algarismos e divisivel por
>11.
    Hmmm...que tal assim:

Caso (1) Se nao houver "troca de centena" entre esses 39 numeros

Neste caso, a observacao chave eh a da Iolanda: a soma dos algarismos de n
na aumenta de 1 a cada vez que o numero aumenta de 1; exceto quando hah
"troca de dezena", quando entao a soma diminui em 8 (-9 nas unidades, +1 nas
dezenas). Assim, a sequencia dos restos das somas dos algarismos de n na
divisao por 11 serah um subconjunto da seguinte sequencia ciclica:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 0
3 4 5 6 7 8 9 10 0 1
4 5 6 7 8 9 10 0 1 2
...
10 0 1 2 3 4 5 6 7 8

(a partir daqui a sequencia repete -- note que eu troco de linha ao trocar
dezenas, assim cada coluna corresponde a uma possibilidade de digito final
para n). Note que existem 28 restos entre os dois primeiros zeros; entre os
outros pares consecutivos de zeros hah apenas 8 restos nao nulos. Como a
nossa sequencia tem 39 desta sequencia de restos, pelo menos um 0 aparece.

Caso (2) Hah uma troca de centena na sequencia (possivelmente uma troca de
ordem maior ao mesmo tempo, nao me interessa)
Este eh o ultimo caso -- 39 numeros consecutivos nao podem trocar as
centenas DUAS vezes...
 Neste caso, os 39 numeros sao divididos em duas subsequencias, uma antes da
"grande troca" e outra depois. A sequencia de restos que vem antes da GRANDE
TROCA serah uma subsequencia da tabela ciclica acima, soh que agora o ultimo
elemento TEM DE ESTAR NA ULTIMA COLUNA (que corresponde aos numeros que
terminam por 9) -- chamemos isso
de subsequencia do tipo (i). Analogamente, a sequencia de restos que comeca
com o resto do numero 100k, TEM DE COMECAR NA PRIMEIRA COLUNA -- tipo (ii).

Nao eh dificil ver que a maior sequencia do tipo (i) sem zeros eh a que
comeca no primeiro 1 e vai ateh o 10 da segunda linha (com 19 elementos); a
maior possivel do tipo (ii) sem zeros COMECA no 1 da segunda linha e termina
no 10 da terceira, com mais 19 elementos. Como temos 39 elementos > 19+19,
concluimos que ao menos um numero da lista tem soma dos algarismos divisivel
por 11.

---///---

Alias, com essa tabela em mãos, não é difícil encontrar uma sequencia com 38
elementos sem somas de algarismos divisiveis por 11. Teremos de usar algo da
forma 100k-19, 100k-18,....,100k-1, 100k, 100k+1,...,100k+18 onde a soma dos
algarismos de 100k-1 deixa resto 10 na divisao por 11 e a soma dos
algarismos de 100k deixa resto 1 na divisao por 11.

Se 100k termina por m zeros, entao sao m noves que somem de 100k-1 para
100k, entao a soma dos algarismos diminui em 9m-1 (como a Iolanda jah tinha
observado). Para conseguir que o resto pule de 10 para 1, precisamos de que
9m-1=9 modulo 11, isto eh, m seja da forma 11a+6 -- temos de terminar com
11a+6 zeros em 100k. Assim, a sequencia de 38 elementos sem soma dos
algarismos divisivel por 11 comecando pelo menor numero eh:

999981 999982 999983 ... 999999 1000000 1000001 ... 1000018

Legal?

Abraco,
     Ralph

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================