Baltic Way 2020 · Problem 9

Let $v_1, v_2, \dots, v_n$ be any ordering of the vertices of $G$. Initially each vertex assigned number $1$, and each edge assigned number $2$. One may imagine that there is a chip lying on each vertex, while two chips are lying on each edge. We are going to refine this assignment so as to get a cool one by performing the following greedy procedure.

To explain what we do in the $i$th step, denote by $x_1, x_2, \dots, x_k$ all backward neighbors of $v_i$, and let $e_j = v_i x_j$, with $j = 1, 2, \dots, k$, denote the corresponding backward edges. For each edge $e_j$ we have two possibilities: (1) if there is only one chip on $x_j$, then we may move one chip from $e_j$ to $x_j$ or do nothing, (2) if there are two chips on $x_j$ we may move one chip from $x_j$ to $e_j$ or do nothing. Notice that none of the sums $S(x_j)$ may change as a result of such action. Also, any action on each edge may change the total sum for $v_i$ just by one. Hence there are $k+1$ possible values for $S(v_i)$. So, at least one combination of chips gives a sum which is different from each of $S(x_j)$. We fix this combination and go to the next step. The proof is complete.