XLII OM - I - Zadanie 12

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dla dowolnej liczby naturalnej $n$ rozważamy prostopadłościan $K_n$ o krawędziach długości $1,1,n$ oraz zbiór $R_n$ złożony z $4n+1$ punktów: wierzchołków prostopadłościanu $K_n$ oraz punktów dzielących jego dłuższe krawędzie na odcinki długości jednostkowej. Wybieramy ze zbioru $R_n$ losowo trzy różne punkty. Niech $p_n$ będzie prawdopodobieństwem tego, że wybrane punkty są wierzchołkami trójkąta rozwartokątnego. Obliczyć $\lim_{n\to \infty} p_n$ .

Uwaga: Trzy punkty współliniowe nie tworzą trójkąta.

Rozwiązanie

Oznaczmy przez $Q(n)$ liczbę wszystkich trójelementowych podzbiorów zbioru $R_n$ , przez $T(n)$ - liczbę niezdegenerowanych trójkątów o wierzchołkach w zbiorze $R_n$ , a przez $P(n)$ - liczbę trójkątów rozwartokątnych. Badane prawdopodobieństwo jest ułamkiem $p_n = P(n)/Q(n)$ . Zauważmy, że

$ Q(n) =\binom {4n+4}{3}, \quad T(n) = \binom{4n+4}{3} - 4\binom {n+1}{3}. $

(Uzasadnienie drugiej równości: od liczby wszystkich trójek odejmujemy liczbę trójek punktów współliniowych - czyli trójek punktów leżących na dowolnej z czterech krawędzi, z których każda zawiera po $n +1$ punktów zbioru $R_n$ .)

Po rozpisaniu symboli Newtona otrzymujemy wzory

$ \begin{split} & Q(n) = \frac{(4n+4)(4n+3)(4n+2)}{6} = \frac{32}{3}n^3 + \textrm{(składniki niższych stopni)},\\ & T(n) = Q(n) - 4 \cdot \frac{(n+1)n(n-1)}{6} = 10n^3 + \textrm{(składniki niższych stopni)}. \end{split} $

Podzielmy zbiór $R_n$ na czteroelementowe ,,warstwy'' $H_0, H_1,\ldots, H_n$ : wierzchołki jednej z kwadratowych ścian prostopadłościanu $K_n$ tworzą warstwę $H_0$ , wierzchołki drugiej - warstwę $H_n$ ; warstwa $H_k$ składa się z punktów zbioru $R_n$ odległych od płaszczyzny warstwy $H_0$ o $k$ jednostek.

Skoro interesuje nas graniczne (przy $n \to \infty$ ) zachowanie rozważanych wielkości, możemy założyć, że $n \geq 4$ .

Ustalmy liczbę naturalną $r$ , $3 \leq r \leq n-1$ , i wybierzmy dowolne numery $k,m \in \{0,1,\ldots,n\}$ takie, że $m - k = r + 1$ . Między warstwami $H_k$ a $H_m$ jest więc $r$ warstw. Wybierając dowolnie punkty $A \in H_k$ , $C \in H_m$ oraz $B \in H_l$ , gdzie $l \in \{k + 1,\ldots,m-1\}$ , otrzymujemy albo trójkąt rozwartokątny albo współliniową trójkę punktów (bo $m-k \geq 4$ ). Mamy $16$ możliwości usytuowania pary punktów $A$ i $C$ oraz $4r$ możliwych położeń punktu $B$ - łącznie $64r$ możliwości; $4r$ spośród nich daje trójki współliniowe. Pozostaje $60r$ trójkątów rozwartokątnych.

Ponieważ numery $k$ , $m$ (o danej różnicy $r+1$ ) można ustalić na $n-r$ sposobów, zatem liczba $P(n)$ wszystkich możliwych do utworzenia trójkątów rozwartokątnych jest nie mniejsza niż suma

$ \begin{split} S(n) & = \sum_{r=3}^{n-1} 60r(n-r) = 60 \left( \sum_{r=1}^{n-1} (nr-r^2)-(3n-5) \right)=\\ & 60 \left( n \cdot \frac{(n-1)n}{2} - \frac{(n-1)n(2n-1)}{6} -3n+5 \right)= \\ & = 10n^3 +(\textrm{składniki niższych stopni}). \end{split} $

Mamy więc dwustronne oszacowanie

$ S(n) \leq P(n) \leq T(n). $

Wielkości $Q(n)$ , $T(n)$ , $S(n)$ są wielomianami trzeciego stopnia (zmiennej $n$ ). Współczynnik przy $n^3$ w $Q(n)$ równa się $32/3$ , natomiast w $T(n)$ i w $S(n)$ współczynnik przy $n^3$ równa się $10$ . Zatem

$ \lim_{n \to \infty} \frac{S(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16}, \quad \lim_{n \to \infty} \frac{T(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16} $

i na mocy twierdzenia o trzech ciągach

$ \lim_{n \to \infty} p_n = \lim_{n \to \infty} \frac{P(n)}{Q(n)} = \frac{15}{16}. $