Description
This problem is from my Discrete Mathematics Course.
In the game of gumdrops, two players are on alternative turns with Player 1 going first. The player has to choose any gumdrop on a grid with arbitrary width and length on each turn. The player then eats the gumdrop as well as all gumdrops above and to the right of it. The player who is forced to eat the poisoned lower-left corner one loses.
Statement
Player 1 has a winning strategy.
Proof
Let’s say this is a M x N grid, and each player chooses a gumdrop with a position (i, j). Also, we suppose the two players are extremely smart, and they know exactly if they can win in a particular scenario(any state of the game board). Since there is no tie, then either player one or player two has a winning strategy.
Prove it by Contradiction:
Assume player two has the winning strategy, then whatever player one moves, player two can perform an action that leads him/her to win. That is if player one picks the top right corner, player two has a winning strategy by selecting another gumdrop positioned at (i, j) to win the game. However, if picking (i, j) can lead player two to win, player one would have known it and can pick (i, j) in the first place instead of choosing the upper right corner to win the game. As a result, there is a contradiction, and player one is the one who has a winning strategy.
As a result, there is a contradiction and player one is the one who has a winning strategy.
Conclusion
This is called a Strategy-stealing Argument where in some games, Player 1 can steal the strategy which Player 2 may do to win. (since they are all “genius”)
What do you think of this problem or the proof? Do you accept it, or do you have other proofs? Leave in the comments below!
What do you think of this problem or the proof? Do you accept it or do you have other proofs? Leave in the comments below!