Can two player game have two solutions for determining who will won or lose at last?

help
1

Here is link of problem - YouTube

Problem Statement : Lets suppose we have n piles of stone each having stones a[i] 1<=i<=n
.We can play turn by turn and we start at first and in one move we can convert a pile into two non empty piles.consider both player are playing optimally . who will win the game ?

According to @kingofnumbers solution , if biggest number is not of type (2^k)-1 then we will always win else we will lose.

I didn’t get it. Instead i thought a different solution.

Here it is : We will add the sum of all coins and number of piles and now we will check if its even or odd . if its even then first player will lose else will win.

Lets consider sum1 shows sum of all coins of piles.
sum2=sum1+n;

initially number of piles are n . now in one move any player will make two piles out one pile so sum1 willl remain constant while n will increase by 1 thus parity of sum2 is changing in every move.

we know in final state all piles will be of containing 1 coin each. so sum2=sum1+sum1=2*sum1;

so if sum2 is even player who is playing will lose else will won .

can you help me to find what’s wrong in my approach ?

Thanks

2 Likes
2

Is question not clear to anyone ?

1 Like
3

Some game theory problems are too much based on intuition, there is no specific set of rules on how to solve a game theory problem(especially hard ones)(what works at one place, does not work at other place) , that’s why no-one is answering :slight_smile:

4

Okay , I got your point.
But can you share your intuition for this problem ?
How would you solve this, if this appears in any future contest ?

5

My strategy is to only study Nim game+all its variations + the dp-approach, anything other than that, I don’t bang my head on the wall cuz I won’t be able to do it. :slight_smile:
And the good thing is, pick up any contest from last 2 years of Codechef,Codeforces and Hackerrank ,all game-theory problem(s) are based on very basic principles of Nim and no weird logic.
Of-course if you see some weird problem(which is not possible in a contest),its better to just remember the result or just leave it :slight_smile: I’ve solved table-game,buddyNim,BinNim,etc. And all of them required the basic principles and no weird logic/intuition :slight_smile: