HMMT 二月 2018 · 冲刺赛 · 第 36 题

HMMT February 2018 — Guts Round — Problem 36

[ 20 ] In the game of Connect Four, there are seven vertical columns which have spaces for six tokens. These form a 7 × 6 grid of spaces. Two players White and Black move alternately. A player takes a turn by picking a column which is not already full and dropping a token of their color into the lowest unoccupied space in that column. The game ends when there are four consecutive tokens of the same color in a line, either horizontally, vertically, or diagonally. The player who has four tokens in a row of their color wins. Assume two players play this game randomly. Each player, on their turn, picks a random column which is not full and drops a token of their color into that column. This happens until one player wins or all of the columns are filled. Let P be the probability that all of the columns are filled without any player obtaining four tokens in a row of their color. Estimate P . An estimate of E > 0 earns b 20 min( P/E, E/P ) c points.

解析

[ 20 ] In the game of Connect Four, there are seven vertical columns which have spaces for six tokens. These form a 7 × 6 grid of spaces. Two players White and Black move alternately. A player takes a turn by picking a column which is not already full and dropping a token of their color into the lowest unoccupied space in that column. The game ends when there are four consecutive tokens of the same color in a line, either horizontally, vertically, or diagonally. The player who has four tokens in a row of their color wins. Assume two players play this game randomly. Each player, on their turn, picks a random column which is not full and drops a token of their color into that column. This happens until one player wins or all of the columns are filled. Let P be the probability that all of the columns are filled without any player obtaining four tokens in a row of their color. Estimate P . An estimate of E > 0 earns b 20 min( P/E, E/P ) c points. Proposed by: Allen Liu Answer: 0.0025632817