Rozważmy układ dziewcząt i chłopców, w którym każdy podzbiór dziewczyn
zna co najmniej tyle chłpców ile jest w podzbiorze tym.
Dziewcząt jest \(\displaystyle{ n}\) oraz każda z nich zna conajmniej \(\displaystyle{ m(n\ge m)}\) chłopaków.
Pokazać, że \(\displaystyle{ n}\) par małżeński może być dobranych na \(\displaystyle{ m!}\) sposobów.
Postępowanie indukcyjne po \(\displaystyle{ m}\)
Gdy \(\displaystyle{ m=1}\) to każda dziewczyna zna choć jednego chłopaka.
Czyli normalna sytuacja, zawsze każda zna choć jednego, a więc istnieje choć 1! sposób na sparowanie.
Następnie załóżmy, że można sparować \(\displaystyle{ <m}\) dziewcząt.
Chcemy dobrać chlopaka \(\displaystyle{ m-tej}\) dziewczynie. Przypuścmy, że parując wybieraliśmy dla
tych \(\displaystyle{ m}\)pierwszych pann chłopaków, tak że nie został popsuty warunek Halla. A skoro tak,
to można wybrać dla tej dziewczyny jeszcze chłopaka którego NA PEWNO zna.
Nawet jeśli był niefart i dziewczyny dla których wybieraliśmy panów, których znają zawsze
uszczuplały grono wolnych i znanych panów dla dalszych pań, to i tak na razie wystarcza.
Czyli w tej sytuacji jest ok.
Jednak co jeśli jedna z pań wybierając chłopaka popsuła warunek Halla dla pozostałch osób ?
Ustalmy, że pierwsza dziewczyna już popsuła ten warunek.
No, ale ten warunek miał moc zanim wybrała, a więc skoro go była w stanie poposuć to musi
istnieć pewne \(\displaystyle{ n'}\) dziewcząt, które znają dokładnie \(\displaystyle{ n'}\) panów.
A jasne, że \(\displaystyle{ m\le n' \le n}\). Tak czy inaczej te panie muszą się ożenić właśnie z tymi panami.
Tzn, one muszą wybrać z tych \(\displaystyle{ n'}\) panów. Więc jeśli był niefart i każda z nich
w obrębie tych panów których zna z warunku zadania - zna tych samych. Tzn znają doładnie tych samych facetów, to
mogą wybierać na \(\displaystyle{ m!}\) sposobów.
A więc chyba koniec.
Proszę jak zawsze o sprawdzenie, bo pewnie gdzieś jakiś bug siedzi.