Olympiad Maths Prep

Track / Stage 6 / 47 of 400 #1047 of 2000

Problem 1047

National olympiad, first round
Combinatorics Difficulty 6.0 Find the answer ToT

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

[b](a) k=9k=9?[/b]
[b](b) k=8k=8?[/b]

Official 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}}

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.