Câu hỏi 33
Tìm số nguyên dương $n$ nhỏ nhất sao cho, nếu ban đầu có $n+1$ dân làng và $n$ tên côn đồ, thì xác suất dân làng thắng nhỏ hơn $1\%$.
Luật chính thức: số người còn lại. $T$: dân làng; $G$: côn đồ; $W$: thắng; $\mathrm M$: sáng; $\mathrm E$: tối.
$$\begin{gathered}
(T,G)\xrightarrow[T/(T+G)]{\mathrm{M}}(T-1,G),\qquad
(T,G)\xrightarrow[G/(T+G)]{\mathrm{M}}(T,G-1),\\
(T,0)\mapsto W_T\ (T\ge1),\quad(0,G)\mapsto W_G\ (G\ge1),\\
(T,G)\xrightarrow{\mathrm{E}}(T-1,G)\quad(T,G\ge1),\\
\mathrm{E}:\quad G\ge T_{\mathrm{new}}\Longrightarrow W_G,\qquad
W_T,W_G\Longrightarrow\mathrm{STOP}.
\end{gathered}$$
https://hmmt-archive.s3.amazonaws.com/tournaments/2014/nov/thm/problems.pdf
$\mathrm{START}\to\mathrm M\to\mathrm E\to\mathrm M\to\cdots$
Luật chính thức: số người còn lại. $T$: dân làng; $G$: côn đồ; $W$: thắng; $\mathrm M$: sáng; $\mathrm E$: tối.
$$\begin{gathered}
(T,G)\xrightarrow[T/(T+G)]{\mathrm{M}}(T-1,G),\qquad
(T,G)\xrightarrow[G/(T+G)]{\mathrm{M}}(T,G-1),\\
(T,0)\mapsto W_T\ (T\ge1),\quad(0,G)\mapsto W_G\ (G\ge1),\\
(T,G)\xrightarrow{\mathrm{E}}(T-1,G)\quad(T,G\ge1),\\
\mathrm{E}:\quad G\ge T_{\mathrm{new}}\Longrightarrow W_G,\qquad
W_T,W_G\Longrightarrow\mathrm{STOP}.
\end{gathered}$$
https://hmmt-archive.s3.amazonaws.com/tournaments/2014/nov/thm/problems.pdf
$\mathrm{START}\to\mathrm M\to\mathrm E\to\mathrm M\to\cdots$