Library / Philippine Mathematical Olympiad - Area Stage /5 of 5

Philippine Mathematical Olympiad - Area Stage

Combinatorics Difficulty 6.0 National Olympiad Prove it Philippines

Problem:

Each of the integers $1,2,3, \ldots, 9$ is assigned to each vertex of a regular 9-sided polygon (that is, every vertex receives exactly one integer from $\{1,2, \ldots, 9\}$ , and two vertices receive different integers) so that the sum of the integers assigned to any three consecutive vertices does not exceed some positive integer $n$ . What is the least possible value of $n$ for which this assignment can be done?

Solution

Solution:

There is an assignment of the integers $1,2,3, \ldots, 9$ to the vertices of the regular nonagon that gives $n=16$ . Let $S$ be the sum of all sums of the integers assigned to three consecutive vertices. If there are integers assigned to three consecutive vertices whose sum is at most $14$ , then $S<135$ , which is a contradiction. Thus, every sum of the integers assigned to three consecutive vertices is equal to $15$ . Consider $a, b, c, d$ . Then $a+b+c=15$ and $b+c+d=15$ , which implies that $a=d$ , a contradiction again.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.