Agora que eu fui reparar, mas não são fatoriais... são quadrados!!!
Se temos N homens e N mulheres existem N² possíveis pares, não N!.
De qualquer modo, acho q o raciocínio vale...
Ignorem a mensagem anterior...
+-------------------------------------------------------------+
se N = 1 temos um caso trivial, estável
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
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <[EMAIL PROTECTED]>
=========================================================================
