Question

In: Advanced Math

Alice and Bob are have several piles of chips. On each turn they can either remove...

Alice and Bob are have several piles of chips. On each turn they can either remove 1 or 2 chips from one pile, or split a pile into two nonempty piles. Players take turns and a player that cannot make a move loses. Find the value of the Sprague–Grundy function for positions with one pile made of n chips. (Please do not forget to prove correctness of your asnwer.)

Solutions

Expert Solution

Nim is a combinatorial game, where two players alternately take turns in taking objects from several heaps. The only rule is that each player must take at least one object on their turn, but they may take more than one object in a single turn, as long as they all come from the same heap.

Nim is the most well-known example of an impartial game, a game where both players have the same moves all the time, and thus the only distinguishing feature is that one player goes first. It is also completely solved, in the sense that the exact strategy has been found for any starting configuration.

Rules

The basic Nim begins with two players and several heaps, each containing several objects. Occasionally, heaps are also called piles, and the objects are called stones.

Each player, in turn, must take at least one stone, but they may take more than one stone as long as they all come from the same pile. It's allowed to make a pile empty, effectively removing the pile out of the game. When a player is unable to move, the game ends. Naturally, as long as there is a stone, either player can take that stone, and thus can move. So the ending condition can be rephrased, where the game ends if there is no stone left.

In normal Nim, the loser is the player unable to move. It is called normal condition by convention from combinatorial game theory, where a normal game gives the win to the last player making a move. In misère Nim, the player unable to move wins instead; this is equivalent to the player taking the last stone losing.

Example Game

Consider the following example of the game. There are three piles, initially having 3, 4, 53,4,5 stones respectively. Alice and Bob are playing, with Alice starting.

In normal play, Alice wins, as Alice has taken the last stone and thus leaving Bob with no move. In misère play, Alice would lose instead, but in this case Alice would have taken 2 stones from Pile 3 on move 7, leaving Bob with pile sizes 0, 1, 0 and thus forcing Bob to take the last object.

In the above game, Alice has played a perfect game, never letting Bob to be able to snatch the win. This can be generalized into a general strategy.

Strategy

  • f the suggested move makes the pile have 1 stone left, make it have 0 stones instead, or
  • If the suggested move makes the pile have 0 stones left, make it have 1 stone instead.

In other words, the correct move is to leave an odd number of piles of size 1. (In normal play, there should be an even number of piles of size 1 instead, to make the nim-sum zero.)

Proof of Winning Strategy

The following proof is for normal Nim's strategy, given by C. Bouton.

theorem:

The moving player wins in normal Nim if and only if the nim-sum of the pile sizes is not zero.


Related Solutions

Piles can be fabricated from several different materials. Compare timber piles to concrete piles, listing the...
Piles can be fabricated from several different materials. Compare timber piles to concrete piles, listing the advantages of each material.
:) Alice and Bob play the following game: in each round, Alice first rolls a single...
:) Alice and Bob play the following game: in each round, Alice first rolls a single standard fair die. Bob then rolls a single standard fair die. If the difference between Bob’s roll and Alice's roll is at most one, Bob wins the round. Otherwise, Alice wins the round. (a) (5 points) What is the probability that Bob wins a single round? (b) (7 points) Alice and Bob play until one of them wins three rounds. The first player to...
Alice and Bob are playing a game in which each of them has three strategies, A,...
Alice and Bob are playing a game in which each of them has three strategies, A, B, or C. If their choices do not match (e.g., if Alice picks B and Bob picks C), then no money is exchanged; otherwise Alice pays Bob $6 (if they both choose A), or $3 (if they both choose B), or $1 (if they both choose C). Is this a zero-sum game? Find a mixed-strategy Nash equilibrium for it. Is this the only equilibrium...
Alice and Bob bet 50 dollars with each other in a game in which their friend...
Alice and Bob bet 50 dollars with each other in a game in which their friend Charlie tosses a two-sided coin 3 times in a remote location. If Alice correctly predicts the majority face (i.e. the face which occurred the most often in the three tosses), she gets to keep Bob's money as well. Charlie calls them and lets them know that at least 1 heads has occurred.a) Assuming that the coin was fair, what is the probability that the...
Suppose Alice and Bob have RSA public keys in a file on a server. They communicate...
Suppose Alice and Bob have RSA public keys in a file on a server. They communicate regularly, using authenticated, confidential message. Eve wants to read the messages but is unable to crack the RSA private keys of Alice and Bob. However, she is able to break into the server and alter the file containing Alice’s and Bob’s public keys. (1) How should Eve alter the file to so that she can read confidential messages sent between Alice and Bob, and...
Four witnesses, Alice, Bob, Carol, and Dave, at a trial each tell the truth with probability...
Four witnesses, Alice, Bob, Carol, and Dave, at a trial each tell the truth with probability 1/3 independent of each other. In their testimonies, Alice claimed that Bob denied that Carol declared that Dave lied. What is the conditional probability that Dave told the truth?
in c++ please In this program you are going to have several files to turn in...
in c++ please In this program you are going to have several files to turn in (NOT JUST ONE!!) hangman.h – this is your header file – I will give you a partially complete header file to start with. hangman.cpp – this is your source file that contains your main function functions.cpp – this is your source file that contains all your other functions wordBank.txt – this is the file with words for the game to use.  You should put 10...
Suppose that tortilla chips and potato chips are substitutes goods for each other. Which of the following can cause the demand for potato chips to fall?
Suppose that tortilla chips and potato chips are substitutes goods for each other. Which of the following can cause the demand for potato chips to fall?a.if potato chips are a normal good, a fall in consumers’ incomesb.if potato chips are a normal good, a rise in consumers’ incomesc.if potato chips are an inferior good, a fall in consumers’ incomesd.none of the abov
we have encountered several firms that have either failed or came close to collapsing during the...
we have encountered several firms that have either failed or came close to collapsing during the Financial Crisis of 2007-2009 (e.g., Bear Stearns, Lehman, AIG, Fannie Mae…). Select one of these firms and write : Describe in some detail the events that led to the failure of the firm. What went wrong? Describe the interconnectedness of the firm, and how that may have played a role in the US government’s response to its pending failure.
I have this matlab program, and need to turn it into a C++ program. Can anyone...
I have this matlab program, and need to turn it into a C++ program. Can anyone help me with this? % Prompt the user for the values x and y x = input ('Enter the x coefficient: '); y = input ('Enter the y coefficient: '); % Calculate the function f(x,y) based upon % the signs of x and y. if x >= 0    if y >= 0        fun = x + y;    else        fun = x + y^2;    end...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT