2
$\begingroup$

There are two piles of checkers on a table. A takes any number of checkers from one pile, or the same number from both piles. B does the same. The winner is the last one to take the checker. Positions are pairs $[x(i), y(i)]$ of non-negative integers. By starting with small numbers, find the recursive rule for losing positions, as well as a 'closed expression' for positions in L.

My logic:

x = one pile, y = the other pile.

The first losing position is $[x(0), y(0)]$, which is true because this player with this position is no longer able to take a checker. Likewise, any position with equal amounts of checkers on both tables is a losing position because the opponent is able to take the same number of checkers from both tables, resulting in a loss for his opponent. Positions where one number of checkers is not equal to another is a winning position for the player who moves first.

I'm not sure if that's right or wrong, would appreciate some help w/ this.

Thank you!

$\endgroup$
  • $\begingroup$ Any position with equal nonzero amounts of checkers in both piles is a winning position: take all the checkers from both piles. (In the common parlance, they're in $N$, not in $P$). $\endgroup$ – Steven Stadnicki Oct 2 '14 at 2:18
  • $\begingroup$ Ah, I see. You're right. How would I go about finding the closed expression for positions in L though? I'm thinking of creating a table and trying to find a rule or something. $\endgroup$ – user164403 Oct 2 '14 at 2:24
  • $\begingroup$ After posting a wrong answer (and being corrected) I found the right one, but also that the closed form is well known. Check "Wythoff's game" on Wikipedia. $\endgroup$ – Leen Droogendijk Oct 2 '14 at 15:50
  • $\begingroup$ The closed-form is well-known, but it's tricky to prove - a recursive definition is much easier. (Note that if we take the losing positions as $(x_n,y_n)$ with $x_n\lt y_n$, then $\{x_n\}\cap\{y_n\}=\emptyset$ - this is easy to prove - and $\{x_n\}\cup\{y_n\}=\mathbb{N}$, which is a bit harder.) $\endgroup$ – Steven Stadnicki Oct 2 '14 at 17:45

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.