Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn.
In a turn :
- A player selects one of the integers, divides it by $2, 3, 4, 5$ or $6$, and then takes the floor to make it an integer again.
- If the integer becomes 0, it is erased from the board.
- The player who makes the last move wins.
Assuming both play optimally, we need to predict who wins the game.
Example : Let N=2 and numbers are [3,4] then alice is going to win this one.
Explanation :
Alice can win by selecting 4 and then dividing it by 2. The integers on the board are now [3,2]. Bob can make any choice, but Alice will always win.
- Bob can divide 2 by 3, 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 3, and Alice can just divide it by 6 to finish, and win, the game.
- Bob can divide 3 by 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 2, and Alice can just divide it by 6 to finish, and win, the game.
- Bob can divide 2 by 2. Now the integers are [1,3]. Alice can respond by dividing 3 by 3. The integers are now [1,1]. Now Bob has no choice but to divide 1 by 2, 3, 4, 5 or 6 and remove it (because it becomes 0). Alice can respond by dividing the remaining 1 by 2 to finish, and win, the game.
- Bob can divide 3 by 2 or 3. Now the integers are [1,2]. Alice can respond by dividing 2 by 2. The integers are now [1,1]. This leads to a situation as in the previous case and Alice wins.