PROBLEM LINK:
Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Game Theory, Sieve of Erasthosenes
PROBLEM:
Two players are playing a game where they start with an integer N. At each move a player can decrease the integer by 1 or divide it by one of it’s divisor except itself and 1. The players have turns to give one move alternately. The player who cannot make any move ( the integer becomes 1) loses the game. Determine who would win the game if they start with N.
EXPLANATION:
If you are not familiar with “Game theory” problems, read this tutorial before.
The terminal position ( here it is N=1) is a losing position. A position is winning if it is possible to move to a losing position in one move. And a player is in a losing position if he can move to winning positions only.
The simplest way to solve this problem would be to notice the pattern by analyzing all the winning/losing positions between 2 and M (where M is a reasonable value say 10000) with a straightforward DP solution. The pattern is that all prime numbers except 2 and 17 are losing positions. All composite numbers except 16, 34 and 289 are winning positions. So the solution is just to check whether the number is a prime or a composite number.
Proof:
Here are the positions for N up to 15.
N = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
position[] = L W L W L W L W W W L W L W W
When N = 2n where n >= 1:
N = 2, 4 and 8 are winning because 1,3 and 7 are losing positions. But 16 is not winning since {2,4,8,15} are not losing positions. But for all other powers of 2 greater than 16, the player can make a move to 16 and thus winning, so all the other powers of 2 are winning.
When N = 17k where k >= 1:
N = 17 is winning since 16 is losing position.
N = 172 = 289 is losing since {17, 288} are winning positions.
For all other greater powers of 17, the player can make a move to losing position 289 and thus winning the game, so all other powers of 17 are winning.
*When N = 2n 17k where n >= 1 and k >= 1:
The smallest such N = 34 is losing, since {2, 17, 33} are all winning positions.
But for any other multiples of 34, the player can make a move to losing position 34 and thus winning, so any other multiple of 34 would be winning.
When N = Number having at least one prime divisor which is not 2 or 17:
It can be proven that all such prime numbers are losing positions and all such composite numbers are winning. Consider an algorithm similar to Sieve of Erasthoneses:
- Find the smallest number N which is not determined yet whether winning or losing
- Determine the state of that position
- If it is losing then mark all it’s multiples as winning positions.Because then all multiples of N would have a losing divisor N, so those would be winning.
Let’s start with the first number 3 which is losing position (since 2 is winning), so all the multiples of 3 would be winning. The next undetermined number would be the next prime number 5 and that would be losing too and all it’s multiples would be winning. The next undetermined position would always be a prime number( without considering 17) P and that would be losing since the composite number P-1 would be marked losing by one of it’s losing prime divisor. All composite numbers having prime factor other than 2 or 17, would always be winning since it would be marked winning by one of it’s losing prime divisor.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.