While, preparing for competition, found an interesting problem, but absolutely don't know how to start.
$600$ natural numbers from $1$ to $600$ are written in a string(each once) in a certain order, such that the sum of any two adjacent numbers does not exceed $800$.
Prove that in a such string some $2$ numbers that have $1$ number between them, when summed give a number bigger than $800$.
(
for example: in string $400$ $6$ $600$ $1$ $3$ $4$ ....
such numbers are $400$ and $600$
)
Tried some simple ideas, but have not succeeded. Maybe a certain math theorem, which i don't know should be used.
If you have a solution, please additionally show me how you came up with it, what was your thought process, becase I really want to learn solving such problems by myself.
Thanks for your answers!
1 Answer
Thought process: maybe instead of thinking about pairs of numbers adding to more than 800, I can just think about individual numbers exceeding 400 and look for two of them close together. Thinking about individual numbers is easier to me than pairs.
Solution: Divide the string into 200 non-overlapping substrings of length 3. There are 201 numbers in the range $\{400,401,\dots,600\}$; by the pigeonhole principle, two of those numbers must be in the same length-3 substring. Their sum is greater than 800, and they can't be next to each other by assumption. Therefore they have to have exactly one number between them.