*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 m / n tem uma expansão decimal que se repete, encontre um limite superior (em termos do número inteiro n ) no número de dígitos na parte que se repete. (Dica: No problema de divisão
m lcmn
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 l bilhetes perdedores em sequência. Encontre l.

Passo 1

O enunciado traz duas aplicações do princípio do compartimento no pombal (princípio das gavetas):
  1. Mostrar que toda fração tfracmn em base decimal termina ou entra em repetição, e no caso de repetição, achar um limite superior, em função de n, para o número de dígitos do período.
  2. Num sorteio de 100 bilhetes, dos quais 12 são premiados, usar o princípio generalizado para garantir que exista uma sequência de l bilhetes perdedores em fila; precisamos determinar l.

Passo 2

Para a expansão decimal de tfracmn usamos o algoritmo da divisão: a cada etapa, multiplicamos o resto rk-1 por 10 e dividimos por n. O novo resto é
rk = 10,rk-1 bmod n
Os restos possíveis são ;0,1,2,dots,n-1, ou seja, há apenas n valores distintos. Pelo princípio do pombal, em n+1 etapas dois desses restos se repetirão.

Passo 3

Se em algum passo rk = 0, a divisão termina e a expansão decimal termina (caso finito). Caso contrário, como há n restos possíveis e estamos gerando n+1 deles, existe um par de índices i<j com
ri = rj neq 0
Isso faz com que os dígitos gerados entre as posições i+1 e j se repitam ciclicamente, provando que a expansão decimal é periódica a partir de i+1.

Passo 4

Como só podem surgir valores de resto entre 1 e n-1, há no máximo n-1 restos não-zero distintos. Logo, em no máximo n etapas o primeiro resto não-zero se repetirá, o que implica que o período em dígitos tem comprimento no máximo
n-1

Passo 5

Agora o problema dos bilhetes: há 100 posições e 12 bilhetes premiados. Esses 12 vencedores dividem a sequência em 12+1=13 “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 é 100-12=88. Distribuindo 88 perdedores em 13 intervalos, pelo princípio generalizado existe pelo menos um intervalo com tamanho
llceil tfrac8813rrceil = llceil 6,769dotsrrceil = 7
Esse valor é o menor l que garantimos.

Resposta

  1. Em tfracmn, a parte periódica tem no máximo n-1 dígitos.
  2. l = 7.

Exercícios de Livros Relacionados