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 6 rapazes sem companhia e 10 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 K_{6,10}).

Passo 2

Para achar o máximo de casais, note que cada casal consome um rapaz e uma moça. Como só há 6 rapazes, não podemos ultrapassar 6 casais. Logo,
\max(\text{nº de casais}) = \min(6,10) = 6.º

Passo 3

Para achar o mínimo, basta permitir que ninguém forme casal. Assim,
\min(\text{nº de casais}) = 0.º

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 k tal que
0 \le k \le 6,
isto é, k\in\{0,1,2,3,4,5,6\}.

Resposta

O número de casais pode ser \{0,1,2,3,4,5,6\}.

Exercícios relacionados