Let $a,b$ be positive even integers. A rectangle with side lengths $a$ and $b$ is split into $a \cdot b$ unit squares. Anja and Bernd take turns and in each turn they color a square that is made of those unit squares. The person that can't color anymore, loses. Anja starts. Find all pairs $(a,b)$, such that she can win for sure. Extension: Solve the problem for positive integers $a,b$ that don't necessarily have to be even. Note: The extension actually was proposed at first. But since this is a homework competition that goes over three months and some cases were weird, the problem was changed to even integers.
Problem
Source: Bundeswettbewerb Mathematik 2015 - Round 2 - #1
Tags: geometry, rectangle, combinatorics
AdithyaBhaskar
05.09.2015 09:15
My solution: It is, in fact, easy to show that for all $2 |a,b$, Anja has a winning strategy. Let, w.l.o.g, $a \leq b = a + 2x$. Then Anja colors the $a \times a$ square such that we have two $a \times x$ squares on its sides. Then whatever Bernd plays, Anja just plays its mirror image: and thus wins . In fact, for all pairs $(a,b)$ of the same parity, Anja wins.
Tintarn
05.09.2015 16:55
First Remark: The strategy if $a<b$ and $a$ is odd, $b$ is even is similar to the one of AdithyaBhaskar: If $a=1$ then clearly Bernd always wins independent of both the strategies. Assume $a=2x+1, b=2(x+y)$ with $x,y \ge 1$. Then Anna can win by first coloring a $2x \times 2x$ square such that one both sides there remains a $2y \times b$-rectangle and additionally we have a $1 \times 2x$ corridor at one of the sides of the colored square. Whatever Bernd does, Anna can color the mirror image and thus wins. Second Remark: The interesting case of the extension seems to be the part where $a<b$ and $a$ is even while $b$ is odd. In fact, it seems like Anna can always win but there is no simple universal strategy (or at least, I didn't find one...). For $b=a+1$ it is of course very simple for Anna to win by first coloring one $a \times a$-square. I can also give a strategy for the cases $2 \times 5$ and $2 \times 7$ but these are not really nice and include some casework.