MathDB

A rook stands in one cell of an infinite square grid. A different cell was colored blue and mines were placed in

n

additional cells: the rook cannot stand on or pass through them. It is known that the rook can reach the blue cell in finitely many moves. Can it do so (for every

n

and such a choice of mines, starting point, and blue cell) in at most (a)

1.99n+100

moves? (b)

2n-2\sqrt{3n}+100

moves?
Remark. In each move, the rook goes in a vertical or horizontal line.

Problem Statement