Maker and Breaker are building a wall. Maker has a supply of green cubical building blocks, and Breaker has a supply of red ones, all of the same size. On the ground, a row of $m$ squares has been marked in chalk as place-holders. Maker and Breaker now take turns in placing a block either directly on one of these squares, or on top of another block already in place, in such a way that the height of each column never exceeds $n$. Maker places the first block. Maker bets that he can form a green row, i.e. all $m$ blocks at a certain height are green. Breaker bets that he can prevent Maker from achieving this. Determine all pairs $(m,n)$ of positive integers for which Maker can make sure he wins the bet.
Problem
Source: Baltic Way 2017, Problem 10
Tags: combinatorics, combinatorics proposed, game, Combinatorial games
26.11.2017 19:29
I think all \(mn \equiv 1 \mod 2\) with \(n \geq 3\) work. Or are there more possible values for \(n\)? All I know is that for \(m\) even we can make Breaker pair off the columns and place his blocks on the same height as Maker's in the same pair he put his in. For \(mn\) odd, Maker can make the third row green (just make him put his block on top of Breaker's if Breaker puts a block above the bottom row, and make him put a block in the bottom row otherwise).
26.11.2017 19:32
Well, $m=1$, $n$ arbitrary is another (trivial) solution, but otherwise that's correct.
26.11.2017 19:38
Oh, shucks, I forgot about that. And here I was thinking about how I wouldn't miss the trivial case this time Anyways, I think the algorithm for Breaker goes as follows when \(n\) is even and \(m>1\) is odd: Breaker pairs up the 2nd and third columns, fourth and fifth columns, sixth and seventh columns, and so on. If Maker places a block in one of these columns, then Breaker places his in its pair, and if Maker places a block in the first column then so does Breaker.
27.11.2017 11:39
I think it's better to replace Maker by "Trump Supporter" and Breaker by "Dreamer". Anyway, as the finish from ManuelKahayon strategy for Breaker, here's the strategy for Maker in the case that $m,n\geq 3$ are odd number: Denote the coordinate of each block of the wall by $(x,y)$ where $x\in \{ 1,2,...,m\}$ and $y\in \{ 1,2,...,n\}$. First, he put one green block at $(1,1)$. After that, Maker keeps in mind the following strategic pairings: $$(2i,1)\Leftrightarrow (2i+1,1), (r,s)\Rightarrow (r,s+1)$$for all $i\in \{ 1,2,...,\frac{m-1}{2}\}$ and $r\in \{ 1,2,...,m\} ,n\in \{ 2,3,...,n\}$. Whenever Breaker places red block at one of blocks in the pairs, Maker can places green block at the other. Note that this guarantee that all blocks with coordinates $(x,y)$ with odd $y>1$ will eventually occupied by green blocks (if the game hasn't stop before). So Maker can create a row $y=3$ containing only green blocks, done.