Exercício 38: No início de uma festa há 6 rapazes desacompanhados e 10 moças desacompanhados. No fim, o número de casais rapaz-moça pode ser?
Passo 1
Resumindo, inicialmente temos
rapazes sem companhia e
moças sem companhia, e no fim queremos formar casais “rapaz-moça” sem repetir ninguém. O conteúdo aqui é combinatória básica de acoplamento (em teoria de grafos, é o tamanho de um emparelhamento num grafo bipartido completo
).
Passo 2
Para achar o máximo de casais, note que cada casal consome um rapaz e uma moça. Como só há
rapazes, não podemos ultrapassar
casais. Logo,
Passo 3
Para achar o mínimo, basta permitir que ninguém forme casal. Assim,
Passo 4
Em emparelhamentos de um bipartido completo, qualquer valor inteiro entre o mínimo e o máximo é atingível. Portanto, o número de casais pode ser qualquer
tal que
isto é,
.
Resposta
O número de casais pode ser
.