XLIV OM - I - Zadanie 11

W sześciu różnych okienkach tabeli o wymiarach $ n \times n $ stawiamy krzyżyk; wszystkie układy krzyżyków są jednakowo prawdopodobne. Niech $ p_n $ będzie prawdopodobieństwem tego, że w pewnym rzędzie poziomym lub pionowym znajdą się co najmniej dwa krzyżyki. Obliczyć granicę ciągu $ (np_n) $, gdy $ n \to \infty $.

Rozwiązanie

Zdarzenia elementarne są wyznaczone przez sześcioelementowe podzbiory zbioru $ n^2 $ okienek tabeli; jest ich $ \binom{n^2}{6} $. Niech $ \mathcal{Z} $ będzie zdarzeniem przeciwnym do zdarzenia rozważanego w zadaniu. Zdarzeniu $ \mathcal{Z} $ sprzyjają konfiguracje uzyskane w następujący sposób: pierwszy krzyżyk stawiamy w dowolnie wybranym okienku: mamy tu $ n^2 $ możliwości. Następnie ,,wykreślamy'' cały rząd poziomy i cały rząd pionowy, na przecięciu których postawiliśmy pierwszy krzyżyk, po czym stawiamy drugi krzyżyk w dowolnym spośród pozostałych okienek: tak więc teraz mamy $ (n-1)^2 $ możliwości. Powtarzamy ten schemat jeszcze czterokrotnie i uzyskujemy liczbę możliwości równą $ n^2 (n -1 )^2 (n - 2)^2 (n - 3)^2 (n - 4 )^2 (n - 5)^2 $. Trzeba ją jeszcze podzielić przez $ 6! $ (liczbę permutacji zbioru sześcioelenientowego), aby uniezależnić rozumowanie od kolejności stawiania krzyżyków.

Tak więc prawdopodobieństwo zdarzenia $ \mathcal{Z} $ (równe $ 1 -p_n $) wynosi

\[<br />
\begin{split}<br />
1-p_n =& \frac{n^2(n- 1)^2(n - 2)^2(n - 3)^2(n - 4)^2(n - 5)^2}{6!} \cdot \binom{n^2}{6}^{-1} =\\<br />
&=\frac{ [n(n - 1)(n - 2)(n - 3)(n - 4)(n - 5)]^2} { n^2(n^2 - 1)(n^2 - 2)(n^2 - 3)(n^2 -4)(n^2 - 5)} .<br />
\end{split}<br />
\]

Nie należy wymnażać wszystkich tych czynników! Oznaczmy licznik otrzymanego ułamka przez $ L_n $, a mianownik przez $ M_n $. Wystarczy zauważyć, że

\[<br />
L_n = (n^6-15n^5 +\phi(n))^2 = n^{12}-30n^{11} +f(n),<br />
\]

gdzie $ \phi(n) $ oraz $ f(n) $ są wielomianami (zmiennej $ n $), odpowiednio stopnia (co najwyżej) $ 4 $ i $ 10 $; podobnie,

\[<br />
M_n = n^{12} - 15n^{10} + \psi(n) = n^{12} + g(n),<br />
\]

gdzie $ \psi(n) $ oraz $ g(n) $ są wielomianami (zmiennej $ n $), odpowiednio stopnia (co najwyżej) $ 8 $ i $ 10 $. Wobec tego

\[<br />
np_n=n\left(1-\frac{L_n}{M_n}\right)=n\cdot \frac{30n^{11}+g(n)-f(n)}{n^{12}+g(n)}=\frac{30+n^{-11}(g(n)-f(n))}{1+n^{-12}g(n)}.<br />
\]

A ponieważ wielomiany $ f(n) $ i $ g(n) $ są stopnia (co najwyżej) dziesiątego, zatem

\[<br />
\lim_{n\to \infty} n^{-11}(g(n)-f(n))=0, \quad      \lim_{n\to \infty} n^{-12}g(n) = 0,<br />
\]

i w konsekwencji $ \displaystyle \lim_{n\to \infty} np_n = 30 $.

Komentarze

Dodaj nową odpowiedź