We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A Nim game of n buckets and a[1], a[2], ..., a[n] balls in each bucket cannot be simply divided into n Nim games with 1 bucket and a[1], a[2], ..., a[n] balls in each game. It's not correct to simply XOR all the losses/victories of each bucket to determine the winner of the whole game. i.e. Player who "wins" on even numbers of buckets may not lose the whole game.
For example, consider a game with two buckets and [2, 7] balls respectively. Player 1 "wins" on both buckets but doesn't lose the game. He/She should not take one whole bucket and let the opponent take the other. Instead, the player should take 5 balls from the second bucket, leaving a situation of [2, 2] to the opponent and then win the game.
This is found by finding the grundy/nimber numbers (which was explained by other comments below) and XOR-ing them. The first few grundy numbers for range(11) were [0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0]. A situation of [2, 7] balls has grundy numbers of [1, 3] for each bucket, and a grundy number of 1 xor 3 == 2 for the whole game. So the player can remove 5 balls from the second bucket, making the remaining situation to have a grundy number of 0, therefore forcing the opponent to lose the game.
Also try [7, 8]. The situation has a grundy number of 3 xor 4 == 7, which does not exist in the grundy numbers list. But the first player can remove 2 balls from the second bucket to change its grundy number from 4 to 3 and wins the whole game.
[Don't Understand, Need Help] :
Why do the grundy numbers loop? I mean, since {2, 3, 5, 7, 11, 13} is finite and not the whole set of prime numbers, it's expected to see the grundy numbers to loop with a much longer period, not a short one like this (9).
How to find this loop period with code? It's easy to prove that the grundy numbers loop with such a period when you write them down, but not so obvious to let the code to detect it.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Prime Game
You are viewing a single comment's thread. Return to all comments →
[Understood and Could Explain] :
A Nim game of
nbuckets anda[1], a[2], ..., a[n]balls in each bucket cannot be simply divided intonNim games with 1 bucket anda[1], a[2], ..., a[n]balls in each game. It's not correct to simply XOR all the losses/victories of each bucket to determine the winner of the whole game. i.e. Player who "wins" on even numbers of buckets may not lose the whole game.For example, consider a game with two buckets and
[2, 7]balls respectively. Player 1 "wins" on both buckets but doesn't lose the game. He/She should not take one whole bucket and let the opponent take the other. Instead, the player should take 5 balls from the second bucket, leaving a situation of[2, 2]to the opponent and then win the game.This is found by finding the grundy/nimber numbers (which was explained by other comments below) and
XOR-ing them. The first few grundy numbers forrange(11)were[0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0]. A situation of[2, 7]balls has grundy numbers of[1, 3]for each bucket, and a grundy number of1 xor 3 == 2for the whole game. So the player can remove 5 balls from the second bucket, making the remaining situation to have a grundy number of 0, therefore forcing the opponent to lose the game.Also try
[7, 8]. The situation has a grundy number of3 xor 4 == 7, which does not exist in the grundy numbers list. But the first player can remove 2 balls from the second bucket to change its grundy number from 4 to 3 and wins the whole game.[Don't Understand, Need Help] :
{2, 3, 5, 7, 11, 13}is finite and not the whole set of prime numbers, it's expected to see the grundy numbers to loop with a much longer period, not a short one like this (9).