Bài toán 100 con gà là gì?
Trong cuộc thi Raytheon MATHCOUNTS National Competition – NYSSPE năm 2017 của Mỹ, ở vòng chung kết có một câu hỏi như sau:
In a barn, 100 chicks sit peacefully in a circle. Suddenly, each chick randomly pecks the chick immediately to its left or right. What is the expected number of unpecked chicks?
Tạm dịch: Trong một kho thóc, 100 con gà ngồi yên lặng theo vòng tròn. Đột nhiên, mỗi con gà ngẫu nhiên quay sang mổ một con gà khác ngồi cạnh mình (có thể là bên trái hoặc bên phải). Vậy, kì vọng có bao nhiêu con gà không bị mổ?
Luke Robitaille, người giành 4 HCV IMO, một trong những người giành nhiều HCV IMO nhất, khi đó mới 13 tuổi, đã chiến thắng cuộc thi với câu trả lời chính xác chỉ sau 1 giây suy nghĩ.
Lời giải Bài toán 100 con gà!
Đáp án là 25.
Đối với mỗi con gà bất kì, xác suất để con bên phải không mổ nó là $0{,}5$ và xác suất để con bên trái không mổ nó cũng là $0{,}5$. Như vậy xác suất để con gà đó không bị mổ là $0{,}5\times 0{,}5 = 0{,}25$.
Vì điều này đúng với mọi gà, nên ta có thể cộng lại, trong $100$ con gà thì ta kì vọng có $0{,}25\times 100=25$ con gà không bị mổ!
“Nhưng khoan,” bạn có thể nói, “xác suất gà con không bị mổ không độc lập! Nếu gà con thứ $n$ không bị mổ, thì nghĩa là con gà thứ $n-2$ và con $n+2$ sẽ bị mổ. Chắc chắn chúng ta phải xem xét đến điều này!”
May mắn thay, có một định lý rất hữu ích được gọi là tuyến tính của kỳ vọng (linearity of expectation). Điều này cho chúng ta biết rằng đối với bất kỳ biến ngẫu nhiên nào $X$ và $Y$, độc lập hay không, thì kì vọng $E[X+Y]=E[X]+E[Y]$, ở đây $E$ là giá trị mong đợi (kỳ vọng).
Những gì chúng tôi lập luận ở trên là chỉ định một biến ngẫu nhiên $X_i$ với con gà thứ $i, E[X_i] = 0$ nếu con gà bị mổ và $E[X_i] = 1$ nếu nó không bị mổ. Khi đó tổng số con gà là $\sum X_i$ nên số gà chưa không bị mổ kỳ vọng là $$ E\left[\sum X_i\right] = \sum E\left[X_i\right]. $$
