Proof by contradiction: Integers randomly ordered on rim of a disk

725 Views Asked by At

(I want to see whether this is a valid proof. It came up in the context of a book chapter on induction. I couldn't prove it using induction but found another way instead, which I'd like to check)

Problem: All integers from 1 through 30 are painted in random order in the shape of a circle. We have to show that no matter what the order is, there must be three successive integers whose sum is at least 45.

Proof: Let us consider all of the possible sums of three successive integers. Starting at some arbitrary integer $i_1$ along the circle and moving clockwise where the second integer is $i_2$, the third $i_3$ etc...the first sum of three successive integers is $i_1 + i_2 + i_3$. The second sum is $i_2 + i_3 + i_4$, the third sum $i_3 + i_4 + i_5$, etc...for a total of $30$ sums.

Each integer along the circle will appear in $3$ of the $30$ sums of $3$ successive integers, meaning that the total of those $30$ sums of $3$ successive integers will be $3$ times the sum of the integers from $1$ through $30$, or $3 \cdot \frac{30 (31)}{2} = 1395$.

Now let's assume that none of the $30$ sums of $3$ successive integers is $\geq 45$; then the maximum total sum of those $30$ sums would be $30 \cdot 44 = 1320$. But we know that the total sum of those $30$ sums of $3$ successive integers is $1395$, which means that the assumption that none of the sums is $\geq 45$ is wrong, and that at least one of the sums has to be $\geq 45$.

2

There are 2 best solutions below

2
On BEST ANSWER

Your reasoning is correct, but you need not rely on proof by contradiction: You have shown that the average of $30$ quantities is $46.5$. Then you could simply use the fact that at least one quantity in any set must be at least the average of the quantities in the set.

3
On

Your proof seems right to me. If you do a similar reasoning, you can prove at least one sum is below $47$:

Assume no sum is either below $47$. Then those $30$ sums would add up to, at least, $1410 = 47\cdot30$, when we know the total sum is $1395$.