Problem

Source: FKMO 2022 Problem 2

Tags: combinatorics, Operation, Korea



There are $n$ boxes $A_1, ..., A_n$ with non-negative number of pebbles inside it(so it can be empty). Let $a_n$ be the number of pebbles in the box $A_n$. There are total $3n$ pebbles in the boxes. From now on, Alice plays the following operation. In each operation, Alice choose one of these boxes which is non-empty. Then she divide this pebbles into $n$ group such that difference of number of pebbles in any two group is at most 1, and put these $n$ group of pebbles into $n$ boxes one by one. This continues until only one box has all the pebbles, and the rest of them are empty. And when it's over, define $Length$ as the total number of operations done by Alice. Let $f(a_1, ..., a_n)$ be the smallest value of $Length$ among all the possible operations on $(a_1, ..., a_n)$. Find the maximum possible value of $f(a_1, ..., a_n)$ among all the ordered pair $(a_1, ..., a_n)$, and find all the ordered pair $(a_1, ..., a_n)$ that equality holds.