DIVGAME - Editorial

PROBLEM LINK:

Practice
Contest

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.

8 Likes

Very nicely written editorial.

Thanks
LoneCoder

I am wondering how did you figure out you only have to consider 2 and 17 as a factor of N? How are they connected?