Question

[10 pts] Prove that if 51 integers are selected from the first hundred positive integers, (1 100), there must be a pair of these integers with a sum equal to 101. 5.

Answer 1

Step-by-step explanation:

There are 50 pairs of positive integers that total 101:

• 1+100
• 2+99
• 3+98
• ...
• 50+51

One integer can be selected from each pair to create a set of 50 integers in the range [1, 100] such that no two will have a sum of 101. Adding any other integer from the range [1, 100], for a total of 51 integers from that range, will complete one of the sums whose total is 101.

Thus, at most 50 integers can be selected from [1, 100] such that no two will have a sum of 101, but any set of 51 integers from that range must have at least one pair that totals 101.