If there are several heaps of stones on the table, it is said that there are $\textit{many}$ stones on the table, if we can find $50$ piles and number them with the numbers from $1$ to $50$ so that the first pile contains at least one stone, the second - at least two stones,..., the $50$-th has at least $50$ stones. Let the table be initially contain $100$ piles of $100$ stones each. Find the largest $n \leq 10 000$ such that after removing any $n$ stones, there will still be $\textit{many}$ stones left on the table.
Problem
Source: All-Russian MO 2023 Final stage 9.5
Tags: combinatorics
23.04.2023 19:40
Answer is n = 5099 If n = 5100 Let remove 51 stones out from each pile Then each pile has 49 stones left which are not many stones on the table Now consider case n = 5099 Since we removed 5099 stones then there must be 4901 stones left Claim : $\frac{4901-100k}{100-k} > 49-k$ Proof : I’m too lazy. Just expand By pigeonhole : There must be at least 1 pile which contains at least 50 stones WLOG let it be 1th pile Now consider other 99 piles Since number of stones in pile 1th does not exceed 100 Then there must be at least 4801 stones left By pigeonhole : There must be at least 1 pile which contains at least 49 stones Let it be 2th pile By claim we have at least 50 stones in 1th pile at least 49 stones in 2th pile ……… at least 1 stones in 50th pile Which desired our table contains many stones
26.04.2023 20:43
The answer is $n_{{\rm max}}=5099$. We split the proof into two parts: Part 1: We may take $5100$ stones so that the condition of the problem is not satisfied. Indeed, it is enough to take $51$ stones from each pile. Part 2: If we take $5099$ stones, the condition of the problem is always satisfied. Suppose that we take $k_i$ stones from the $i$th pile with $k_1 \geq k_2 \geq \ldots \geq k_{100}$. We then have the following Claim. Claim: $k_i \leq 150-i$, for all $i \in \{51, 52, \ldots, 100 \}$. Proof: Suppose that there existed an $i \in \{51, \ldots, 100 \}$ such that $k_i \geq 151-i$. Then note that $5099=k_1+\ldots+k_{100} \geq k_1+\ldots+k_i \geq ik_i \geq i(151-i) \geq 5100,$ with the last inequality being true as it is equivalent to $(i-51)(i-100) \leq 0,$ which is true since $51 \leq i \leq 100$. Hence, we reach a contradiction and so the claim must be true $\blacksquare$ Back to the claim, $100-k_i$ stones have remained to each pile, and for all $i \in \{51,52, \ldots, 100 \}$ we have $100-k_i \geq 100-(150-i)=i-50,$ therefore the $51$th pile contains at least $1$ stone, the $52$th pile contains at least $2$ stones, and finally the $100$th pile contains at least $50$ stones.
06.01.2024 14:52
We claim that $n=5099$. First, we show that $n\geq5100$ is impossible. Note that if we remove $51$ stones from each pile, then no pile has $50$ stones, so there aren't $many$ stones. We now prove that $5099$ works. After removing $5099$ stones there will be $4901$ stones remaining. Let the number of stones on pile $i$ be $x_i$. We have that $x_1+x_2+\cdots+x_{100}=4901$. WLOG assume $x_1\geq x_2\geq x_3\cdots\geq x_{100}$. Then, $x_1\geq\lceil{\frac{4901}{100}}\rceil=50$. Since $x_1\leq100$, we have $x_2\geq\lceil\frac{4801}{99}\rceil\geq\lceil\frac{4801}{100}\rceil=49$ In general, for $1\leq i\leq 50$, we may write $x_i\geq\lceil\frac{100(50-i)+1}{100}\rceil=51-i$ We are done. $\blacksquare$ Remark: If we replace $50$ with $k$, then $n=2k^2+2k-1$.
07.01.2024 13:29
Same solution as this Pyramix wrote: We claim that $n=5099$. First, we show that $n\geq5100$ is impossible. Note that if we remove $51$ stones from each pile, then no pile has $50$ stones, so there aren't $many$ stones. We now prove that $5099$ works. After removing $5099$ stones there will be $4901$ stones remaining. Let the number of stones on pile $i$ be $x_i$. We have that $x_1+x_2+\cdots+x_{100}=4901$. WLOG assume $x_1\geq x_2\geq x_3\cdots\geq x_{100}$. Then, $x_1\geq\lceil{\frac{4901}{100}}\rceil=50$. Since $x_1\leq100$, we have $x_2\geq\lceil\frac{4801}{99}\rceil\geq\lceil\frac{4801}{100}\rceil=49$ In general, for $1\leq i\leq 50$, we may write $x_i\geq\lceil\frac{100(50-i)+1}{100}\rceil=51-i$ We are done. $\blacksquare$ Remark: If we replace $50$ with $k$, then $n=2k^2+2k-1$. N=5099 works. First observe $N$ $<$ 5100 5100 clearly does not work.