A problem from the 1999 St. Petersburg City Mathematical Olympiad:
Fifty cards are arranged on a table so that only the uppermost side of each card is visible. Each card bears two numbers, one on each side. The numbers range from 1 to 100, and each number appears exactly once. Vasya must choose any number of cards and flip them over, and then add up the 50 numbers now on top. What’s the highest sum he can be sure to reach?
|
SelectClick for Answer |
The highest number he can be sure to reach is (1/2)(1 + 2 + 3 + … + 100), or 2525. If the visible numbers already meet this total, he should accept them as they are; otherwise he should flip all 50 cards.
This might be the best that he can do. Suppose that the cards show the numbers from 26 to 75 (totaling 2525) and that the k cards he flips over are the first k cards in the sequence 1, 2, …, 25, 76, 77, …, 100. If he flips over fewer than 26 cards his sum will decrease; if he flips more than that, the sum will rise again but will reach 2525 only with the 50th card. Either way, he won’t beat that total.
|
