Uma pequena faculdade oferece 250 classes diferentes. Duas classes não podem se encontrar ao mesmo tempo na mesma sala, é claro. Existem doze horários diferentes em que as classes podem ocorrer. Qual o número mínimo de salas de aula necessárias para acomodar todas as classes?
*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.)

Passo 1

Temos 250 turmas e 12 horários distintos; cada sala pode comportar, em cada horário, no máximo uma turma. Logo, se usarmos R salas, o número total de “vagas–horário” é
12R

Passo 2

Para acomodar todas as 250 turmas precisamos de
12R >= 250
logo
R >= 25012approx20,83
Como R é inteiro, tomamos o teto:
R = llceiltfrac25012rrceil = 21

Passo 3

Queremos provar que todo número racional tfracmn tem expansão decimal que ou termina ou se repete, usando o princípio do compartimento (pombal) aplicado ao algoritmo tradicional de divisão.

Passo 4

No algoritmo de divisão para gerar dígitos decimais de tfracmn, em cada etapa tomamos o resto rk (inicialmente r0=m) e calculamos
10,rk = qk+1,n + rk+1,
com 0<= rk+1<n. Os possíveis restos são 0,1,2,dots,n-1, ou seja, n valores.

Passo 5

Se em algum passo rk+1=0, a divisão termina e a expansão decimal é finita. Se nunca aparece resto zero, temos sempre restos em 1,2,dots,n-1, isto é, n-1 valores possíveis. Pelo princípio do pombal, ao gerar n restos consecutivos sem atingir zero, dois deles devem se repetir. A partir desse primeiro índice repetido, os dígitos gerados voltam a se repetir, formando o período.

Passo 6

Como só há n-1 restos não nulos, o comprimento do bloco repetido é, no máximo, n-1.

Resposta

Todo racional tfracmn tem expansão decimal finita ou periódica, e o número de dígitos do período é, no máximo, n-1.

Exercícios de Livros Relacionados