0
$\begingroup$

This variant is almost similar to the normal nim game which states -

Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the last non-empty pile is declared as a winner.

The twist is an inclusion of a "pass" move for each non-empty pile. To make myself clear, a player can choose to pass his move on any non-empty pile on which there was no "pass" move made.

I looked up grundy numbers to solve this problem, but I do not how to add the rule of pass move.

For ex:

$G(0) = mex(empty-set) = 0$

$G(1) = mex(G(1),0) = ?$

Heremex(g) is a function which takes a set of non-negative integers and outputs smallest non-negative integer that is not present in the list.

For ex : mex(0,1,2) = 3 and mex(0,2,3) = 1

I just don't know how to proceed. I'd appreciate some help. Also, I'd like to add that the number of piles is small say 10-15 but the number contained in each pile is quite huge. Hence those recursive backtracking type of solutions won't work.

Update : The pass move is not mandatory.

$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "the pass move is not mandatory"? No move is ever mandatory. What is special about the pass move? $\endgroup$ Dec 23, 2016 at 6:25
  • $\begingroup$ This problem appears to be taken from an active programming contests. Is that correct? I consider it polite to acknowledge your sources and reference the original source where you ran across this problem. Also, I'm not sure whether you should be asking us to help you solve the contest problem. $\endgroup$
    – D.W.
    Dec 25, 2016 at 16:08
  • $\begingroup$ @D.W. Yes it is from the contest. I'm sorry. Remove this as it violates the rules. $\endgroup$
    – RogerThat
    Dec 25, 2016 at 17:31
  • $\begingroup$ Once you've received an answer, removing the question would be inappropriate, as it would be disrespectful to the person who spent time answering. You can still edit the question to provide proper attribution for the source of the problem. $\endgroup$
    – D.W.
    Dec 25, 2016 at 20:21

1 Answer 1

1
$\begingroup$

You have to augment each pile with an extra bit which states if it has been passed or not. Then you can compute the Grundy function as usual. For example, here are some values: $$ \DeclareMathOperator{\mex}{mex} \newcommand{\yes}{\text{Yes}} \newcommand{\no}{\text{No}} G() = \mex(\emptyset) = 0 \\ G(1,\yes) = \mex(G()) = \mex(0) = 1 \\ G(1,\no) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\ G(2,\yes) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\ G(2,\no) = \mex(G(),G(1,\yes),G(2,\yes)) = \mex(0,1,2) = 3 $$ Here Yes means that the pile has been passed, and No that it hasn't been passed.

You mention that a recursive solution won't be efficient enough. In that case, I suggest trying to find a formula for the Grundy function. Here is a hint:

A pile which has been passed behaves like a normal pile. A pile which has not been passed behaves like a pile which is one item larger.

$\endgroup$
7
  • $\begingroup$ Thanks a lot for this. I now understand G. Also, pass move is valid only on non-empty pile so - $G(0,NO)$ = 0. Hence this changes $G(1,No) = 2$ and $G(n,Yes) = n$. Thanks again. $\endgroup$
    – RogerThat
    Dec 23, 2016 at 4:41
  • $\begingroup$ Oops, I forgot to mention in the question that the pass move is not mandatory. I guess this changes everything. $\endgroup$
    – RogerThat
    Dec 23, 2016 at 4:45
  • $\begingroup$ @RogerThat In my solution the pass move is also not mandatory! $\endgroup$ Dec 23, 2016 at 6:22
  • $\begingroup$ @YuvalFilmus $G(2,Yes) = mex(G(),G(1,Yes) = mex(0,1) = 2$. Because once that pile is passed it cannot be passed again. (I've mentioned this in the question) $\endgroup$
    – RogerThat
    Dec 23, 2016 at 6:31
  • $\begingroup$ @YuvalFilmus I'm being wrong about the above comment? $\endgroup$
    – RogerThat
    Dec 23, 2016 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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