{0,1,2,.....9} are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon.Prove there are 3 consecutive vertices whose sum is at least 14.

Question

This is a homework Question and has to do with Pigeonhole principle. Could use a hint.

Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that there are 3 consecutive vertices whose sum is at least 14.

(hint given by Prof: Consider the numbers $S_0=x_0+x_1+x_2,$ $S_1=x_1+x_2+x_3,$ $ ...,$ $S_9=x_9+x_0+x_1$)

I would like to solve it but I don't even have a sense of direction on how to start with this.

Answer 1

HINT: Following the suggestion, let $S_0=x_0+x_1+x_2$, $S_1=x_1+x_2+x_3$, and so on up through $S_9=x_9+x_0+x_1$. The numbers $S_0,\dots,S_9$ are the sums of all ten of the possible sets of three adjacent numbers. Suppose that none of them is $14$ or more, i.e, that $S_k\le 13$ for $k=0,1,\dots,9$. Then

$$S_0+S_1+S_2+\ldots+S_9\le 10\cdot13=130\;.$$

1. What is $S_0+S_1+S_2+\ldots+S_9$ algebraically, i.e., in terms of the numbers $x_0,x_1,\dots,x_9$?
2. What is $x_0+x_1+\ldots+x_9$? In view of (1), what does that tell you about $S_0+\ldots+S_9$?

Answer 2

As an alternative answer to this, let's use Dijkstra's generalization of the pigeonhole principle: for any set or bag (multiset), $\textit{average} \le \textit{maximum}$. (See EWD980, EWD1094; see also section 16.4 in Gries & Schneider, "A Logical Approach to Discrete math".)

For the pigeonhole principle, the key choices are: what are the pigeons, and what are the holes? For Dijkstra's generalization, the key choice is: what is the bag?

In this case we need to prove that there is a "3-sum" (i.e., the sum of the numbers assigned to 3 consecutive vertices) that is at least 14, or in other words, that the maximum 3-sum is at least 14.

---

Proof. The above suggests to look at the bag of all 3-sums, and investigate its average.

To calculate the average we need to know the sum of all 3-sums and the number of 3-sums. Since each vertex occurs in exactly 3 3-sums, the sum of all 3-sums is 3 times the sum of all vertex numbers, or $3 \times (0 + 1 + \dots + 9)$, or 135. The number of 3-sums is obviously 10. Therefore the average 3-sum is 135/10 or 13.5.

Now by the generalized principle ($\textit{average} \le \textit{maximum}$) it follows that the maximum 3-sum is at least 13.5. And since all 3-sums are integers (since each vertex number is an integer) we can round up, and the maximum 3-sum is at least 14.

Therefore we have proven that there is a 3-sum that is at least 14.