Proofs of Existence and Optimality · Proofs of Optimality

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

The answer is \(50\). Let's prove this. First, let's show that there exists such a set of fifty cards. It is not difficult to present it: \[50, 51, \dotsc, 98, 99.\] Here, the sum of any two numbers is greater than one hundred.

Now let's show that there does not exist a set of more than fifty cards. Among our ninety cards, there are forty pairs, in each of which the sum is 100: \[(10, 90), (11, 89), \dotsc, (49, 51).\] Thus, from these eighty numbers, it will not be possible to take more than forty numbers. There are still ten numbers left that did not fall into any pairs: \[50, 91, 92, \dotsc, 99.\] It is easy to see that they can always be taken into the hand. Thus, it will be possible to take no more than \(40+10=50\) cards.