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.


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$?
| cite | improve this answer | |
  • $\begingroup$ so for 1. $S_0 + S_1..S_9$ algebraically in terms of $x_0,x_1,..,x_9$ is $3(x_0+x_1+x_2...+x_9)+$ For 2) $x_0+x_1+..x_9=45$ as i added values $0+1..+9=45$ , so $S_0+S_1..S_9$ is in between $45$ and $130$. $\endgroup$ – Kj Tada Jul 5 '13 at 9:41
  • $\begingroup$ @KjTada: (1) Almost: it’s $3(x_0+x_1+\ldots+x_9)$. I suspect that you missed the $x_0$ in $S_8=x_8+x_9+x_0$. (2) You have the pieces, but you’ve not seen how they fit together. With (1) corrected, you know that $$S_0+\ldots+S_9=3(x_0+\ldots+x_9)=3\cdot45=135\;.$$ Is this possible if all of the sums $S_k$ are at most $13$? $\endgroup$ – Brian M. Scott Jul 5 '13 at 9:46
  • $\begingroup$ thanks Brian, no by Pigeon hole then there must be at least one $S_k$ whose sum is greater than 13. $\endgroup$ – Kj Tada Jul 5 '13 at 9:50
  • $\begingroup$ @KjTada: You’ve got it. You're welcome! $\endgroup$ – Brian M. Scott Jul 5 '13 at 9:51

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.