Problem A. 918. (November 2025)
A. 918. Given a tree with \(\displaystyle n \ge 2\) vertices labelled \(\displaystyle v_1\), \(\displaystyle v_2\), \(\displaystyle \dots\), \(\displaystyle v_n\). Each vertex hosts a dwarf, and every dwarf has some number of coins, at least \(\displaystyle 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 \(\displaystyle n\), the smallest integer \(\displaystyle k\) such that for every tree with \(\displaystyle n\) vertices there exists an initial coin distribution in which the numbers of coins of any two dwarfs differ by at most \(\displaystyle k\), and after the process every dwarf ends up with exactly the same number of coins as at the beginning.
Proposed by Márton Németh, Budapest
(7 pont)
Deadline expired on December 10, 2025.
Answer: We show the smallest such value of \(\displaystyle k\) is \(\displaystyle n-2\).
Construction: For \(\displaystyle k\geq n-2\), consider the star graph with \(\displaystyle n-1\) vertices, with centre \(\displaystyle v\), leaves \(\displaystyle w\), \(\displaystyle w_2\), \(\displaystyle \ldots\), \(\displaystyle w_{n-2}\), and attach a leaf \(\displaystyle u\) to \(\displaystyle w\). Let the order of the nodes be \(\displaystyle v, w, w_2, \ldots, w_{n-2}, u\).
The key insight is that whenever a leaf takes a coin from its neighbour, that neighbour must later give a coin back to the leaf; hence, when the neighbour is processed, the leaf is one of its richest neighbours. Thus during the first iteration, vertex \(\displaystyle v\) obtains \(\displaystyle n-3\) coins. Then \(\displaystyle w\) takes a coin from \(\displaystyle u\), so \(\displaystyle u\) initially has \(\displaystyle n-3\) more coins than \(\displaystyle v\). This can be improved to \(\displaystyle n-2\) upon noticing that \(\displaystyle n-3\) is only achievable if \(\displaystyle v\) doesn't take a coin from \(\displaystyle w\), so neither does \(\displaystyle w\) from \(\displaystyle v\), so when \(\displaystyle w\) takes coins, \(\displaystyle u\) is strictly richer than \(\displaystyle v\), contradiction.
Upper bound: We prove a stronger statement: for any tree and indexing, one can assign coins so that whenever a vertex takes coins from its neighbours, all of its neighbours have the same ammount of coins. This is sufficient, since if the degree of a vertex is \(\displaystyle d\), then it loses a coin \(\displaystyle d\) times, and gets \(\displaystyle d\) coins once.
Every tree is bipartite, so color the vertices black and white so that adjacent vertices are colored different. It's sufficient to construct an initial configuration where the pairwise difference of coins of black (and respectively, white) vertices is at most \(\displaystyle n-2\), because then WLOG we increase all numbers of coins on white vertices by the same ammount. This does not influence the process, as only the relative numbers of coins on neighbours of a vertex matter.
So let's consider only the black vertices. Let \(\displaystyle B\) be any black vertex, we give it say \(\displaystyle 0\) coins (we worry not about coins going negative, we can always shift all numbers by some large positive ammount). Then for \(\displaystyle i=2, 4, 6, \ldots\), in order, we assign coins to black vertices of distance \(\displaystyle i\) from \(\displaystyle B\).
For vertex \(\displaystyle B_i\) at distance \(\displaystyle i\) from \(\displaystyle B\) (\(\displaystyle i\geq 2\)) let \(\displaystyle BW_1B_2W_3\ldots B_i\) be (the unique) path from \(\displaystyle B\) to \(\displaystyle B_i\). Consider the moment when \(\displaystyle W_{i-1}\) takes coins from its neighbours. Assume so far \(\displaystyle a_1\) of neighbours of \(\displaystyle B_{i-2}\) took coins, \(\displaystyle B_{i-2}\) itself took coins \(\displaystyle \varepsilon_1\in \{0, 1\}\) times. Let \(\displaystyle b_1\) denote the number of coins assigned to \(\displaystyle B_{i-2}\) initially (which is well-defined as \(\displaystyle i-2<i\)). Similarly so far \(\displaystyle a_2\) of neighbours of \(\displaystyle B_i\) took coins already, \(\displaystyle B_i\) itself took coins \(\displaystyle \varepsilon_2\in \{0, 1\}\) times. Finally denote \(\displaystyle d(v)\) the degree of vertex \(\displaystyle v\) in the graph.
Give \(\displaystyle b_2 = b_1+\varepsilon_1d(B_{i-2})-a_1+a_2-\varepsilon_2 d(B_i)\) coins to \(\displaystyle B_i\)! We show anytime a white vertex takes coins, its neighbours are equally rich.
We proceed by induction by the indexing of the vertices. For the first vertex \(\displaystyle v\), the claim holds, since in the above formula, \(\displaystyle a_i\) and \(\displaystyle \varepsilon_i\) are all \(\displaystyle 0\), so all of the neighbours of \(\displaystyle v\) get the same value \(\displaystyle b\).
In some subsequent step, WLOG some white vertex is taking coins. Then assume its closest neighbour to \(\displaystyle B\) is \(\displaystyle B_{i-2}\), which received \(\displaystyle b_1\) coins. By the induction hypothesis it also received \(\displaystyle \varepsilon_1d(B_{i-2})\) coins, and lost \(\displaystyle a_1\) so far, so now has \(\displaystyle b_1+\varepsilon_1d(B_{i-2})-a_1\) coins. Some other neighbour \(\displaystyle B_i\) got \(\displaystyle b_2 = b_1+\varepsilon_1d(B_{i-2})-a_1+a_2-\varepsilon_2 d(B_i)\) coins initially, then got \(\displaystyle \varepsilon_2 d(B_i)\) more, and lost \(\displaystyle a_2\), so also has \(\displaystyle b_1+\varepsilon_1d(B_{i-2})-a_1\) currently. This concludes the induction step.
It is hence sufficient to show all differences between initial numbers of coins between black vertices is at most \(\displaystyle n-2\). Let \(\displaystyle B_1\) and \(\displaystyle B_k\) be two arbitrary black vertices. Let the connecting path be \(\displaystyle B_1W_1B_2W_2\ldots W_{k-1}B_k\). Denote by \(\displaystyle x_i\) and \(\displaystyle y_i\) the number of coins on \(\displaystyle B_i\) at moments right before \(\displaystyle W_i\) and \(\displaystyle W_{i-1}\) are taking coins, respectively. By the above, \(\displaystyle x_i = y_{i+1}\).
We know \(\displaystyle |x_i-y_i|\leq d(B_i)\), since the number of coins of \(\displaystyle B_i\) increased and decreased by \(\displaystyle d(B_i)\)in total, so that is also its maximal change. Hence
\(\displaystyle |x_1 - y_k| = |x_{k-1} - y_2|\leq \sum_{i=2}^{k-1} |x_i-y_i|\leq \sum_{i=2}^{k-1} d(B_i). \)
Initial number of coins in \(\displaystyle B_1\) and \(\displaystyle x_1\) differ by at most \(\displaystyle d(B_1)\). Similarly initial number of coins in \(\displaystyle B_k\) and \(\displaystyle y_k\) differ by at most \(\displaystyle d(B_k)\). So the total difference is at most
\(\displaystyle d(B_1) + \sum_{i=2}^{k-1} d(B_i) + d(B_k) \leq n-1, \)
since edges coming from black vertices are pairwise different.
Let's look at the equality case. Then the \(\displaystyle x_i-y_i\) have the same sign, in absolute value equal \(\displaystyle d(B_i)\). Similarly the number of coins in \(\displaystyle B_1\) initially minus \(\displaystyle x_1\), and the number of coins in \(\displaystyle B_k\) initially minus \(\displaystyle y_k\) match signs, and are \(\displaystyle d(B_1)\) and \(\displaystyle d(B_k)\) in absolute value. But then \(\displaystyle W_1\) and \(\displaystyle W_{k-1}\) are indexed lower than \(\displaystyle B_1\) and \(\displaystyle B_k\) respectively, contradiction. Hence we're done.
Statistics:
13 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Bolla Donát Andor, Gyenes Károly, Kis Ágoston, Sárdinecz Dóra, Szakács Ábel, Xiaoyi Mo. 6 points: Forrai Boldizsár. 5 points: 1 student. 2 points: 1 student. 0 point: 2 students.
Problems in Mathematics of KöMaL, November 2025