# NUMGAME - Editorial

**URL:** <https://discuss.codechef.com/t/numgame-editorial/8671>\
**Category:** editorial\
**Tags:** easy-medium, editorial, game-theory, number-theory\
**Created:** [December 18, 2014, 1:05pm UTC](https://discuss.codechef.com/t/numgame-editorial/8671 "2014-12-18T13:05:56Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![sushant96](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sushant96](https://discuss.codechef.com/u/sushant96)\
**Post date:** [December 18, 2014, 1:05pm UTC](https://discuss.codechef.com/t/numgame-editorial/8671/1 "2014-12-18T13:05:56Z")

</div>

### PROBLEM LINK:

[Practice](http://www.codechef.com/problems/NUMGAME)

**Author:** [syco](http://www.codechef.com/users/syco)

**Editorialist:** [SUSHANT AGARWAL](http://www.codechef.com/users/sushant96)

### 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](http://www.codechef.com/viewsolution/5609854).

---

<div class="post-metadata">

**Author:** ![subhayansrkr](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@subhayansrkr](https://discuss.codechef.com/u/subhayansrkr)\
**Post date:** [January 21, 2016, 9:47pm UTC](https://discuss.codechef.com/t/numgame-editorial/8671/2 "2016-01-21T21:47:32Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![konfused](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@konfused](https://discuss.codechef.com/u/konfused)\
**Post date:** [January 30, 2016, 9:57am UTC](https://discuss.codechef.com/t/numgame-editorial/8671/3 "2016-01-30T09:57:42Z")

</div>

@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).