Maths Olympiad Prep

Library / /44 of 61

Combinatorics Difficulty 6.1 National olympiad Prove it Ukraine

Is it possible to write numbers 1,2,3,4,5,6,7,81, 2, 3, 4, 5, 6, 7, 8 at the vertices of an octagon (one number at each vertex) so that the sum of numbers in each three consecutive vertices is greater than:

a) 1313;
b) 1111;
c) 1212?

Solution

Нехай біля вершин правильного восьмикутника послідовно записані числа a1,a2,a3,a4,a5,a6,a7,a8a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8.

a) Припустимо, що числа можна розташувати потрібним чином. Тоді
{a1+a2+a314,a2+a3+a414,a8+a1+a214. \begin{cases} a_1 + a_2 + a_3 \geq 14, \\ a_2 + a_3 + a_4 \geq 14, \\ \vdots \\ a_8 + a_1 + a_2 \geq 14. \end{cases}
Додаючи всі ці нерівності, одержимо: 3(a1+a2++a8)8143(a_1 + a_2 + \ldots + a_8) \geq 8 \cdot 14. Але a1+a2++a8=1+2++8=36a_1 + a_2 + \ldots + a_8 = 1 + 2 + \ldots + 8 = 36, тому дістаємо нерівність 3368143 \cdot 36 \geq 8 \cdot 14, тобто 108112108 \geq 112. Суперечність.

б) Можна покласти, наприклад, a1=1a_1 = 1, a2=5a_2 = 5, a3=6a_3 = 6, a4=2a_4 = 2, a5=4a_5 = 4, a6=7a_6 = 7, a7=3a_7 = 3, a8=8a_8 = 8.

в) Припустимо, що потрібне розміщення чисел існує. Числа 22 і 33 не можна записати в сусідніх вершинах, інакше і зліва і справа від них мало б стояти число 88, яке не може зустрітись двічі. Далі, не порушуючи загальності, можна вважати, що a1=1a_1 = 1, тоді жодне з чисел a2,a3,a7,a8a_2, a_3, a_7, a_8 не дорівнює ані 22 ані 33, а тому або a4=2a_4 = 2 і a6=3a_6 = 3, або a4=3a_4 = 3 і a6=2a_6 = 2. У обох цих випадках маємо a5=8a_5 = 8. Отже, a2,a3,a7a_2, a_3, a_7 та a8a_8 — це записані в деякому порядку числа 4,5,6,74, 5, 6, 7, і тому (a1+a2+a3)+(a7+a8+a1)=24(a_1 + a_2 + a_3) + (a_7 + a_8 + a_1) = 24 та сума принаймні в одній з дужок є меншою за 1313. Суперечність.

Відповідь: а) Не можна. б) Можна. в) Не можна.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.