We are required to use contradiction to prove that:
If the numbers $1, 2, …, 20$ are arranged in a circle regardless of order, that there must be $3$ close numbers whose sum is at least $32$.
If we list the numbers, say in a clockwise direction starting at any arbitrary number say, $k_1$ upto $k_{20}$ we look at the total sum as being
\begin{equation*}
\begin{aligned}
(k_1 + k_2 + k_3) + (k_2 + k_3 + k_4) + (k_3 + k_4 + k_5) + … + (k_{19} + k_{20} + k_1) + (k_{20} + k_1 + k_2)
\end{aligned}
\end{equation*}
Here, we realise that every number from 1 to 20 appears atleast 3 times in the above big sum. So the big sum is literally $3(1 + 2 + 3 + … + 20)$
We know however that the total sum of values from $1$ to $20$ can be achieved by using the formula
\begin{equation*}
\begin{aligned}
\sum_{k=1}^{n} k &= \frac{n(n + 1)}{2} \\
&= \frac{20(20 + 1)}{2} \\
&= 210
\end{aligned}
\end{equation*}
Right now am stuck at this point. How to prove that there will be $3$ numbers that have a sum lesser than $32$.
My thinking is that if i join up the three biggest numbers, namely $18 + 19 + 20$, I will end up with $57$. But then how do I prove it with contradiction in this induction question?
Best Answer
I am assuming that by 'three close numbers' you mean a triplet of adjacent numbers in some permutation (following from what you gave in the details of your question).
I am not very sure about where you can use induction effectively here. But if you do look at the problem from a pigeonhole principle point of view, the answer is fairly straightforward and you're actually almost there, you're just looking at the wrong question. What you should try to prove is that there will always be a triplet where the sum is at least 32; of course there have to triplets where the sum is less than 32 as well.
Just notice that the sum you calculated, which equals $210$, appears exactly thrice when you take the sum across all triplets of interest; and there are exactly 20 of these in any rearrangement in a circle as you've already figured out. Then it follows immediately that $$\frac{3}{20}\sum_{i=1}^{20}i=31.5, $$ which implies that if the sums for all triplets of interest were less than 32, they would be at most 31, which gives a contradiction because the sums cannot match; it is strictly less in case this were true.