|
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 -----
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
Tudo
para criar o seu site: ferramentas fáceis de usar, espaço de sobra e
acessórios.
|