Mathematical Induction

[dwyane wade]

On the outside rim of a circular disk the integers from 1 through 30 are painted in
random order. Show that no matter what this order is, there must be three successive
integers whose sum is at least 45.

 

[Olinguito]

Hi dwayne wade.

Let the integers be $a_1,a_2,\ldots,a_{30}$ as arranged around the the disc, and let
$$s_1\ =\ a_1+a_2+a_3 \\ s_2\ =\ a_2+a_3+a_4 \\ s_3\ =\ a_3+a_4+a_5 \\ \vdots \\ s_{28}\ =\ a_{28}+a_{29}+a_{30} \\ s_{29}\ =\ a_{29}+a_{30}+a_1 \\ s_{30}\ =\ a_{30}+a_1+a_2.$$
Suppose to the contrary that all the sums are less than 45, i.e. $s_i<45$ for all $i=1,\ldots,30$. Then
$$\sum_{i=1}^{30}s_i\ <\ 30\cdot45\ =\ 1350.$$
But
$$\sum_{i=1}^{30}s_i\ =3(a_1+\cdots+a_{30})\ =\ 3(1+\cdots30)\ =\ 3\cdot\frac{30\cdot31}2\ =\ 1395\ >\ 1350.$$


PS: It can be shown that there must be three adjacent numbers on the disc whose sum is at least $47$. In general, if the integers $1,\ldots,n$ are arrange in a circle, in any order, there must be $r$ adjacent ones whose sum is at least $\frac12r(n+1)$.