XLVIII MOM - Zadanie 3

W zawodach matematycznych niektórzy uczestnicy przyjaźnią się. Przyjaźń jest zawsze wzajemna. Grupę uczestników nazwiemy kliką, jeśli każdych dwóch zawodników tej grupy przyjaźni się. (W szczególności, każda grupa złożona z mniej niż dwóch zawodników jest kliką.) Liczbę osób, jaką liczy klika nazwiemy jej rozmiarem.

Wiadomo, że w zawodach tych rozmiar największej kliki jest liczbą parzystą. Dowieść, że uczestników zawodów można rozdzielić do dwóch pokoi tak, aby rozmiar największej kliki w jednym pokoju był równy rozmiarowi największej kliki w drugim pokoju.

Rozwiązanie

Przedstawimy algorytm rozdzielenia uczestników zawodów do dwóch pokoi, które będziemy nazywać Pokój A oraz Pokój B. Rozpoczniemy od pewnego początkowego rozdzielenia, a następnie będziemy wielokrotnie przenosić jedną osobę do drugiego pokoju, tak by w efekcie uzyskać rozdzielenie spełniające warunki zadania.

Na każdym etapie postępowania niech $A$ i $B$ oznaczają zbiory uczestników znajdujących się w odpowiednich pokojach, zaś $k(A)$ oraz $k(B)$ - rozmiary największych klik w tych pokojach.

Postępowanie składa się z czterech kroków.

Krok 1. Niech $M$ będzie jedną z klik największego rozmiaru. Z założenia rozmiar $|M|=2m$ jest liczbą parzystą. Umieśćmy wszystkich zawodników z tej kliki w pokoju $A$ , a pozostałych uczestników w pokoju $B$ .

Ponieważ $M$ jest kliką największego rozmiaru, w takim początkowym rozmieszczeniu prawdziwa jest zależność $k(A)=|M|\ge k(B)$ .

Krok 2. Dopóki zachodzi nierówność $k(A)>k(B)$ , przenosimy dowolnie wybraną osobę z pokoju $A$ do pokoju $B$ .

Zauważmy przede wszystkim, że nierówność $k(A)>k(B)$ oznacza, że pokój $A$ jest niepusty. Ponadto wszyscy aktualni mieszkańcy pokoju $A$ tworzą klikę, więc po przeniesieniu jednej osoby z tego pokoju rozmiar największej kliki w pokoju $A$ zmniejszy się o 1. Natomiast rozmiar największej kliki w pokoju $B$ nie zmienia się albo zwiększy się o 1.

Po wielokrotnym przeprowadzeniu przeniesienia jednej osoby z pokoju $A$ do pokoju $B$ otrzymamy sytuację, w której

$ k(A)=k(B)\quad\hbox{albo}\quad k(A)=k(B)-1. $

Dodatkowo w pokoju $A$ pozostało co najmniej $m$ osób, gdyż w przeciwnym razie w pokoju $B$ znalazłoby się przynajmniej $m+1$ osób należących do kliki $M$ , a w pokoju $A$ pozostałoby najwyżej $m-1$ osób; mielibyśmy więc $k(A)\le m-1$ , $k(B)\ge m+1$ , wbrew uzyskanej wcześniej alternatywie.

Jeżeli $k(A)=k(B)$ , to otrzymane rozmieszczenie uczestników spełnia warunki zadania.

Możemy więc przyjąć w dalszej części rozumowania, że $k(A)=n$ oraz $k(B)=n+1$ . Jak udowodniliśmy powyżej, mamy wówczas

$ n=|A|=|A\cap M|\ge m\quad\hbox{oraz}\quad|B\cap M|\le m. $

Krok 3.Jeżeli istnieje uczestnik $x\in B\cap M$ oraz $(n+1)$ -elementowa klika $C$ , do której uczestnik $x$ nie należy, to przenosimy uczestnika $x$ do pokoju $A$ .

Uczestnik $x$ należy do kliki $M$ i wobec tego po przeniesieniu go do pokoju $A$ w pokoju tym znajdzie się $n+1$ uczestników, z których wszyscy należą do tej kliki. W efekcie $k(A)=n+1$ . Ponadto rozmiar największej kliki w pokoju $B$ wynosił $n+1$ przed przeniesieniem uczestnika $x$ , zaś $(n+1)$ -osobowa klika $C$ pozostała w całości w pokoju $B$ . Tak więc $k(B)=n+1$ , czyli $k(A)=k(B)$ .

Zatem jeśli udało się wykonać krok 3, uzyskaliśmy żądane rozmieszczenie uczestników w pokojach. W przeciwnym razie przechodzimy do kroku 4.

Krok 4. Dopóki spełniona jest równość $k(B)=n+1$ , wybieramy dowolną $(n+1)$ -osobową klikę $C$ znajdującą się w pokoju $B$ i przemieszczamy jednego uczestnika $x\in C\setminus M$ do pokoju $A$ .

Zauważmy przede wszystkim, że procedura ta jest wykonalna:

$ |C|=n+1\ge m+1>m\ge|B\cap M|, $

co dowodzi, że zbiór $C\setminus M$ jest niepusty.

Przemieszczając jedną osobę z pokoju $B$ do pokoju $A$ zmniejszamy rozmiar $k(B)$ najwyżej o 1. Wobec tego po zakończeniu kroku 4 uzyskamy rozmieszczenie, w którym $k(B)=n$ .

Ponadto po zakończeniu kroku 4 w pokoju $A$ będzie znajdowała się $n$ -osobowa klika $A\cap M$ . Udowodnimy, że w tym pokoju nie ma większej kliki.

Niech więc $D$ będzie dowolną kliką w pokoju $A$ .

Uczestników umieszczonych w pokoju $A$ można podzielić na dwie grupy:

uczestnicy należący do kliki $M$ ;
uczestnicy, którzy w kroku 4 zostali
przeniesieni z pokoju $B$ .

Mieszkańcy pokoju $A$ należący do pierwszej grupy oczywiście przyjaźnią się ze wszystkimi osobami tworzącymi klikę $M$ . Weźmy teraz pod uwagę mieszkańca sklasyfikowanego w drugiej grupie. Ponieważ nie udało się wykonać kroku 3, więc przed rozpoczęciem kroku 4 każda $(n+1)$ -osobowa klika w pokoju $B$ zawierała $B\cap M$ jako podzbiór. Wobec tego każda osoba przeniesiona z tej kliki do pokoju $A$ przyjaźniła się ze wszystkimi osobami należącymi do kliki $B\cap M$ .

Udowodniliśmy w ten sposób, że wszyscy mieszkańcy pokoju $A$ przyjaźnią się ze wszystkimi uczestnikami kliki $B\cap M$ . Zauważmy następnie, że zbiór $D\cup(B\cap M)$ jest sumą dwóch klik: $D$ oraz $B\cap M$ ; ponadto każdy uczestnik należący do pierwszej kliki przyjaźni się z dowolnym uczestnikiem należącym do drugiej kliki. Wobec tego $D\cup(B\cap M)$ jest kliką. Jej rozmiar nie przekracza największego rozmiaru kliki wśród wszystkich uczestników zawodów, czyli liczby $|M|$ . Stąd mamy