Gênio Indomável - Segundo Problema de Matemática

O filme Gênio Indomável (Good Will Hunting) conta a história de um gênio secreto da matemática interpretado por Matt Damon. A trama gira em torno do personagem principal, Will, que resolve um problema matemático extremamente difícil que intrigou os professores do MIT por dois anos. O problema não só era, na verdade, bastante simples, como o personagem do filme ainda assim errou a solução.

O problema, conforme escrito no quadro, era: "Desenhe todas as árvores homeomorficamente irredutíveis de tamanho n=10."

Deixe-me tentar explicar isso em termos simples. O problema pede todos os diagramas possíveis compostos por dez pontos, conectados por linhas, onde nenhuma linha pode ter exatamente duas linhas partindo dela (caso contrário, seria redutível) e não pode haver laços fechados (caso contrário, não seria uma árvore). "Homeomorficamente irredutível" significa que não importa o ângulo das linhas, apenas quantas linhas partem de cada ponto.

No filme, Will produz apenas oito das dez árvores. Deixe-me mostrar uma maneira de chegar à resposta de forma sistemática. Vou pensar nas árvores como árvores genealógicas, começando pelo patriarca da família.

Solução 1 – Nove filhos. Esta é a única solução com apenas duas gerações.

Solução 2 – Três filhos com netos divididos em 6/0/0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Observe que não pode haver exatamente dois filhos, porque então você poderia ir de um filho para o pai e depois para o outro filho, o que seria redutível.

Solução 3 – Três filhos com netos divididos em 4/2/0

Note que ninguém pode ter apenas um filho, caso contrário a árvore seria redutível.

Solução 4 – Três filhos com netos divididos 3/3/0

Solução 5 – Três filhos com netos divididos em 2/2/2

Solução 6 – Quatro filhos com netos divididos em 5/0/0/0

Solução 7 – Quatro filhos com netos divididos em 3/2/0/0

<

Lembre-se, as crianças não podem ter apenas um filho, senão a árvore seria redutível.

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Solução 8 – Cinco filhos com netos divididos em 4/0/0/0

Você poderia considerar cinco filhos com netos divididos em 2/2/0/0, mas isso seria homeomorficamente redutível à mesma árvore que a solução 3 (levei um tempo para perceber isso).

Solução 9 – Três netos, com a proporção de netos 2/0/0. Um dos dois netos tem quatro bisnetos.

Solução 10 -- Três netos, com a divisão entre eles sendo 2/2/0. Um dos dois netos tem dois bisnetos.

Percebo que estou usando uma lógica um tanto rebuscada para chegar às dez soluções. No entanto, pelo menos cheguei às dez, ao contrário do Will no filme.

Na próxima semana, pretendo abordar outro filme em que a cena matemática foi bem feita: Meninas Malvadas.

Links relacionados:

O problema em Gênio Indomável – vídeo do YouTube por Numberfile

Solução emphp#s220" style="color:#a5341f;" target="_blank">MathProblems.info