, 2018

Problem:

In the game of Connect Four, there are seven vertical columns which have spaces for six tokens. These form a $7 \times 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 $\lfloor 20 \min (P / E, E / P)\rfloor$ points.