4 A game Alice and Bob are playing a game with n piles of marbles. The pile i ha

Question

4 A game

Alice and Bob are playing a game with n piles of marbles. The pile i has ni marbles. Here is the rule. Alice and Bob will take turns (Alice being the rst); each time, a player needs to rst pick a pile and then take any number of remaining marbles in that pile. Note this player must take at least one marble. Whoever takes the last marble wins the game. As an example, consider there are three piles A;B and C with 3, 4 and 5 marbles respectively. Alice can win as follows. Alice takes 2 from A. Suppose Bob takes 1 from A. Then Alice takes 1 from C. Suppose Bob takes 2 from B. Then Alice takes 2 from C. Bob takes 2 from B. Alice then wins by taking 2 from C. Try to play with this example to convince yourself that Bob cannot prevent Alice from winning the game in this example. Suppose Alice and Bob are both smart and will play using the optimal strategy. Now tell me exactly when Alice can win the game. Justify your answer.

Explanation / Answer

First of all lets simplify the steps mentioned in above question:

Alice is starting the game

Further try:

Let Bob start first:

Further it is given that both are smart and use optimal strategy then we can conclude ths Nim Sum game as:

“If both A and B play optimally (i.e- they don’t make any mistakes), then the player starting first is guaranteed to win if the Nim-Sum at the beginning of the game is non-zero. Otherwise, if the Nim-Sum evaluates to zero, then player A will lose definitely.”

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.