Ana and Beatriz take turns in a game that starts with a square of side $1$ drawn on an infinite grid. Each turn consists of drawing a square that does not overlap with the rectangle already drawn, in such a way that one of its sides is a (complete) side of the figure already drawn. A player wins if she completes a rectangle whose area is a multiple of $5$. If Ana goes first, does either player have a winning strategy?
Problem
Source: CentroAmerican 2013 Problem 4
Tags: geometry, rectangle, combinatorics unsolved, combinatorics
27.08.2013 08:41
If the rectangle at the beginning of one's move has side lengths $a\times b$ then one can move either to the rectangle $a\times(a+b)$ or to the rectangle $(a+b)\times b$. Hence the players essentially move from pair $(a,b)$ to either pair $(a,a+b)$ or $(b,a+b)$. The starting pair is $(1,1)$, and a player wins if $a$ or $b$ is a multiple of $5$. By considering the game states modulo $5$ and by analyzing some cases, one sees that under optimal play of both players the game will cycle infinitely: Ana starts with $(1,2)$ Beatriz cannot move to $(2,3)$, since then Ana's next move wins. Hence Beatriz moves to $(1,3)$. Ana cannot move to $(1,4)$, since then Beatriz's next move wins. Hence Ana moves to $(3,4)$. Beatriz cannot move to $(3,7)\equiv(3,2)$, since then Ana's next move wins. Hence Beatriz moves to $(4,7)\equiv(4,2)$. Ana cannot move to $(4,6)$, since then Beatriz's next move wins. Hence Ana moves to $(2,6)\equiv(2,1)$. We are back at the beginning of the game, and the cycle repeats for ever.
20.01.2021 21:12
fprosk wrote: Ana and Beatriz take turns in a game that starts with a square of side $1$ drawn on an infinite grid. Each turn consists of drawing a square that does not overlap with the rectangle already drawn, in such a way that one of its sides is a (complete) side of the figure already drawn. A player wins if she completes a rectangle whose area is a multiple of $5$. If Ana goes first, does either player have a winning strategy? Take a stage where the area is not a multiple of $5$ and let the next move not be the last one, otherwise the other player would have predicted it and had made a different move. Let this stage be $(a, b)\rightarrow (a, b+a)$ or $(a+b, b)$, then by assumption $5\nmid a, b , (a+b)$. The 4 possibilities for the next move are $\{(a, b+2a), (b+2a, b+a)\}$ or $\{(a+b, a+2b), (a+2b, b)\}$ , but obviously not both cases are "winning" since if $5\mid b+2a$ and $5\mid a+2b$, then $5\mid a+b$ , contradiction. So the players can always prevent each other's win and there's no winning strategy for any of them.