Komentarz

XXXIII OM - III - Zadanie 1

Wskazać taki sposób rozmieszczenia przy okrągłym stole $ n $ dziewcząt i $ n $ chłopców, aby liczba $ d_n - c_n $ była największa, gdzie $ d_n $ jest liczbą dziewcząt, siedzących między dwoma chłopcami, zaś $ c_n $ - liczbą chłopców siedzących, między dwiema dziewczętami.

Rozwiązanie

Rozważmy dowolne rozsadzenie $ n $ dziewcząt i $ n $ chłopców. Nazwijmy grupą $ k $ dziewcząt (dla $ k > 1 $) każdy ciąg $ k $ dziewcząt siedzących obok sie*bie, jeśli pierwsza i $ k $-ta dziewczynka z tego ciągu sąsiaduje przy stole z chłopcem. Niech $ D_n $ będzie liczbą grup dziewcząt w danym rozsadzeniu. Analogicznie definiujemy grupę $ k $ chłopców. Niech $ C_n $ będzie liczbą grup chłopców. Ponieważ każda grupa dziewcząt sąsiaduje z grupą chłopców lub z pojedynczym chłopcem i każda grupa chłopców sąsiaduje z grupą dziewcząt lub z pojedynczą dziewczynką, więc

\[<br /> d_n + D_n = c_n + C_n,<br /> \]

skąd

\[<br /> (*) \qquad d_n - c_n = C_n - D_n.<br /> \]

Jeśli $ D_n = 0 $, to każda dziewczynka sąsiaduje z dwoma chłopcami, skąd wynika, że każdy chłopiec sąsiaduje z dwiema dziewczynkami, więc $ C_n = 0 $ i $ d_n - c_n = 0 $. Jeśli natomiast $ D_n \geq 1 $, to z równości (*) wynika, że

\[<br /> d_n - c_n \leq C_n - 1.<br /> \]

Z drugiej strony $ C_n $ jest liczbą grup chłopców, a każda grupa zawiera co
najmniej dwóch chłopców, więc $ C_n \leq \frac{n}{2} $. Ponadto $ C_n $ jest liczbą całkowitą, więc $ C_n \leq \left[ \frac{n}{2} \right] $. ($ [k] $ jest największą liczbą całkowitą mniejszą lub równą $ k $). Wobec tego

\[<br /> d_n - c_n \leq \left[ \frac{n}{2} \right] - 1<br /> \]

przy każdym rozsadzeniu $ n $ dziewcząt i $ n $ chłopców.

Pokażemy teraz takie rozsadzenie, przy którym $ d_n - c_n = \left[ \frac{n}{2} \right] - 1 $. Jeśli $ n = 2k $, to sadzamy kolejno dwóch chłopców, jedną dziewczynkę, dwóch chłopców, jedną dziewczynkę itd., wreszcie ostatnich dwóch chłopców i dalej pozostałe dziewczęta. Przy tym rozsadzeniu $ k - 1 $ dziewcząt ma po obu stronach chłopców, natomiast żaden chłopiec nie ma dwóch sąsiadek.

Jeśli $ n = 2k + 1 $, to sadzamy podobnie: dwóch chłopców, jedną dziewczynkę, dwóch chłopców, jedną dziewczynkę itd. wreszcie ostatnich trzech chłopców i resztę dziewcząt. W tej sytuacji również $ k - 1 $ dziewcząt siedzi między dwoma chłopcami, a żaden chłopiec nie ma dwóch sąsiadek.

Wobec tego maksymalna wartość $ d_n - c_n $ wynosi $ \left[ \frac{n}{2} \right]-1 $.

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

Dodaj komentarz