chocolate breaking game

79 Views Asked by At

This question is based on a high school entry exam many years ago in my country, maybe it's famous but i didnt found the source.

In the beginning there is a chocolate bar size $m\times n$ on the table, in each step the player will pick a chocolate piece and break them into two smaller piece with integer side length (i.e they can either break into ($m\times a$ and $m\times(n-a)$ bar) or ($n\times b$ and $n\times(m-b)$ bar) with $m,n\in\mathbb{Z}^+, 0<a<n,0<b<m$). Whoever make the first chocolate piece of size $1\times 1$ will lose, find the winner.

I have struggled this problem for quite a while, although the original version is much easier (they given $mn$ are even), when they are both odd, even in the case $m=1$ it is still very difficult I have try this by hand for the first 20 value and find out:

For $m = 1$ and $n<20$ the player who play after will win if and only if $n = 7,11,17$