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
 

----- Original Message -----
Sent: Tuesday, October 08, 2002 2:18 PM
Subject: [obm-l] Teorema de Donald ; Olimpiada Iberoamericana de Matematica 2002

O MINISTERIO DA SAUDE ADVERTE:LER E-MAILS LONGOS PODE PROVOCAR SONOLENCIA FORTE E GRAVES ALUCINAÇOES.

Bem gente,ja saiu os enunciados da Olimpiada Iberoamericana desse ano.Vamos resolve-los?Eu resolvi o segundo dia junto com a turma do Etapa.

Ah,tambem tem o problema do Donald Knuth(que o Edmilson propos numa OBM fase 3 e o Tengan corrigiu):

Imagine uma festa com N homens e N mulheres.Nessa festa cada homem  faz o seguinte procedimento:pega um papelzinho e escreve os nomes das mulheres em ordem estritamente crescente de preferencia.Cada mulher faz o mesmo com os homens.

Vamos definir casamento instavel assim:

Temos os casais (A,B) e (C,D),em que A e C sao os homens.Se A gosta mais de D do que de B,e D gosta mais de A do que de C,entao o casamento (A,B) e instavel (e o casamento (C,D) tambem)(suponha que o fogo corre solto nesta festa,ou seja se um casamento for instavel a traiçao e instantanea).

Demonstre que pode-se arranjar os casais de modo que todos os casamentos sejam estaveis.

QUEM RESOLVER GANHA UM PARABENS!!!!!!! 



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

Responder a