You and I are going to play a game. We have one million grains of sand in a bag. We take it in turns to remove \(2\), \(3\) or \(5\) grains of sand from the bag. The first person that cannot make a move loses.
Would you go first?
There are \(n\) balls labelled 1 to \(n\). If there are \(m\) boxes labelled 1 to \(m\) containing the \(n\) balls, a legal position is one in which the box containing the ball \(i\) has number at most the number on the box containing the ball \(i+1\), for every \(i\).
There are two types of legal moves: 1. Add a new empty box labelled \(m+1\) and pick a box from box 1 to \(m+1\), say the box \(j\). Move the balls in each box with (box) number at least \(j\) up by one box. 2. Pick a box \(j\), shift the balls in the boxes with (box) number strictly greater than \(j\) down by one box. Then remove the now empty box \(m\).
Prove it is possible to go from an initial position with \(n\) boxes with the ball \(i\) in the box \(i\) to any legal position with \(m\) boxes within \(n+m\) legal moves.
Two players are playing a game with a heap of \(100\) rocks, and they take turns removing rocks from the heap. The rules are the following: the first player takes one rock, the second can take either one or two rocks, then the first player can take one, two or three rocks, then the second can take \(1\), \(2\), \(3\) or \(4\) rocks from the pile and so on. That is, on each turn, the players have one more option for the number of rocks that they can take. The one who takes the last rock wins. Who has the winning strategy?