*23. Use o princípio do compartimento no pombal para explicar por que todo número racional tem uma expansão decimal que ou termina ou se repete. No caso em que um número racional
tem uma expansão decimal que se repete, encontre um limite superior (em termos do número inteiro
) no número de dígitos na parte que se repete. (Dica: No problema de divisão
considere os possíveis restos em cada passo do algoritmo de divisão.)
24. Suponha que 100 bilhetes de loteria são distribuídos em sequência aos 100 primeiros convidados que chegam a uma festa. Desses 100 bilhetes, somente 12 são bilhetes ganhadores. O princípio generalizado do compartimento no pombal garante que deve haver pelo menos
bilhetes perdedores em sequência. Encontre
.
24. Suponha que 100 bilhetes de loteria são distribuídos em sequência aos 100 primeiros convidados que chegam a uma festa. Desses 100 bilhetes, somente 12 são bilhetes ganhadores. O princípio generalizado do compartimento no pombal garante que deve haver pelo menos
Passo 1
O enunciado traz duas aplicações do princípio do compartimento no pombal (princípio das gavetas):
- Mostrar que toda fração
em base decimal termina ou entra em repetição, e no caso de repetição, achar um limite superior, em função de , para o número de dígitos do período. - Num sorteio de
bilhetes, dos quais são premiados, usar o princípio generalizado para garantir que exista uma sequência de bilhetes perdedores em fila; precisamos determinar .
Passo 2
Para a expansão decimal de
usamos o algoritmo da divisão: a cada etapa, multiplicamos o resto
por
e dividimos por
. O novo resto é
Os restos possíveis são
, ou seja, há apenas
valores distintos. Pelo princípio do pombal, em
etapas dois desses restos se repetirão.
Passo 3
Se em algum passo
, a divisão termina e a expansão decimal termina (caso finito). Caso contrário, como há
restos possíveis e estamos gerando
deles, existe um par de índices
com
Isso faz com que os dígitos gerados entre as posições
e
se repitam ciclicamente, provando que a expansão decimal é periódica a partir de
.
Passo 4
Como só podem surgir valores de resto entre
e
, há no máximo
restos não-zero distintos. Logo, em no máximo
etapas o primeiro resto não-zero se repetirá, o que implica que o período em dígitos tem comprimento no máximo
Passo 5
Agora o problema dos bilhetes: há
posições e
bilhetes premiados. Esses
vencedores dividem a sequência em
“intervalos” de perdedores (um antes do primeiro vencedor, um entre cada par de vencedores e um após o último).
Passo 6
O total de bilhetes perdedores é
. Distribuindo
perdedores em
intervalos, pelo princípio generalizado existe pelo menos um intervalo com tamanho
Esse valor é o menor
que garantimos.
Resposta
-
Em
, a parte periódica tem no máximo dígitos. -
.