Matematyka.pl

Na przyjęciu jest \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ n}\) chłopców. Każda dziewczyna lubi \(\displaystyle{ r}\) chłopców, a każdy chłopiec lubi \(\displaystyle{ s}\) dziewcząt. Udowodnić, że jeżeli \(\displaystyle{ r+s >n}\), to istnieje para, która lubi się nawzajem, a jeżeli \(\displaystyle{ r+s \le n}\) to może być tak, że każde uczucie jest nieodwzajemnione.

Niech \(\displaystyle{ C, D}\) będą zbiorami chłopców i dziewcząt. Dla \(\displaystyle{ x,y\in C\cup D}\) będziemy pisali
$$xLy\,\Leftrightarrow\,x\mbox{ lubi }y$$
Oczywiście relacja \(\displaystyle{ L}\) nie musi być symetryczna i zachodzi tylko pomiędzy przedstawicielami różnych płci. Dla ustalonego \(\displaystyle{ c \in C}\) wprowadzamy zbiory
$$L_c = \big\{d\in D\,\big|\,dLc\big\},\,D_c = \big\{d\in D\,\big|\,cLd\big\}$$
Mamy
$$\sum_{c\in C}|L_c| = \sum_{d\in D}\bigg|\big\{c\in C\,\big|\,dLc\big\}\bigg| = n\cdot r$$
Stąd wynika, że istnieje chłopiec \(\displaystyle{ c}\) taki, że \(\displaystyle{ |L_c| \geq r}\). Zatem
$$|L_c| + |D_c| \geq r + s > n$$
a wiec zbiory \(\displaystyle{ L_c}\) i \(\displaystyle{ D_c}\) mają niepuste przecięcie. Oznacza to, że istnieje dziewczyna \(\displaystyle{ d}\) taka, że \(\displaystyle{ dLc}\) oraz \(\displaystyle{ cLd}\).

W przypadku \(\displaystyle{ r + s \leq n}\) można skonstruować kontrprzykład. Należy rozłożyć sympatie dziewcząt równomiernie (co się nie zdarza w rzeczywistości ze względu na dobór płciowy) tzn. każda dziewczyna lubi \(\displaystyle{ r}\) chłopców oraz każdy chłopiec jest lubiany przez dokładnie \(\displaystyle{ r}\) dziewczyn. Taki rozkład jest możliwy. Następnie dla każdego chłopca \(\displaystyle{ s}\) jego sympatie ustalić jako te dziewczyny, które go nie lubią. To jest możliwe, bo \(\displaystyle{ r + s \leq n}\).