6 - O problema dos colegas de quarto

6 - O problema dos colegas de

quarto

Nossas discussões sobre o problema do emparelhamento começaram por sua forma mais simplificada, o problema do casamento, em que se combinava cada homem a uma mulher (ou vice-versa), segundo as preferências de cada um. Depois, contemplamos sua forma generalizada no problema das admissões em universidades, porque, ao invés de combinar dois elementos (homens e mulheres), esta extensão permitia a combinação de um elemento de um grupo com vários de outro grupo, uma vez que cada universidade busca admitir uma quota de estudantes.

Nosso próximo passo é analisar o problema dos colegas de quarto, mais complexo devido ao fato de que não são grupos distintos que se combinam, mas cada pessoa ordena todas as outras segundo uma ordem de preferência, de forma que qualquer uma pode vir a ser colega de quarto.

Definição: Semelhantemente ao problema do casamento, diz-se que um emparelhamento é instável se houver duas pessoas que não estão pareadas entre si, mas que se preferem ao invés de seus atuais pares, de modo a formarem um par de bloqueio. Caso contrário, o emparelhamento é estável.

Exercício

1) No problema de colegas de quarto, nem toda situação admite uma solução estável; mostre que é o caso das pessoas rotuladas como ■, 1, 2,..., M, sendo M ímpar, com listas de preferência satisfazendo estas condições: ■ tem uma lista qualquer; todos os demais listam ■ em último lugar; cada n entre 1 e M – 1 prefere n + 1 em primeiro lugar; M prefere 1 em primeiro. (Note o caráter cíclico das primeiras preferências.)