Os círculos da figura abaixo foram preenchidos com os números de 1 a 7, de modo que todas as flechas apontam de um número menor para um maior. Neste caso, dizemos que a figura foi bem preenchida.
(a) Complete a figura abaixo com os números de 1 a 9 de modo que ela fique bem preenchida.
(b) De quantas maneiras a figura ao lado pode ser bem preenchida com os números de 1 a 5?
(c) De quantas maneiras a figura ao lado pode ser bem preenchida com os números de 1 a 7?
Reportar erro na questãoResolução comentada
Resolução comentada
a) Em uma figura bem preenchida, o círculo do topo recebe setas de todos os outros, então ele é o maior número: 9.
O círculo ligado ao 2 por uma seta tem de ser menor que 2, então é o 1.
O círculo vazio da direita (chame de C) recebe setas do 7 e de outro círculo. Ele é maior que 7 e menor que 9, então C=8.
Já usamos 9,8,7,5,2,1. Sobram 3,4,6.
Na cadeia abaixo do 5, os dois círculos vazios satisfazem \text{(baixo)}<\text{(meio)}<5. Só 3 e 4 cabem, então o de baixo é 3 e o do meio é 4.
O 6 vai para o círculo que falta, ao lado do 7, e 6<8 confere.
Preenchimento: topo 9; nível seguinte 5, 2, 8; embaixo, abaixo do 5 o 4 e depois o 3, abaixo do 2 o 1, e abaixo do 8 os números 7 e 6.
Resposta: topo 9, depois 5, 4, 3 na cadeia da esquerda, 2 e 1 no ramo do meio, 8 com 7 e 6 abaixo dele.
b) O círculo do topo é o maior de todos, então vale 5.
Sobram 1,2,3,4 para os outros quatro círculos: uma folha à esquerda, o círculo da direita (chame de R) e as duas folhas abaixo de R.
Escolha o número da folha da esquerda, que não tem restrição: 4 possibilidades.
Dos 3 números restantes, R deve ser o maior, pois recebe setas das duas folhas abaixo dele: 1 possibilidade.
Os outros dois números ocupam as duas folhas em qualquer ordem: 2 possibilidades.
Total: 4\cdot 1\cdot 2=8.
Resposta: 8 maneiras.
c) O topo vale 7.
Sobram 1,\dots,6. O círculo da esquerda do topo é uma folha livre. O restante forma um ramo de 5 círculos, cuja raiz b é maior que todos os outros do ramo.
Escolha o número da folha livre: 6 possibilidades.
Com os 5 números restantes, b é o maior: 1 possibilidade.
Dos 4 números que sobram, escolha o da folha ao lado de d (o filho de b que tem duas folhas abaixo): 4 possibilidades.
Dos 3 restantes, d é o maior: 1 possibilidade.
Os 2 últimos ocupam as duas folhas de baixo em qualquer ordem: 2 possibilidades.
