In an $m\times n$ rectangular chessboard,there is a stone in the lower leftmost square. Two persons A,B move the stone alternately. In each step one can move the stone upward or rightward any number of squares. The one who moves it into the upper rightmost square wins. Find all $(m,n)$ such that the first person has a winning strategy.
Problem
Source: Lithuania NMO 2010
Tags: combinatorics, Chessboard
11.03.2012 08:59
Define that if a stone has a position $(x,y)$ then it is $x$ more steps upward and $y$ more steps rightward before it reaches the upper-right position. This way, we can imagine the grid to be rotated; it starts on the lattice point $(m-1,n-1)$ and players move it leftward or downward. If the coordinates are the same, then the player to move must make them not equal. If the coordinates are not the same, then the player to move can make them equal. Since $(0,0)$ has equal coordinates, then all $(x,y)$ where $x \neq y$ wins and all $(x,x)$ loses. Hence the first player wins iff $m \neq n$.
16.11.2016 18:12
This is clearly the same as a nim Game with two heaps of sizes $n$ and $m$.
27.10.2017 11:36
good problem
20.11.2017 14:45
This game is equivalent to Nim$(m,n)$.The Grundy Number of $(m,n)$ is $m$ xor $n$. First player wins$\iff$Grundy Number is not $0\iff m$ xor $n \neq 0\iff m\neq n$