Discrete Math Problem Solving Assignment


Question Description

On the ﬁrst day of class we introduced the following game. It is played with some number of stacks of red and black checkers. One player plays red, the other plays black; the colors have no relation to who plays ﬁrst (that is decided separately). On your turn, you remove one checker of your color from some stack, along with all the checkers on top of it. You lose if it is your turn and there are no checkers of your color left (so that you have no moves). You win if your opponent loses. Here are two theorems about this game to start you oﬀ; one of them we proved in class.
Theorem 1. If there are only black checkers on the board, and there is at least one of them, then Black wins.
Proof. There are two cases, depending on who starts: Case 1: Red starts. Then Red has no moves, so Red loses. Case 2: Black starts. Then Black can remove any black checker (since there is at least one). And on Red’s turn, Red has no moves, so Red loses.
Theorem 2. If there is only one stack of checkers, then whoever’s color is on the bottom can win.
Proof. Without loss of generality, suppose the checker on the bottom is black. Then there are two cases, depending on who starts: Case 1: Black starts. Then Black can remove the bottom checker. And on Red’s turn, there are no checkers left, so Red loses. Case 2: Red starts. Then there are two further cases: Case 2a: There are no red checkers. Then Red loses immediately. Case 2b: There is at least one red checker. Then Red can remove any such checker, but the bottom checker will still be black. Thus on Black’s turn, Black can remove the bottom checker, leaving Red with no moves as in Case 1.
The goal of this project overall is to understand this game as fully as possible by exploration, make conjectures about who can win it depending on the starting position, and prove them. In Part 1, your initial goal is to discover and prove at least one nontrivial statement about the game. However, if you ﬁnd such a statement quickly, don’t be satisﬁed and rest on your laurels: look for more!
As we discussed in class, a good way to explore and understand something complicated is to investigate simple cases ﬁrst. Here are some suggestions for simple groups of starting positions to try looking at. For each suggestion, who do you think will win? If it depends, then what does it depend on? How can you decide, given a starting position in that group, who will win? If it’s not obvious (and it probably won’t be), try playing a bunch of games in that group with someone else and look for patterns.
(1) Suppose that every stack is either all red or all black.
(2) Suppose there are exactly two stacks.
(3) Suppose every stack has at most two checkers in it.
In each case, if you think you’ve ﬁgured out the answer, test it with more examples to be sure. Then try to prove it (we’ll discuss proofs in class soon enough). Also try to generalize it: for instance, in (1) what if every stack is either all red or all black except for possibly one checker of the opposite color? In (2) what if there are exactly three stacks? Four? In (3) what if every stack has at most three checkers in it? Four? Here’s another idea. Suppose you have two starting positions that you understand fully (that is, you know who has a winning strategy), and you combine them side by side to make a single new starting position. Who wins? If this is still too complicated in general; here are some ways to make it simpler:
(a) Try combining only some particular groups of starting positions, like those described in the two theorems or in the simple groups suggested above. That is, say in case (1) you take two positions in which each stack is either all red or all black, and you put them side by side to make a new position. If you know (based on your answer to (1)) who wins the two input positions, then can you deduce who wins the resulting combined position? What information do you need?
(b) Are there particular situations in which you can always say who wins? For instance, what if both input positions are won by Red? Or if one is won by Red and one by Black? Or if one is won by the second player and one is won by Black? Etc.
(c) Suppose you take some position and combine it with another copy of itself. If you know who wins the input position, can you deduce who wins the combined one?
(d) Similarly, what if you take a position and combine it with its “opposite” (in which all the colors are reversed)?

Tutor Answer

School: UIUC

Please let me know if there is anything needs to be changed or added. I will be also appreciated that you can let me know i...

flag Report DMCA

Top quality work from this tutor! I’ll be back!


Thank you! Reasonably priced given the quality


Brown University

1271 Tutors

California Institute of Technology

2131 Tutors

Carnegie Mellon University

982 Tutors

Columbia University

1256 Tutors

Dartmouth University

2113 Tutors

Emory University

2279 Tutors

Harvard University

599 Tutors

Massachusetts Institute of Technology

2319 Tutors

New York University

1645 Tutors

Notre Dam University

1911 Tutors

Oklahoma University

2122 Tutors

Pennsylvania State University

932 Tutors

Princeton University

1211 Tutors

Stanford University

983 Tutors

University of California

1282 Tutors

Oxford University

123 Tutors

Yale University

2325 Tutors