XLIV OM - I - Zadanie 11

Zawody matematyczne:

XLIV OM, 1992-1993

Etap:

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

$ \begin{split} 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} =\\ &=\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)} . \end{split} $

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

$ L_n = (n^6-15n^5 +\phi(n))^2 = n^{12}-30n^{11} +f(n), $

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

$ M_n = n^{12} - 15n^{10} + \psi(n) = n^{12} + g(n), $

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

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

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

$ \lim_{n\to \infty} n^{-11}(g(n)-f(n))=0, \quad \lim_{n\to \infty} n^{-12}g(n) = 0, $

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