LIX OM - I -Zadanie 7

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

W $n$ -osobowym stowarzyszeniu działa $2n-1$ komisji (każdy niepusty zbiór członków stowarzyszenia
tworzy komisję). W każdej komisji należy wybrać przewodniczącego. Wymagany jest przy tym warunek: Jeżeli
komisja $C$ jest sumą $C = A\cup B$ dwóch komisji $A$ i $B$ , to przewodniczący komisji $C$ jest też
przewodniczącym co najmniej jednej z komisji $A$ , $B$ . Wyznaczyć liczbę możliwych wyborów przewodniczących.

Rozwiązanie

Odpowiedź: n!.

Wskażemy wzajemnie jednoznaczną odpowiedniość między możliwymi wyborami przewodniczących komisji
a sposobami przydzielenia członkom stowarzyszenia numerów $1, 2, \dots , n$ (przy czym różnym członkom
przydzielone są różne numery). Tych ostatnich jest oczywiście tyle samo, ile permutacji zbioru $n$ -elementowego,
czyli $n!$ .

Przypuśćmy więc, że w każdej komisji wybrano przewodniczącego zgodnie z założeniami zadania.
Przypisujemy członkom stowarzyszenia numery indukcyjnie w następujący sposób:

Numer 1 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia.
Numer 2 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia oprócz członka o numerze 1.
Numer 3 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia oprócz członków o numerach 1 i 2, itd.

Wykażemy, że przy takim sposobie przypisania numerów spełniony jest następujący warunek:

(*) Przewodniczącym dowolnej komisji jest ten spośród jej członków, któremu przydzielony jest najmniejszy numer.

Rzeczywiście, rozpatrzmy dowolną komisję $A$ i niech $k$ będzie najmniejszym z numerów przypisanych członkom
tej komisji. Niech $B$ będzie komisją złożoną z wszystkich członków stowarzyszenia, którym przydzielono numery
nie mniejsze niż $k$ . Ze sposobu rozdzielenia numerów wynika, że przewodniczącym komisji $B$ jest członek
o numerze $k$ . Ponadto komisja $B$ jest sumą dwóch komisji: $A$ oraz $B\A$ . Ponieważ członek o numerze
$k$ nie należy do komisji $B\A$ , więc zgodnie z warunkami zadania musi on być przewodniczącym komisji A.

Określiliśmy więc odwzorowanie, które wyborowi przewodniczących komisji przyporządkowuje sposób przydzielenia
członkom stowarzyszenia liczb $1, 2, \dots , n$ . Aby dokończyć rozwiązanie zadania, wskażemy teraz odwzorowanie
odwrotne.

Mianowicie, jeżeli członkom stowarzyszenia przypisano liczby $1, 2, \dots , n$ , to w każdej komisji
wybieramy na przewodniczącego tego jej członka, który ma najmniejszy numer (warunek (*) będzie więc spełniony).
Jeżeli komisja $C$ jest sumą $C = A\cup B$ dwóch komisji $A, B$ i członek o numerze $k$ jest przewodniczącym
komisji $C$ , to należy on do jednej z komisji $A, B$ , w której jest członkiem o najniższym numerze — a więc jest
jej przewodniczącym. Widzimy zatem, że warunek dany w treści zadania jest spełniony. Wobec tego jeżeli
rozpoczniemy od wyborów przewodniczących komisji, przyporządkujemy członkom stowarzyszenia numery zgodnie
z określoną wcześniej zasadą, a następnie z tych numerów odtworzymy przewodniczących komisji, to
otrzymamy wyjściowy wybór przewodniczących. Podobnie jeżeli rozdzielimy numery członkom stowarzyszenia, na
ich podstawie wybierzemy przewodniczących komisji, a potem zgodnie z opisaną procedurą indukcyjną przypiszemy
członkom numery, to będą one tożsame z wyjściowymi numerami. W takim razie określone odwzorowania są wzajemnie
odwrotne, co kończy rozwiązanie.