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
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.)
*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
Passo 1
Temos
turmas e
horários distintos; cada sala pode comportar, em cada horário, no máximo uma turma. Logo, se usarmos
salas, o número total de “vagas–horário” é
Passo 2
Para acomodar todas as
turmas precisamos de
logo
Como
é inteiro, tomamos o teto:
Passo 3
Queremos provar que todo número racional
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
, em cada etapa tomamos o resto
(inicialmente
) e calculamos
com
. Os possíveis restos são
, ou seja,
valores.
Passo 5
Se em algum passo
, a divisão termina e a expansão decimal é finita. Se nunca aparece resto zero, temos sempre restos em
, isto é,
valores possíveis. Pelo princípio do pombal, ao gerar
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á
restos não nulos, o comprimento do bloco repetido é, no máximo,
.
Resposta
Todo racional
tem expansão decimal finita ou periódica, e o número de dígitos do período é, no máximo,
.