Discrete Math Problem Solving Assignment

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!(over?)1As 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)?