5
$\begingroup$

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!

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.