Siga-nos

Perfil

Expresso

Solução para o problema "Turma complicada"

  • 333

Na passada sexta-feira deixámos AQUI um problema. Hoje apresentamos-lhe a solução. 

Numa turma de 37 alunos, sabemos que cada aluno tem no máximo três inimigos entre os colegas de turma. Pretendemos dividir a turma em dois grupos, de modo a que cada aluno tenha no máximo um inimigo dentro do seu grupo. 

Solução

Vamos então criar um algoritmo que nos aproxima sucessivamente da solução pretendida. Começamos por dividir a turma em dois grupos, A e B, de forma arbitrária. Iremos agora alterar a configuração inicial, até encontrarmos uma divisão admissível. Para isso, procuramos um aluno que tenha dois ou mais inimigos no seu grupo e mudamo-lo para o outro grupo. Em seguida, repetimos a mesma receita, procuramos outro aluno com dois ou mais inimigos no seu grupo e mudamo-lo de grupo. E assim sucessivamente, até não haver mais alunos nestas condições.

 Aparentemente, já está. Este procedimento parece levar a uma divisão onde não há nenhum aluno que tenha mais do que um inimigo dentro do seu grupo. Mas cuidado, observe que quando muda um aluno de grupo, isso pode obrigar a alterar a posição de outro aluno que antes estava bem nesse grupo. Será que não podemos cair numa sequência infinita de trocas sem nunca chegarmos a uma solução satisfatória?

 Para avaliar a qualidade da divisão,  consideramos a soma do número de inimizades  dentro do grupo A, com as inimizades dentro do grupo B. Facilmente se verifica que a soma total das inimizades dentro dos grupos baixa, sempre que se troca um aluno que tenha duas ou três inimizades dentro do grupo. Esta soma é sempre um número inteiro positivo e depois da troca passa a ser um valor estritamente menor.

Porque é que o algoritmo acima tem de parar? Porque a soma do número de inimizades dos dois grupos não pode baixar para sempre. O seu valor mínimo é zero. Logo, a dada altura o processo terá de parar. E isto significa que em cada um dos grupos ninguém tem dois ou mais inimigos. 

Problema resolvido e boa visita!