Matematické Fórum

↑ check_drummer:

no je to problém převzatý z open kurzu z MIT, stručně řečeno:

Máme n žen a n mužů,
každá žena i muž má svůuj preferenční list, kde má seřazeny
všechny osoby opačného pohlaví sestupně podle preference,
úkolem je najít stabilní párovaní, tedy takové rozdělení do
manželských dvojic, aby si novým sňatkem alespoň jeden z
novomanželů pohoršil.

Popis jedné iterace (jednoho dne):

Dokud není splněna ukončovací podmínka, probíhá každý den takto:

Ráno: každá žena stojí na svém balkóně. Každý muž stojí pod
balkónem ženy, která je nejvýše v jeho seznamu, a dvoří se jí.
Muži s prázdným seznamem jsou doma.

Odpoledne: každá žena, pod jejíž balkónem jsou alespoň dva
muži, řekne tomu v seznamu nejvýše položenému, aby přišel zítra
a ostatním, at’ už nechodí.

Večer: každý odehnaný muž si škrtne ze svého seznamu ženu,
která ho dnes odehnala.

Ukončovací podmínka: každé ženě se dvoří nejvýš jeden muž.

Konkretní příklad:


Děkuju moc že se o to zajímáte

Zkusím to jen o trochu elegantněji (a je na posouzení, jestli to ve výsledku elegantnější bude : )) ):

Říkejme jevu "jeden den se u ženy objeví alespoň dva muži" např. jednoduše "výskyt" a počítejme výskyty a dny:

Fakt1: Za 1 den můžou proběhnout nejvýše 2 výskyty (jinak by mužů muselo být alespoň 6).
Fakt2: Musí proběhnout alespoň 5 výskytů, než bude párování dokončeno.
Z toho plyne: Děj musí probíhat alespoň tři dny.

Fakt 3: Od chvíle, kdy nějaký muž přijde k ženě, blokuje tato žena jednoho muže (ne nutně konkrétního, ale kvantitativně) po celý zbytek procesu.
Z toho plyne: uskuteční-li se libovolným způsobem tři výskyty, v dalších dnech již budou k dispozici nejvýše dva muži. Uskuteční-li se lib. způsobem čtyři výskyty, další den bude k dispozici pouze jeden muž.

Zanedbejme tedy teď dny, ve kterých neproběhne výskyt (situace s muži k dispozici se vždy buď jen zhorší - ubude jich - nebo nezmění). Během prvních dvou dnů můžou proběhnout nejvýše tři výskyty. Zbudou tedy nejvýše dva neblokovaní muži a dvě ženy, u nichž by se měl uskutečnit výskyt, což zřejmě nemá řešení.

I kdyby v prvních dvou dnech nakrásně proběhly čtyři výskyty, pátý již určitě neproběhne (nedostatek mužů).

Pozn: býti k dispozici znamená "mít možnost vyskytnout se ve výskytu u některé z žen, u níž výskyt ještě neproběhl" - je to však údaj kvantitativní a neváže se na jednotlivé muže, nýbrž jen na počet mužů.
Pozn2: Zavedená terminologie působí dost hrozivě a prosím všechny feministy a feministky, aby si ji přizpůsobili, příp. aby zaměnili názvy "žena" a "muž" : ))

Jde přinést daleko snažší argument, že dokonce pro obecné n nemůže být, aby se každé ženě alespoň v jedné iteraci dvořícího rituálu dvořili současně alespoň dva muži.

Jak už psal ↑ OiBobik: ve faktu 3, je jasné, že jakmile se u nějaké ženy objeví nějaký muž, pak až do konce celého procesu se u ní objeví alespoň jeden muž (vždy alespoň ten nejúspěšnější z předchozího kola).

Poslední kolo, kdy u každé ženy stojí jeden muž, se samozřejmě "nepočítá".

Využijme toho, že celý dvořící algoritmus skončí a dá nějaké řešení.

Není-li poslední kolo současně kolo první (kdy by nebylo co řešit), pak v předposledním kole existuje žena, u které nikdo nestojí (kdyby taková žena neexistovala, pak jsme v kole posledním, ale to nejsme). No ale protože je to kolo předposlední, za kterým je už jen kolo poslední, a protože v posledním kole stojí u každé ženy jediný muž, tak u této ženy nikdy nebudou stát muži dva.

EDIT: Dokonce jsem dokázal drobně víc: Existuje alespoň jedna žena, u které se poprvé nějaký muž objeví až v závěrečném kole.