Re: Fw: [obm-l] Teorema de Donald ; Olimpiada Iberoamericana de Matematica 2002

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Nooossa,que e isso?Nao entendi muito bem porque to num sono...Mas a minha ideia era como construir esse conjuntao.De todo jeito te mais!

 "Domingos Jr." wrote:

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 é
=========================================================================

---

Yahoo! GeoCities
Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e acessórios.