XXXIX OM - I - Zadanie 9

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Spośród wierzchołków $n$ -kąta foremnego ( $n \geq 4$ ) wybrano cztery różne. Wybór każdej czwórki wierzchołków jest jednakowo prawdopodobny. Obliczyć prawdopodobieństwo tego, że wszystkie wybrane wierzchołki leżą na pewnym półokręgu (przyjmujemy, że do półokręgu należą jego końce).

Rozwiązanie

Niech $W$ będzie zbiorem wszystkich $n$ wierzchołków rozważanego $n$ -kąta foremnego.

Oznaczmy szukane prawdopodobieństwo przez $P(n)$ . Wyraża się ono ułamkiem

$ P(n)= \frac{L(n)}{M(n)}, $

którego mianownik jest liczbą wszystkich czteroelementowych podzbiorów zbioru $W$ , a licznik jest liczbą czteropunktowych podzbiorów $W$ zawartych w półokręgach. Oczywiście

$ M(n) = \binom{n}{4} = \frac{1}{24} n(n-1)(n-2)(n-3). $

Wykażemy poniżej, że licznik dany jest wzorem

$ (1) \qquad L(n) = \left\{ \begin{array}{ll} \frac{1}{48}n^2(n-2)(n-4) & \textrm{dla} \ n \ \textrm{parzystych}\\ \frac{1}{48}n(n-1)(n-3)(n-5) & \textrm{dla} \ n \ \textrm{nieparzystych.} \end{array} \right. $

Stąd wyniknie odpowiedź na postawione w zadaniu pytanie:

$ (2) \qquad P(n) = \left\{ \begin{array}{ll} \frac{n(n-4)}{2(n-1)(n-3)} & \textrm{dla} \ n \ \textrm{parzystych}\\ \frac{n-5}{2(n-5)} & \textrm{dla} \ n \ \textrm{nieparzystych.} \end{array} \right. $

Pozostaje udowodnić wzór (1). Dla $n = 4$ , $n = 5$ nie ma czwórki wierzchołków zawartej w półokręgu. Zatem $L(4) = 0$ , $L(5) = 0$ , co zgadza się z (1). W dalszym ciągu zakładajmy, że $n \geq 6$ .

Rozważane w zadaniu półokręgi muszą być zawarte w okręgu opisanym na danym wielokącie. Ustalmy orientację (kierunek obiegu) tego okręgu. Każdy jego półokrąg ma wówczas wyróżniony początek i koniec.

Jeśli $V$ jest czteropunktowym podzbiorem zbioru $W$ zawartym w półokręgu, to wśród wszystkich zawierających go półokręgów istnieje dokładnie jeden półokrąg, którego początek jest punktem zbioru $V$ . Oznaczmy ten półokrąg przez $C_V$ .

Niech teraz $C$ będzie pewnym ustalonym półokręgiem o początku i końcu $W$ zbiorze $W$ . Liczba czteropunktowych zbiorów $V \subset W$ , dla których $C_V = C$ ,
wynosi $\binom{[n/2]}{3}$ wynika to stąd, że jeden z punktów zbioru $V$ musi być początkiem półokręgu $C$ , dalsze zaś trzy punkty zbioru $V$ można wybrać dowolnie spośród pozostałych $[n/2]$ punktów zbioru $W$ należących do $C$ .