Game theory simple question : Game of coins

coins
game
of
theory

#1

Can anyone explain the approach to this question ?


I have tried doing it on pen paper starting with N = 2 upto 10 or so but my solution doesn’t match with theirs. I am not quite comfortable with the fact that alice is always the winner of this game.
Thanks :slight_smile:


#2

Yes from the Problem statement, and from a little Pen-Copy Work, you can see that, Alice is the only winner!

Examples :
N=4
1 2 3 4

Alice removes 2,3 then Bob removes any one of 1 & 4 then Alice removes the left peice and she wins!

N=5

1 2 3 4 5

Alice removes 2,3. Then Bob removes only 1, or both 4 and 5, Alice removes the remaining and she wins!

N=6

1 2 3 4 5 6

Alice removes 2,3, Then either Bob can remove only 1, or (4,5) or (5,6), he will only lose.

The problem meant that, there is always a solution possible in favour of Alice, if both the players play optimally but Alice starts the Game!

So for any N, the winner is Alice

Fastest Algorithm! O(1) :stuck_out_tongue:


#3

Hi Shivam,

lets understand in other way suppose if alice and bob can’t choose two adjacent they are allowed to choose only one coin then what happen alice started game if number of coin are odd then alice will win other wise not because only one coin is allowed to picked up. means analyse it alice always want to make number of coin even because if number of coin will be even then bob choose one and now number of coin again become odd and at last smallest odd number is 1 (one) means alice will choose this one and win the game.

so here same thing is happening when number of coin is odd alice chooses one coin to make it even and when number of coin is even then alice will choose two adjacent coin to make it even (and at last if one coin is left then no problem but when two coin is left adjacent then alice will choose both to make even but now nothing is left to play with and this condition is not possible when bob left even coins and non of them are adjacent).

and when bob tries to make even number of coin (because who left even will be winner) then in next turn alice chooses two coin to make again even. and one thing is also notable that when alice left even number of coin then bob has opportunity to make even but alice will always choose pair such that no adjacent pair left so that this problem will reduce to that problem which i described above means only one coin can be picked up because of no adjacent.

i hope it was not any theoretical or some formula based logic which we have to accept as sweet poison :slight_smile:


#4

since, both are intended to win the game, fortunately alice initialize the game*(in every case)*, and he is getting the profit of. Because of flexible rules(can choose any one or any two consecutive coins), that’s why alice wins every time.