Гарні та чудові маркування м'ячів з мотузками

Умова задачі

Для кожного натурального $k$ визначимо набір кольорів числами:
$R_n=\{-k,\ -(k-1),\ \ldots,\ -2,\ -1,\ 1,\ 2,\ \ldots,\ (k-1),\ k\},\quad \text{для } n=2k,$
$\text{та}\quad R_n=\{-k,\ -(k-1),\ \ldots,\ -2,\ -1,\ 0,\ 1,\ 2,\ \ldots,\ (k-1),\ k\},\quad \text{для } n=2k+1.$

Схема складається з набору м'ячів, а також чорних і червоних мотузок, що з'єднують деякі м'ячі в пари. При цьому один м'яч може бути в декількох парах з різними м'ячами. Маркування — це фарбування кожного м'яча в один з кольорів із множини $R_n$ . Назвемо таке маркування гарним, якщо будь-які два м'ячі, що з'єднані мотузкою, мають різний колір. Назвемо маркування чудовим, якщо колір будь-яких двох м'ячів, що з'єднані чорною мотузкою, різний, а сума кольорів будь-яких двох м'ячів, що з'єднані червоною мотузкою, не дорівнює $0$ .

Нехай $n \geqslant 3$ — фіксоване. Припустимо, що довільна схема, яка має гарне маркування за допомогою $R_n$ кольорів, обов'язково має також і чудове маркування за допомогою $R_m$ кольорів. Знайдіть найменше можливе значення $m$ для $n$ .

Пов’язані теми

Оптимальна конструкція (оцінка і приклад)Принцип Діріхле (скінченні множини)

Олімпіадні задачі з математики

Задачі дня

Гарні та чудові маркування м'ячів з мотузками

Умова задачі

Пов’язані теми

Рекомендації щодо вивчення олімпіадної математики

Гурток за п’ять хвилин

П’ять років програми

Шість правил, підтверджених дослідженнями

Ритм олімпіадного року

Як зібрати задачі тут

Про проєкт

Автори задач

Що в архіві

Українські олімпіади й турніри

Міжнародні олімпіади

Змагання інших країн

Що є в кожної задачі

З чого почати

Хто це робить

Помилки та пропозиції

Автори задач

Богдан Рубльов

Українські олімпіади й турніри

Міжнародні й закордонні змагання

Дякуємо