1
$\begingroup$

It’s a two player game. Both the players play optimally. Given n number of stones, a player can choose either 1 stone or p stones or q stones where 1 < p < q. Suppose player 'A' starts the game then determine who will win the game. The Player who picks the last 1 stone or last p stones or last q stones wins the game.

Now, can this be solved using a greedy approach?

EDIT:

So, I have looked at similar problems which suggest that I build some base cases and start generalising from there. For the cases, n = 0, A loses, n = 1, n = p, n = q; A wins. For other cases, the winning and losing depend on the values of p and q.

If p < n < q, then I would see if n - p is even and if n - p < p. If that is the case then we choose to pick p stones else the only choice is to pick up one stone. But if, n - p > p, then I am not able to understand how to make a greedy choice.

Similarly, if n > q. How would I greedily determine my choice? It would be helpful if you can direct me in constructing an algorithm.

$\endgroup$
  • $\begingroup$ What are your thoughts and what have you tried? $\endgroup$ – YiFan Nov 3 '18 at 7:15
  • 1
    $\begingroup$ I have edited the question. I read in some other answer on stackoverflow that in CLRS textbook, it says that a greedy choice cannot be done using the future but rather can depend on the choices that you have made so far. But for a case such as 1 < p < q < n. How would I choose between 1 or p or q? Thanks for the help. I really appreciate it. $\endgroup$ – Sai Somanath Komanduri Nov 3 '18 at 7:48
  • $\begingroup$ The greedy choice is the biggest you can make - choose $q$ if you can, otherwise $p$ otherwise $1$. The question is not so much what is the greedy strategy, but is it any good. My instinct would be to consider parity first (hint: what happens if $p$ and $q$ are both odd?) $\endgroup$ – Mark Bennet Nov 3 '18 at 8:34
  • $\begingroup$ Correct me if I'm wrong. If both p and q were odd and n is even then player A would never win. So the greedy algorithm will check all these conditions to make a choice? $\endgroup$ – Sai Somanath Komanduri Nov 3 '18 at 20:26
  • $\begingroup$ It might be easier to pick a few specific pairs of $p$ and $q$ to see how the strategy works out. Try (say) $p = 3, q = 7$; how does that work out? $\endgroup$ – Brian Tung Nov 3 '18 at 20:32

Your Answer

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

Browse other questions tagged or ask your own question.