Question

Prove (constructively) that there is a winning strategy for the first player on any n by n board of Gumdrop. If you don't remember the rules of Gumdrop from class, you can refer to the hwl chocolate problem on Blackboard. Hint: The first move is (2, 2). The Chocolate Problem In the game of "Gumdrop", there are n. m gumdrops arranged in an n by m rectangular grid, where n and m are integers > 2. Two players alternate turns, on each turn eating at least one gumdrop. On your turn, you choose a gumdrop of your choice on the grid, at coordinates i, j. You then eat all gumdrops on the grid at coordinates x, y, where x > i and y > j. That is, you eat all gumdrops in the rectangle whose bottom-left coordinates are i, j. The gumdrop at x = 1, y = 1 (the bottom-left gumdrop) is red, and all other gumdrops are green. If you're particularly greedy, you could choose x = 1, y = 1, and eat all the gumdrops. But that would be a bad idea, because whomever eats the red gumdrop loses the game. As you have to eat at least one gumdrop on your turn, you lose if the red gumdrop is the only one left. a) It turns out that whichever player goes first will win if she plays perfectly. Prove it. b) "Gumdrop" is an unsolved game (like Chess, and unlike Tic-Tac-Toe), meaning that no one has figured out the optimal strategy. Explain why this fact does not contradict your answer to part (a).

Answer 1

Answer:

Explanation:

a)

our first step will be at (2,2) so we will only remain with

one row (1,1),(1,2)......(1,n) and

one column (1,1),(2,1),...(n,1).

when the other player choses one of these remaining options then chose symetrically opposite one

choosing one element in a row doesnot eat an element in column and visaversa

that is if he chooses (i,1) you choose (1,i) or if he chooses(1,i) you choose (i,1). in your following steps.

finally he choose (1,2) you choose (2,1) then he remains with (1,1) and he looses

or finally if he choose (2,1) you choose (1,2) then he remains with (1,1) and he looses

so we wins if we start.

b). here in this gumdrop we are fixing where red one is, if it is some where else there might not be an optimal strategy.