NUMGAME - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Author: syco

Editorialist: SUSHANT AGARWAL

DIFFICULTY:

EASY

PREREQUISITES:

Basic Number Theory.You can also browse through the chapter “Games” from the book “Mathematical Circles” by Fomin,Genkin,Itenberg for an idea on how to solve simlar problems.

EXPLANATION:

Let us look at small examples first and then try and figure out how to solve the problem.This following table represents Whether you will win or lose if you are on the given number and it is your chance to play.

1)Lose

2)Win

3)Lose

4)Win

5)Lose

6)Win

7)Lose

8)Win

It seems that if N is an Even number then Alice wins otherwise Bob wins.This is indeed True.

Strategy to be followed :- If you are on an Even number,subtract 1 from the number.The opponent will then have an Odd number.All factors of odd numbers are Odd.Hence he can only subtract an Odd number.Hence you will have an even number on your turn.Keep following the same strategy.What will remain “Invariant” is that you will always have an even number and the opponent will have an odd number.This process will keep continuing until you reach one the numbers between 1 and 8,for which the results are listed above.

EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.

2 Likes
2

In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N.
suppose,we take 6,then one can subtract either 2 or 3,depending on that,new no. may be either even or odd.so result will varrie,please clarify.

3 Likes
3

@subhayansrkr

Note “Assuming both play optimally” ie. Both are playing for win.

At N=6, one can subtract 1/2/3, but one will never subtract 2 because he may lose that way. So he has to chose 1/3 to win ( & to have opponent an odd number).

5 Likes