Komentarz

LIX OM - I -Zadanie 7

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz