You are not logged in. Please login at www.codechef.com to post your questions!

×

Game theory simple question : Game of coins

Can anyone explain the approach to this question ? https://www.hackerearth.com/problem/algorithm/game-of-coins/ 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 :)

asked 04 Aug '15, 00:32

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912319
accept rate: 10%


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 :)

link

answered 04 Aug '15, 22:27

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

edited 04 Aug '15, 22:31

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.

link

answered 08 Aug '15, 01:48

manojchef's gravatar image

0★manojchef
1
accept rate: 0%

-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) :P

link

answered 04 Aug '15, 21:16

bradley's gravatar image

3★bradley
6562321
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×138
×84
×65
×32

question asked: 04 Aug '15, 00:32

question was seen: 4,441 times

last updated: 08 Aug '15, 01:48