Maths Olympiad Prep

Track / Stage 6 / 340 of 400 #1340 of 1964

Problem 1340

National olympiad, first round
Combinatorics Difficulty 6.7 Find the answer

If there are several heaps of stones on the table, it is said that there are many\textit{many} stones on the table, if we can find 5050 piles and number them with the numbers from 11 to 5050 so that the first pile contains at least one stone, the second - at least two stones,..., the 5050-th has at least 5050 stones. Let the table be initially contain 100100 piles of 100100 stones each. Find the largest n10000n \leq 10 000 such that after removing any nn stones, there will still be many\textit{many} stones left on the table.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

1. Initial Setup:
- We start with 100 piles of 100 stones each.
- We need to find the largest n10,000 n \leq 10,000 such that after removing any n n stones, there will still be 50 piles numbered from 1 to 50, where the i i -th pile has at least i i stones.

2. Part 1:
- We can remove 5100 stones in such a way that the condition is not satisfied.
- Specifically, if we remove 51 stones from each pile, we will have removed 51×100=5100 51 \times 100 = 5100 stones.
- After this removal, each pile will have 10051=49 100 - 51 = 49 stones.
- Since the 50th pile needs at least 50 stones, the condition is not satisfied.

3. Part 2:
- We need to show that if we remove 5099 stones, the condition is always satisfied.
- Suppose we remove ki k_i stones from the i i -th pile, with k1k2k100 k_1 \geq k_2 \geq \ldots \geq k_{100} .
- We claim that ki150i k_i \leq 150 - i for all i{51,52,,100} i \in \{51, 52, \ldots, 100\} .

4. Proof of the Claim:
- Assume there exists an i{51,,100} i \in \{51, \ldots, 100\} such that ki151i k_i \geq 151 - i .
- Then, we have:
5099=k1+k2++k100k1+k2++kiikii(151i) 5099 = k_1 + k_2 + \ldots + k_{100} \geq k_1 + k_2 + \ldots + k_i \geq i \cdot k_i \geq i \cdot (151 - i)
- We need to show that i(151i)5100 i \cdot (151 - i) \geq 5100 leads to a contradiction.
- Consider the function f(i)=i(151i) f(i) = i \cdot (151 - i) :
f(i)=151ii2 f(i) = 151i - i^2
- This is a quadratic function opening downwards with a maximum at i=151275.5 i = \frac{151}{2} \approx 75.5 .
- Evaluating f(i) f(i) at the boundaries i=51 i = 51 and i=100 i = 100 :
f(51)=51(15151)=51100=5100 f(51) = 51 \cdot (151 - 51) = 51 \cdot 100 = 5100
f(100)=100(151100)=10051=5100 f(100) = 100 \cdot (151 - 100) = 100 \cdot 51 = 5100
- Since f(i)5100 f(i) \leq 5100 for 51i100 51 \leq i \leq 100 , the assumption ki151i k_i \geq 151 - i leads to 50995100 5099 \geq 5100 , which is a contradiction.
- Therefore, ki150i k_i \leq 150 - i for all i{51,52,,100} i \in \{51, 52, \ldots, 100\} .

5. Verification:
- After removing ki k_i stones, each pile i i has 100ki 100 - k_i stones left.
- For i{51,52,,100} i \in \{51, 52, \ldots, 100\} :
100ki100(150i)=i50 100 - k_i \geq 100 - (150 - i) = i - 50
- Thus, the 51st pile has at least 1 stone, the 52nd pile has at least 2 stones, ..., and the 100th pile has at least 50 stones.

Conclusion:
5099 \boxed{5099}

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