2
$\begingroup$

A game is played on a $100\times 100$ board between three players, $A$, $B$, and $C$, in this order. Each turn, the player must paint a cell adjacent to (at least) one of the sides of the board. The player cannot paint a cell adjacent to a painted cell, or a cell symmetric to a painted cell with respect to the center of the board. The player who cannot paint loses. Can $B$ and $C$ combine to make $A$ lose?

My thought is that $B$ and $C$ could combine by, supposing there is an $x$- and $y$-axis with the center of the board as the origin, having $B$ paint the cell symmetric to what $A$ painted with respect to the $x$-axis, and similarly for $C$ and the $y$-axis. This would make $A$ lose because $A$ cannot paint the cell symmetric with respect to the origin. But the strategy doesn't work, because if $A$ paints a cell adjacent to an axis, the cell on the other side of the axis adjacent to it cannot be painted.

$\endgroup$
2
  • $\begingroup$ You can regard B and C as one player and make it a two person game. Player BC get to moves when A gets one. This may not be such an advantage because BC has to move twice. You really have a ring of $400$ cells because the middle of the board doesn't matter. $\endgroup$ Mar 29, 2018 at 14:21
  • 1
    $\begingroup$ Not sure if this helps, but you can regard this as a game where players are trying to choose a set of independent vertices on a graph. The initial graph is 3-regular graph consisting of a 400-cycle together with chords joining pairs of opposite vertices. When a player selects a vertex, that vertex and its neighbors are deleted from the graph. This (unanswered) question seems relevant: mathoverflow.net/questions/282095/… $\endgroup$ Mar 29, 2018 at 14:49

1 Answer 1

3
$\begingroup$

Hint: The problem was misleading you by presenting the game on a rectangular board, causing you to look for rectangular symmetries. Really, the game is just being played on a ring of 396 cells, where each cell is adjacent to its neighbors and its opposite. Since 396 is a multiple of 3, this ring has trilateral symmetry, which is more helpful since this is a three player game.

Please have another go using this hint, the solution is rather beautiful and satisfying to find.

$\endgroup$
5
  • $\begingroup$ If B and C are colluding, isn't it a two player game with one player getting, and required to make, two moves. $\endgroup$ Mar 29, 2018 at 15:51
  • 2
    $\begingroup$ Say we label the cells as $1,2,\dots,396$. If $A$ paints cell $x$, we let $B$ and $C$ paint cells $x+132$ and $x+264$. By symmetry, if $A$'s move is valid, so are $B$ and $C$'s. $\endgroup$
    – user11550
    Mar 29, 2018 at 15:54
  • 1
    $\begingroup$ @user11550 Bravo! :) It seems like you ask a lot of interesting math puzzles, which I am a huge fan of. Can I ask where you are getting these puzzles from? $\endgroup$ Mar 29, 2018 at 16:20
  • 1
    $\begingroup$ @MikeEarnest Sure! They're from the Saint Petersburg math olympiad: pdmi.ras.ru/~olymp/2017/problems.html $\endgroup$
    – user11550
    Mar 29, 2018 at 16:28
  • $\begingroup$ thank you very much, @user11550 ! $\endgroup$ Mar 29, 2018 at 16:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .