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

Умова задачі

Нехай $n \geq 3$ — фіксоване натуральне число. Є $n$ коробок $A_{1}, A_{2}, \ldots, A_{n}$ , у кожній з яких лежить деяка кількість камінців $a_{1}, a_{2}, \ldots, a_{n}$ так, що $a_{1}+a_{2}+\cdots+a_{n}=3 n$ . Хід складається з таких дій:
вибрати коробку і розкласти всі камінці з неї по $n$ коробках (включно з вибраною) так, щоб для будь-яких двох коробок кількості доданих камінців відрізнялися не більше ніж на 1.
Для розподілу $a_{1}, a_{2}, \ldots, a_{n}$ визначимо $f\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ як найменшу кількість ходів, потрібну, щоб зібрати всі камінці в одній коробці. Нехай $M_{n}$ — максимум $f\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ за всіма можливими розподілами $a_{1}, a_{2}, \ldots, a_{n}$ такими, що $a_{1}+a_{2}+\cdots+a_{n}=3 n$ . Знайдіть $M_{n}$ і всі розподіли $a_{1}, a_{2}, \ldots, a_{n}$ , для яких $f\left(a_{1}, a_{2}, \ldots, a_{n}\right)=M_{n}$ .
Приклад. Якщо $n=4$ і в коробках міститься 2, 6, 0, 4 камінці, то 2 камінці з коробки $A_{1}$ можна роздати як 1,0,1,0. Після цього ходу кількість камінців у коробках дорівнює 1, 6, 1, 4.

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

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

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

Задачі дня

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

Умова задачі

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

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

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

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

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

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

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

Про проєкт

Автори задач

Що в архіві

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

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

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

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

З чого почати

Хто це робить

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

Автори задач

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

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

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

Дякуємо