KöMaL 2025 A918

Given a tree with $n \ge 2$ vertices labelled $v_1$, $v_2$, $\dots$, $v_n$. Each vertex hosts a dwarf, and every dwarf has some number of coins, at least $n$. We then go through the vertices in the order of increasing indices: the dwarf on the current vertex takes one coin from its richest neighbour; if there are several richest neighbours, he takes one coin from each of them. Determine, as a function of $n$, the smallest integer $k$ such that for every tree with $n$ vertices there exists an initial coin distribution in which the numbers of coins of any two dwarfs differ by at most $k$, and after the process every dwarf ends up with exactly the same number of coins as at the beginning.