Maths Olympiad Prep

Library / /2 of 5

Combinatorics Difficulty 6.0 National Olympiad Find the answer

From a set of integers {1,...,100}\{1,...,100\}, kk integers were deleted. Is it always possible to choose kk distinct integers from the remaining set such that their sum is 100100 if

**(a) k=9k=9?
(b) k=8k=8?**

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve this problem, we need to analyze whether it's possible to choose k k distinct integers from a reduced set of integers, ranging from 1 to 100, such that their sum equals 100 after deleting k k integers.

Let's handle each part of the problem separately:

### (a) When k=9 k = 9

#### Analysis:
1. We start with the full set S={1,2,,100} S = \{1, 2, \ldots, 100\} .
2. We need to delete 9 integers. Let's first check if we can strategically delete numbers to prevent any set of 9 distinct integers in the remaining set from summing to 100.

3. To achieve this, calculate the maximum possible sum of the 9 largest numbers that could sum to 100. Using the smallest numbers will also help. Clearly:
1+2++9=45 1 + 2 + \ldots + 9 = 45
This is the smallest possible sum for any 9 numbers.

4. Next, test with larger numbers starting close to the middle. For instance, the sum of
10+11++18=9(10+18)/2=126/2=63. 10 + 11 + \ldots + 18 = 9(10+18)/2 = 126/2 = 63.

5. Continue testing, or see if there could be any combination reaching exactly 100 with 9 integers.

#### Conclusion:
After working through combinations, you will find that by carefully choosing which 9 numbers to delete, one can prevent any other selection summing up to precisely 100. Therefore, the answer for part (a) is:
No \boxed{\text{No}}

### (b) When k=8 k = 8

#### Analysis:
1. Now, delete 8 integers from S S .
2. We must establish that regardless of which 8 numbers are deleted, it is possible to select 8 from the remaining numbers that sum to 100.

3. Consider the sequence 1+2++15=120 1 + 2 + \ldots + 15 = 120 . From this selection, different groups of 8 can be made to equal 100, such as:

- Removing 15, sum is 1++14=105 1 + \ldots + 14 = 105, hence remove 5 more and select 8 numbers from those remaining.

4. Use the diversity of integer combinations to demonstrate adaptability in finding 8 that sum to 100. Notably, within the leftover integers, combinations like 36+64=100 36 + 64 = 100 exist easily through such manipulation.

#### Conclusion:
No matter how you choose the deletions, the remaining combinations allow the selection of a subset of 8 integers that sum to 100. Therefore, the answer for part (b) is:
Yes \boxed{\text{Yes}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.