XXXIII OM - III - Zadanie 1

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

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

$ d_n + D_n = c_n + C_n, $

skąd

$ (*) \qquad d_n - c_n = C_n - D_n. $

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

$ d_n - c_n \leq C_n - 1. $

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

$ d_n - c_n \leq \left[ \frac{n}{2} \right] - 1 $

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$ .