1. The Carnival Coin Game: You are running a game booth at your local village carnival. In your game you lay out an array of coins on a table. You and your customer alternate turns. During a turn, the player must either pick up one coin or pick up two. The player forced to pick up the last coin loses. Your task is to design a strategy (loop invariant algorithm) that ensures that you always win. You get to choose the number n of coins to start with. Part of your strategy is to specify a precondition on n. (Don't answer n = 1 as you need to allow forn to be chosen from an infinite set of possible values.) You graciously allow (require) your customer to go first. Each round (step) starts with the customer picking up either 1 or 2 coins. Your strategy must specify how you in turn respond to what he does. As a hint, here are a few possibilities for you to consider. (a) You pick up the same number as him, i.e. if he picks up one, then you pick up one too. Same for two (b) You pick up the opposite number as him, i.e. if he picks up one, then you pick up two and visa versa. (c) Or maybe you have some fancier strategy depending on the number of coins left. The post condition is "I win because the number of coins left is i = 1 and it is the customer's turn." Many students are tempted to have part of the exit condition be this same "; = 1". I, however, never like having the post and the exit conditions being the same, because then instead of needing to prove the post condition is eventually true, you need to prove the exit condition is eventually true. Instead. I like an exit condition that is CLEARLY reached if enough progress is made. If the number left is say i = 10, then you don't exit. What do you do if i is 2 or 3? Maybe we should exit the loop and move to the code after the loop. So lets make the exit condition be something like i 0. Take care when maintaining the loop invariant that this condition is also maintained. Here is a NEW problem that you might want to try. In the previous game, each player is allowed only to take one or two coins. I had a version of this game in a plastic board with marbles in which you must take one, two or three. It had a mechanical Al that played the winning strategy. What strategy do you play if each turn the player must take one, two, three, four, or five? 1 1. The Carnival Coin Game: You are running a game booth at your local village carnival. In your game you lay out an array of coins on a table. You and your customer alternate turns. During a turn, the player must either pick up one coin or pick up two. The player forced to pick up the last coin loses. Your task is to design a strategy (loop invariant algorithm) that ensures that you always win. You get to choose the number n of coins to start with. Part of your strategy is to specify a precondition on n. (Don't answer n = 1 as you need to allow forn to be chosen from an infinite set of possible values.) You graciously allow (require) your customer to go first. Each round (step) starts with the customer picking up either 1 or 2 coins. Your strategy must specify how you in turn respond to what he does. As a hint, here are a few possibilities for you to consider. (a) You pick up the same number as him, i.e. if he picks up one, then you pick up one too. Same for two (b) You pick up the opposite number as him, i.e. if he picks up one, then you pick up two and visa versa. (c) Or maybe you have some fancier strategy depending on the number of coins left. The post condition is "I win because the number of coins left is i = 1 and it is the customer's turn." Many students are tempted to have part of the exit condition be this same "; = 1". I, however, never like having the post and the exit conditions being the same, because then instead of needing to prove the post condition is eventually true, you need to prove the exit condition is eventually true. Instead. I like an exit condition that is CLEARLY reached if enough progress is made. If the number left is say i = 10, then you don't exit. What do you do if i is 2 or 3? Maybe we should exit the loop and move to the code after the loop. So lets make the exit condition be something like i 0. Take care when maintaining the loop invariant that this condition is also maintained. Here is a NEW problem that you might want to try. In the previous game, each player is allowed only to take one or two coins. I had a version of this game in a plastic board with marbles in which you must take one, two or three. It had a mechanical Al that played the winning strategy. What strategy do you play if each turn the player must take one, two, three, four, or five? 1