Consider a doubly-ended queue with 1000 elements. Alice and Bob take turns to remove an element from either end of the queue. The player who removes a larger sum wins.
Who wins the game?
This problem appeared in IOI 1996 in Hungary, but it's a well-known puzzle by now.