Siga-nos

Perfil

Expresso

Turma complicada

  • 333

O puzzle de hoje é um problema típico de olimpíadas de matemática, onde é suposto criar um algoritmo. Um algoritmo consiste num conjunto de regras que devem ser seguidas para atingir um determinado fim. Um pouco como seguir uma receita culinária. Toda a gente se recorda, por exemplo, do algoritmo da soma, da escola primária.

Inicialmente, temos uma turma com 37 alunos. O número de alunos não é relevante mas certamente agradaria à troika. Infelizmente, nem todos os alunos desta turma se dão bem entre si. Embora se saiba também que cada aluno tem no máximo três inimigos, entre os colegas de turma. Naturalmente, a relação de inimizade é sempre recíproca, se o Pedro não gosta da Sara, então a Sara também não simpatiza com o Pedro.

A directora de turma pretende levar estes alunos numa visita de estudo. Ainda não sabe onde, mas garante que não leva ninguém ao Museu dos Coches.

Com o objectivo de minimizar o número de potenciais conflitos durante a visita, decidiu-se dividir a turma em dois grupos. Fazendo cada um dos grupos a visita separadamente.

O desafio desta semana consiste em mostrar que é sempre possível fazer a divisão da turma em dois grupos, de modo a que cada aluno tenha no máximo um inimigo dentro do seu grupo. Não é importante o tamanho de cada um dos grupos.

Deixamos uma sugestão para o início do algoritmo: começar por dividir os  alunos em dois grupos, de forma arbitrária.