Explanation Given information: a game of nim Proof: We prove this by strong induction. For the basis step, when n = 2 stones are in each pile, the first player isup a creek. If she takes two stones from a pile, then the second player takes one stone from the remaining pileand wins. If she takes one stone from a pile, then the second player takes two stones from the other pile andagain wins. Assume the inductive hypothesis that the second player can always win if the game starts withtwo piles of j stones for all j between 2 and k, inclusive, where k ≥ 2, and consider a game with two pilescontaining k + 1 stones each. If the first player takes all the stones from one of the piles, then the secondplayer takes all but one stone from the remaining pile and wins

8th Edition

ISBN: 9781264309689

Author: ROSEN

Publisher: MCG

See similar textbooks

Videos

Question

Chapter 11.2, Problem 39E

To determine

To prove:

If a game of nim begins with two piles containingthe same number of stones, as long as this number is atleast two, then the second player wins when both playersfollow optimal strategies.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 11.2, Problem 38E

Chapter 11.2, Problem 40E

Students have asked these similar questions

Question 2: Let A(G) be the set of all automorphisms of a group G. Prove that if G is a group having only two elements, then A(G) consists only of I. JL

Q Let E be a subset of a spacex thens - prove that: i) E≤ E 2) Eclosed iff E'SE 3 E = EVE' = E° Ud (E).

Question 4: Let G be a finite abelian group of order o(G) and suppose the integer n is relatively prime to o(G). Consider the mapping : G→G defined by (y) = y". Prove that this mapping is an automorphism.

Chapter 11 Solutions

DISCRETE MATHEMATICS LOOSELEAF

Ch. 11.1 - Prob. 1E Ch. 11.1 - Vhich of these graphs are trees?Ch. 11.1 - Prob. 3E Ch. 11.1 - Prob. 4E Ch. 11.1 - Prob. 5E Ch. 11.1 - Prob. 6E Ch. 11.1 - Prob. 7E Ch. 11.1 - Prob. 8E Ch. 11.1 - Prob. 9E Ch. 11.1 - Prob. 10E

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To prove: If a game of nim begins with two piles containingthe same number of stones, as long as this number is atleast two, then the second player wins when both playersfollow optimal strategies.

Solution Summary: The author explains that a game of nim begins with two piles containing the same number of stones, as long as this number is atleast two, and proves this by strong induction.

Videos

To prove: If a game of nim begins with two piles containingthe same number of stones, as long as this number is atleast two, then the second player wins when both playersfollow optimal strategies.

Want to see the full answer?

Chapter 11 Solutions

To prove:

If a game of nim begins with two piles containingthe same number of stones, as long as this number is atleast two, then the second player wins when both playersfollow optimal strategies.