Math Problem Solver

Considere uma sala retangular, cujo comprimento é um valor inteiro E. Deseja-se

instalar divisórias removíveis que permitam obter salas menores de modo a cumprir a seguinte

condição: para cada inteiro X de 1 até E, uma sala de comprimento X pode ser construída de

uma ÚNICA forma, possivelmente juntando-se salas adjacentes. Essas divisórias são sempre

perpendiculares ao comprimento da sala, como ilustrado na Figura 6 a seguir.

Figura 6: Representação das divisórias utilizadas na sala.

A extremidade esquerda da sala é uma divisória denotada como 0 e a extremidade direita é uma

divisória denotada como E.

Note que se E = 3 a condição pode ser satisfeita colocando-se divisórias nas posições 0, 1, 3,

vide a figura 7, pois poderemos formar uma sala de comprimento 1 (ilustrada em azul, à es-

querda, como Sala 1), uma sala de comprimento 2 (ilustrada em laranja, à direita, como Sala 2),

e uma sala de comprimento 3 (correspondente à junção das salas 1 e 2).Sala 1 Sala 2

Figura 7: Divisórias cumprindo a condição enunciada para sala de extensão E = 3.

Note que se E = 7 a colocação de divisórias nas posições 0, 1, 3, 7, como indicado na Figura 8,

não satisfaz a condição enunciada. Isso ocorre pois mesmo sendo possível formar salas meno-

res de comprimentos 1 (Sala 1, em azul na figura 8), 2 (Sala 2, em laranja), 3 (correspondente

11

41ª Olimpíada de Matemática da Unicamp

Instituto de Matemática, Estatística e Computação Científica

Universidade Estadual de Campinas

à junção das salas 1 e 2), 4 (Sala 4, em roxo), 6 (correspondente à junção das salas 2 e 4) e 7

(correspondente à sala inicial), não é possível formar uma sala de comprimento 5.

Ainda, se acrescentamos uma divisória na posição 5, como mostrado na Figura 9, formamos sa-

las de quaisquer comprimentos, mas há mais de uma maneira de formar salas com comprimento

2 (Sala 2(a) representada em laranja, Sala 2(b) em amarelo e Sala 2(c) em rosa).Sala 1 Sala 2 Sala 4

Figura 8: Divisórias que não formam todos os comprimentos para E = 7.Sala 1 Sala 2 (a) Sala 2 (c)Sala 2 (b)

Figura 9: Divisórias formando qualquer comprimento para E = 7, mas sem unicidade.

Responda ao que se pede.

Para os itens de (a) a (d) considere uma sala de comprimento E satisfazendo a condição acima.

Observação: Os itens são independentes.

(a) Encontre todas as possibilidades de colocação de divisórias para todos os valores de E de

1 a 6. Não é necessário justificar este item.

(b) Considere E ⩾ 3. Mostre que as salas de comprimento 1 e 2 estão em extremidades

opostas da sala, ou seja, uma das salas tem uma divisória na extremidade 0 enquanto a

outra tem uma divisória em E.

12

41ª Olimpíada de Matemática da Unicamp

Instituto de Matemática, Estatística e Computação Científica

Universidade Estadual de Campinas

(c) Considere E ⩾ 6. Mostre que as salas de comprimento 1 e 3 estão uma ao lado da outra,

ou seja, elas compartilham uma divisória. (Dica: Analise como uma sala de tamanho E − 4

pode ser formada.)

(d) Mostre que se forem colocadas n divisórias (incluindo as extremidades 0 e E), sendo n um

número natural, em uma sala de comprimento E satisfazendo a condição, então deve-se

ter

E = n(n − 1)

2 .

(e) Use o item (d) para mostrar que não é possível que uma sala de comprimento E ⩾ 10

satisfaça a condição. (Dica: Analise inicialmente o caso E = 10 e posteriormente E ⩾ 11.

Lembre que a posição de algumas salas já foi definida nos itens (b) e (c).)

(f) Conclua que as únicas possibilidades de colocação de divisórias são as realizadas nas

posições encontradas no item (a).