0
$\begingroup$

2 players 'A' and 'B' are playing a game. A piles of Stone has n stones.Player can remove either one stone or stone equal to power of some prime number. The player who can not make a move in his turn loses.

'A' plays first. Both 'A' and 'B' play optimally, who will win the game?

I am new to such kind of problems, I tried making all possible situations, but i am unable to solve this problem. Any help will be appreciated.

$\endgroup$
  • $\begingroup$ I would question whether or not it's correct to say they both play "optimally" if one definitely loses. It seems to me that either going first you are always able to win or going second you are always able to win. Thus they do not both have to play optimally, only the one that is assured a win (assuming, of course, that player plays optimally). $\endgroup$ – Jared Jun 8 '16 at 1:51
  • $\begingroup$ Yes, that is true, i also think that the first person decides who wins. @Jared. But what will be those conditions? $\endgroup$ – shahrukh Jun 8 '16 at 1:59
  • 2
    $\begingroup$ I think it's perfectly standard to say that both players play optimally. For the game to be a certain win for one player, that player needs to be able to win against optimal play by the other. Furthermore, whether it's a first-player win or a second-player win depends upon the value of $n$. $\endgroup$ – Greg Martin Jun 8 '16 at 2:26
  • $\begingroup$ Don't answer this question, it is from a live competition. codechef.com/JUNE16/problems/CHCOINSG $\endgroup$ – lulu Jun 9 '16 at 11:41
  • $\begingroup$ Your other question was also from the codechef competition. $\endgroup$ – lulu Jun 9 '16 at 11:44
3
$\begingroup$

HINT: Clearly A wins if $1\le n\le 5$, and B wins if $n=6$. Show that in general, if $n$ is not a multiple of $6$, then A can take stones so as to leave a multiple of $6$. Show further that if $n$ is a multiple of $6$, then A cannot move so as to leave a multiple of $6$.

Put these facts together properly, and you'll know exactly which $n$ are wins for A and which are wins for B, and also what the winning strategy is.

$\endgroup$
1
$\begingroup$

This, like any impartial perfect information game, is Nim in disguise. You need to find the Nim-value of piles of $n$ stones. $1$ and any prime power are $*1$ because you can take all the stones and move to $0$. Then $6$ is $0$ as it loses. Look up the Sprague-Grundy theorem.

$\endgroup$
  • $\begingroup$ $4$ is a prime power, so it's also a winning position. $6$ is the first losing position. Only a small detail, I know. $\endgroup$ – Greg Martin Jun 8 '16 at 2:27
  • $\begingroup$ @Martin: I forgot you could take prime powers when writing. Thanks $\endgroup$ – Ross Millikan Jun 8 '16 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.