Максимальна кількість ходів для розподілу камінців

Умова задачі

Нехай $n \ge 3$ — фіксоване натуральне число. Є $n$ коробок $A_1, A_2, \dots, A_n$ , у кожній з яких лежить певна кількість камінців $(a_1, a_2, \dots, a_n)$ , причому $a_1+a_2+\cdots+a_n = 3n$ . Хід складається з таких дій:
вибрати коробку та розкласти всі камінці з неї по $n$ коробках (включно з вибраною коробкою) так, щоб для будь-яких двох коробок кількості доданих до них камінців відрізнялися не більше ніж на 1.
Для розподілу $a_1, a_2, \dots, a_n$ визначимо $f(a_1, a_2, \dots, a_n)$ як найменшу кількість ходів, потрібну для того, щоб зібрати всі камінці в одній коробці. Нехай $M_n$ — максимум $f(a_1, a_2, \dots, a_n)$ за всіма можливими розподілами $a_1, a_2, \dots, a_n$ , для яких $a_1 + a_2 + \cdots + a_n = 3n$ . Визначте $M_n$ та всі розподіли $a_1, a_2, \dots, a_n$ , для яких $f(a_1, a_2, \dots, a_n) = M_n$ .

Приклад. Якщо $n = 4$ і в коробках по порядку лежить 2, 6, 0, 4 камінці, то ми можемо розкласти 2 камінці з коробки $A_1$ , поклавши в кожну коробку по порядку 1, 0, 1, 0 камінців. Після цього ходу кількість камінців у кожній коробці по порядку дорівнює 1, 6, 1, 4.

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

Оптимальна конструкція (оцінка і приклад)Напівінваріанти

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

Задачі дня

Максимальна кількість ходів для розподілу камінців

Умова задачі

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

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

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

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

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

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

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

Про проєкт

Автори задач

Що в архіві

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

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

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

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

З чого почати

Хто це робить

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

Автори задач

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

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

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

Дякуємо