AoPS - Problem

Source: 2022 Switzerland IMO TST, Problem 4

Tags: combinatorics, graph theory, winning strategy

Rukevwe

07.08.2022 17:08

Given a (simple) graph $G$ with $n \geq 2$ vertices $v_1, v_2, \dots, v_n$ and $m \geq 1$ edges, Joël and Robert play the following game with $m$ coins: Joël first assigns to each vertex $v_i$ a non-negative integer $w_i$ such that $w_1+\cdots+w_n=m$. Robert then chooses a (possibly empty) subset of edges, and for each edge chosen he places a coin on exactly one of its two endpoints, and then removes that edge from the graph. When he is done, the amount of coins on each vertex $v_i$ should not be greater than $w_i$. Joël then does the same for all the remaining edges. Joël wins if the number of coins on each vertex $v_i$ is equal to $w_i$. Determine all graphs $G$ for which Joël has a winning strategy.

We claim that Robert wins if and only if $G$ is bipartite. If $G$ is bipartite and $V$ can be partitioned into $A$ and $B$, Robert simply needs to pick $w(a) = \text{deg}(a)$ for all $a \in A$ and $\text{deg}(b) = 0$ for all $b \in B$. This forces Joel to place his coins on top of a subset of $A$ and Robert wins by placing his coins on top of the rest of $A$. Now suppose Robert wins. Let $u(x)$ be the number of neighbors $y$ of $x$ with $w(y)=0$. We need $u(v) \ge w(v)$ for all vertices $v$ since otherwise Joel simply has to place his coins on top of all positive-valued neighbors of $v$ to win. This gives $m = \sum w(v) \leq \sum u(v) \leq m$, so we have equality. The former equality yields $w(v) = u(v)$ for all $v$. Combining that with the latter equality gives that all edges are incident with exactly one zero-valued vertex.