# Mathematical Induction

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.

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)$.

Last edited: