|
se N = 1 temos um caso trivial
se N = 2
H = { A, C }
M = { B, D }
temos 2! possibilidades
1) (A, B) é estável e (C, D) deve ser
também
2) (A, B) não é estável, nesse caso, é só trocar
com o outro par e obtemos dois casamentos estáveis
suponha que para todo N inteiro positivo, 1 <=
N < k seja possível obter uma combinação somente com casamentos
estáveis com N casais.
Selecionamos um primeiro casal (k! possibilidades
para esse primeiro).
pela hipótese de indução, é sempre possível obter
uma combinação somente com casamentos estáveis dentro do conjunto de homens e
mulheres que sobrou (k-1) homens e (k-1) mulheres.
Devo então provar que para pelo menos um casal (A,
B) dentre k! possibilidades temos que (A, B) é estável em relação a todos
do conjunto formado pela hip. de indução (chamarei-o de S).
Se o casal selecionado não é estável com todos os elementos de S, podemos pegar o casal selecionado e um casal dentro de S tal que ambos são instáveis um em relação do outro. A partir daí formamos um terceiro casal, mais estável que os dois, este novo casal está obviamente dentro das k! possibilidades iniciais, sendo assim podemos a partir desse outro casal obter sempre um outro casal mais estável e assim sucessivamente, como as possibilidades são finitas, uma hora obtemos um casal que é o mais estável de todos!* Pegando esse casal mais estável de todos associamos a ele um conjunto S,
que existe pela hipótese de indução, não existe nenhum outro casal dentro de S
que desestabilize o primeiro (já que todos os casais dentro de S são alguns das
k! possibilidades iniciais e o primeiro casal é o mais estável dentro de todos
eles).
Então o conjunto {primeiro casal} U S é todo
estável e contém k pares, logo provamos, pelo PIF que sempre existe a
possibilidade de obter uma combinação com todos os casais estáveis.
* futuramente eu pretendo formalizar a seguinte
idéia:
Seja V o conjunto de todas as k! possibilidades de
casais.
Existe um elemento de V que é estável dentro de
V.
na verdade é exatamente essa a demonstração formal
que falta para que o problema tenha sido resolvido.
se alguém conseguir, por favor, coloque
aqui.
[ ]'s
|