## PROBLEM LINKS

## Author:SRIKANT BADRI

## DIFFICULTY:

SIMPLE

## PROBLEM:

Two players are breaking a chocolate bar of size **N×M** into pieces. A player’s turn consists of choosing one piece and breaking it in two. Which player wins the game?

## EXPLANATION:

This is a classic mathematical exercise. Notice that the number of pieces of chocolate increases by 1 in each player’s turn; initially, there’s only 1 piece and when the game ends, there have to be **NM** pieces (otherwise, there’s still some piece that can be broken). So the outcome of the game only depends on who makes the **NM**-th move - or equivalently, on the parity of **NM**. If **NM** is odd, the first player has to make the **NM**-th move and loses; otherwise, the second player has to make it and loses. Of course, this works in constant time.