5
$\begingroup$

There are some piles of numbers. Numbers are divided in 2 groups, A and B. Player x plays with group A and player y plays with group B. x makes the move first. On each step a player chooses a pile and chooses a number of his group and remove all numbers smaller and equal to the number (number of both group A and B) from that piles only.

The person who can't make the move which means he finds no number of his group, loses.

Is that a nim game? What should be the strategy? Who will win?

$\endgroup$
  • $\begingroup$ That depends on what you mean by "can't make a move" and whether or not player X must choose a number in his pile (and similarly for Y). $\endgroup$ – Dennis Meng Nov 3 '13 at 6:01
  • $\begingroup$ every player must choose a number from the piles, and can't make move means he finds no number of his group. Problem description updated. $\endgroup$ – user76797 Nov 3 '13 at 6:06
4
$\begingroup$

It's not a nim game, it's an Hackenbush game (Blue-Red version if $A\cap B=\emptyset$)

Replace each number by a line segment of color red for number from $A$, and blue for $B$. To each pile of number, build a pile of line segment, by decreasing order of number.

For example, if $A$ are even numbers, and $B$ are odd numbers, the pile $[3,4,7,8,10]$ will be replace by ground-red(for 10)-red(for 8)-blue(for 7)-red(4)-blue(3).

Hackenbush games are not nim games. To each finite position can be assigned a dyadic number whose sign will give the player who can win.

EDIT : strategy explained for player x : To each number (from $A$) in each pile, $x$ will assign a value that will be :

  1. $1$ if this the largest number of the pile
  2. $1$ if the next larger number was assigned 1 and is from the same set ($A$ or $B$)
  3. $2^{-n}$ where $n$ is the distance to the closest number with value $1$.

Example : in pile [10,8,7,4,3,1], 10 will have value 1 (by rule 1), 8 value 1 (by rule 2), and 4 value $\frac{1}{4}$ (by rule 3). For player y, 7 will be assigned value $\frac{1}{2}$ (rule 2 does not apply here because the next larger number 8 is not from the same set, so rule 3), 3 value $\frac{1}{8}$, and 1 value $\frac{1}{16}$.

The best strategy is to remove the number of lowest value. (This is not the quickest strategy !)

If you add all values for player x and subtract all values for player y, a positive sum means player x has a winning strategy, negative sum is for player y while a zero sum means second player.

$\endgroup$
  • $\begingroup$ Wikipedia doesn't describe the strategy, there is certainly a mathematical strategy, right? $\endgroup$ – user76797 Nov 3 '13 at 6:24
  • $\begingroup$ I made an edit to explain how to compute the strategy. $\endgroup$ – Xoff Nov 3 '13 at 6:46

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.