RE: [obm-l] Teorema de Donald

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

Pessoal
 
E se pensarmos mais ou menos assim:
 
(1) O número de diferentes combinações de casais num salão com K homens e K
mulheres será K!.
 
(2) Seja o casal (H1, Ma) (H2, Mb). Sabemos que se a dupla de casal é:
 
a-) Estável: Logo, (H1, Mb) (H2, Ma) é uma dupla Instável
b-) Instável: Logo, (H1, Mb) (H2, Ma) é uma dupla Estável.
 
Ou seja, se formos analisar todas as combinações possíveis de duplas de
casais (H1, Mx) (H2, My), sabemos que metade destas combinações são válidas
(estáveis)!
 
Minha idéia era provar por combinação que existe pelo menos uma das K!
combinações que é válida, fazendo este raciocínio para todos os pares de
casais.
 
De cara, fazendo este raciocínio para H1 e H2, já eliminamos metade das
combinações!
 
O que acham??
 
JG

-----Original Message-----
From: Domingos Jr. [mailto:dopikas@uol.com.br]
Sent: Thursday, October 17, 2002 7:50 PM
To: obm-l@mat.puc-rio.br
Subject: Re: [obm-l] Teorema de Donald


Um algoritmo feito assim pode varrer todas as combinações de pares possíveis
se isso for necessário (acho que é altamente improvável que isso ocorra,
talvez seja até impossível).
 
a demonstração que eu tinha imaginado para o problema (logo após a sua
primeira postagem) era +/- assim:
 
para n = 1 (1 casal) temos que é sempre possível obter um "1-casamento"
suponha para todo 1 <= n < k seja sempre possível obter um n-casamento
um (n+1)-casamento pode ser obtido da seguinte maneira:
1) Existe um subconjunto Hx (1<= x <= n), de x homens, e Mx, de x mulheres,
tal que para todo homem de Hx as x mulheres preferidas estão todas em Mx e
para toda mulher de Mx seux x homens preferidos estão em Hx.
    neste caso, podemos dividir o problema em dois menores, arranjando um
x-casamento e um (n + 1 - x)-casamento, o que é perfeitamente possível
dentro da hipótese de indução
 
2) há uma mistura total de gostos!, neste caso estamos com um problema chato
para resolver.
 
ainda não tive nenhuma boa idéia de como lidar com esse caso.
 

----- Original Message ----- 
From: Johann Peter Gustav Lejeune  <mailto:peterdirichlet2002@yahoo.com.br>
Dirichlet 
To: obm-l@mat.puc-rio.br <mailto:obm-l@mat.puc-rio.br>  ;
teoremalista@yahoogrupos.com.br <mailto:teoremalista@yahoogrupos.com.br>  ;
teoremaprob@yahoogrupos.com.br <mailto:teoremaprob@yahoogrupos.com.br>  
Sent: Thursday, October 17, 2002 3:59 PM
Subject: [obm-l] Teorema de Donald


Para quem nao leu minha mensagem nem se tocou de que estou vivo :):)

A demonstraçao sera assim:Escolha um homem M1,e noive com a predileta M1.

ALGORITMO:

1)Escolha um homem solteiro.

2)Verifique quem e sua predileta,e

2') faça com que ele a proponha em noivado.

3)Se a moça for solteira,ela aceita incondicionalmente;caso ela esteja
noivada,ela escolhe,dentre seu noivo e o proponente,o mais bem colocado da
sua lista de preferencias.

4)Deste passo,pode ocorrer:

4.1-A moça pretendida e solteira.Deve-se entao retornar a 1).

4.2a-A moça pretendida e noivada e o rejeita.Neste caso ele procura pela sua
segunda predileta,e volta a 2')

4.2b-A moça pretendida e noivada e o aceita.Assim sendo seu ex-noivo age
como em 4.2a.

Quando o processo acabar trealiza-se um n-casamento.

Agora dei o exercicio de bandeja:PROVE QUE ISTO DA CERTO.

 

Te mais galera!!!!!!!!!!!



TRANSIRE SVVM PECTVS MVNDOQUE POTIRE

CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE

Fields Medal(John Charles Fields)




  _____  

Yahoo! GeoCities <http://br.geocities.yahoo.com/> 
Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e
acessórios.

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================