Here's a puzzle that's been seating in the back of my head for quite a long time.
The game is played on a grid of infinite dimensions; sufficiently large checkered paper. First player specifies the square area of either 4 or 9 cells. He can't choose the same area twice. Second player marks an unmarked cell within this area. If he can't make his move, he loses. What is the minimal amount of turns the first player need to assuredly beat the second player?
I can't think of a good approach here other than randomly sort through various situation in attempt to beat the second player. Any tips and suggestions on how to tackle this problem, what math methods to use, would be greatly appreciated.
Upper Bound Answer
In a $n\times n$ square area, there are $(n-m+1)^2$ square areas of size $m$ and $n^2$ squares of size $1$.
Hence $$n^2<(n-8 )^2+(n-3 )^2$$ implies $$0<n^2-22n+73$$ implies $n\ge 18$ (and also $n\le 4$ but its irrelevant).
So choose all possible squares of size $4$ (there are 225) and $9$ (there are 100) in a square of size $18$ that only have 324 square of size 1, and you will eventually win at move 325 (before if the other player makes mistakes).
So the minimal amout of turns is lower or equal to 325.
I have the feeling that it can't be improved, but I don't have time now to pursue further...
EDIT
for $2\times 2$ and $3\times 3$ cells, you obtain $$n^2<(n-1)^2+(n-2)^2$$ $$0<n^2-6n+5$$
So $n\ge 6$ with the same strategy and you will win at turn 37. As suggested by John Hugues, a strategy on a $6\times 5$ rectangle is enough, and you will win at turn 31. (or a $8\times 4$ rectangle also is enough and you'll win at turn 33.)