Suppose you have 50 coins—a mixture of pennies, nickels, dimes, and quarters—arranged in a line on a tabletop. You choose a coin from one of the ends and put it in your pocket. Your opponent then chooses a coin from one of the ends of the line of remaining coins. You and your opponent take turns removing a coin in this manner until your opponent takes the last one. The player with the larger amount of money wins.
Peter Winkler of Dartmouth College describes it as "the simplest game in the world." There are just two players. There's no chance involved. There's no hidden information; everyone sees what's going on. There are at most two options per move.
In this coin game, it's possible to prove that, starting with an even number of coins of any denomination, the first player can always guarantee getting at least as much as the other player.
How? With 50 coins, label the coins from 1 to 50. Add up the values of all the odd-numbered coins. Separately, add