XLII OM - I - Zadanie 12

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

\[<br /> Q(n) =\binom {4n+4}{3}, \quad T(n) = \binom{4n+4}{3} - 4\binom {n+1}{3}.<br /> \]

(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

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

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

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

Mamy więc dwustronne oszacowanie

\[<br /> S(n) \leq P(n) \leq T(n).<br /> \]

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

\[<br /> \lim_{n \to \infty} \frac{S(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16}, \quad<br /> \lim_{n \to \infty} \frac{T(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16}<br /> \]

i na mocy twierdzenia o trzech ciągach

\[<br /> \lim_{n \to \infty} p_n = \lim_{n \to \infty} \frac{P(n)}{Q(n)} = \frac{15}{16}.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź