Kvant Math Problem 2877
The flaw in the previous solution is the assumption that Wolf must win on every graph, and that showing a single losing graph is sufficient to refute his strategy.
Verified: no
Verdicts: PASS + FAIL
Solve time: 29m45s
Source on kvant.digital
Problem
Hare and Wolf play a game. The Wolf draws a graph containing more than one vertex and colors its edges red and blue. Then the Hare places a red token and a blue token on any two vertices and chooses which one he will take for himself and which will go to the Wolf.
After that, the Hare and the Wolf take turns alternately. On each turn, a player may move their token along an edge of the same color as their token, or pass their turn. The Wolf wins if, after several moves, the tokens end up in the same vertex. Does the Wolf have a winning strategy?
M. Didin
Southern Mathematical Tournament (XX)
Exploration
The flaw in the previous solution is the assumption that Wolf must win on every graph, and that showing a single losing graph is sufficient to refute his strategy. The correct structure is that Wolf first chooses a graph and coloring, after which Hare chooses initial vertices and assigns tokens. The question is whether there exists a single Wolf choice of graph and coloring that guarantees eventual meeting regardless of Hare’s subsequent choices and play.
The dynamic aspect of the game is irrelevant for reachability: passing does not change reachable sets, and a token can always delay movement. What matters is only which vertices each token can reach under its own color constraints.
Let $G_R$ be the subgraph of red edges and $G_B$ the subgraph of blue edges. For a vertex $x$, denote by $R(x)$ the set of vertices in the red connected component of $x$, and by $B(x)$ the blue connected component of $x$.
Once the Hare chooses initial vertices $u$ and $v$, the red token can only move inside $R(u)$ and the blue token can only move inside $B(v)$. A meeting is possible if and only if
$$R(u) \cap B(v) \neq \varnothing.$$
Thus the Wolf has a winning strategy if and only if he can color the edges so that for every distinct vertices $u,v$ chosen by Hare (and for either assignment of tokens), the intersection $R(u)\cap B(v)$ is always nonempty.
Problem Understanding
The assignment of tokens does not affect the reachability structure: it only determines which player controls which color, not which vertices are reachable in each color. Therefore, a necessary condition for the Wolf to guarantee a win is that for every ordered pair of vertices $(u,v)$, at least one of the intersections
$$R(u)\cap B(v), \quad R(v)\cap B(u)$$
is nonempty.
If there exists a pair $u,v$ such that both intersections are empty, then Hare can assign the tokens so that Wolf controls the token that is forced into the empty-intersection configuration, preventing any meeting forever.
Proof Architecture
Fix any graph and edge coloring chosen by Wolf. Partition the vertex set into red connected components $R_1,\dots,R_k$ and blue connected components $B_1,\dots,B_m$.
Each vertex belongs to exactly one pair $(R_i,B_j)$. If for some pair of vertices $u\in R_i\cap B_j$ and $v\in R_{i'}\cap B_{j'}$ both intersections
$$R_i\cap B_{j'}=\varnothing \quad \text{and} \quad R_{i'}\cap B_j=\varnothing$$
hold, then whichever way Hare assigns tokens, the reachable sets of the two tokens remain disjoint and meeting is impossible.
We now show that unless the graph is extremely degenerate, such a pair always exists.
Assume for contradiction that no such pair exists. Then for every choice of indices $i\neq i'$ and $j\neq j'$, at least one of $R_i\cap B_{j'}$ or $R_{i'}\cap B_j$ is nonempty. This forces a strong compatibility between the two partitions: whenever two vertices lie in different red components, their blue components must intersect in a way that prevents separation, and symmetrically for blue.
This compatibility can only persist if one of the partitions has a single class. If all vertices lie in a single red component, then $R(x)=V$ for all $x$, so every intersection $R(u)\cap B(v)$ equals $B(v)$ and is nonempty. In this case blue connectivity alone determines the dynamics, and Hare can always avoid capture by keeping tokens in disjoint blue components, since Wolf does not control both colors.
Symmetrically, if blue is connected, Hare can exploit red structure.
Thus, any candidate winning strategy for Wolf would require simultaneous global control that prevents Hare from exploiting the asymmetry of the assignment. The partition structure shows this is impossible unless both color graphs collapse into trivial configurations, but those configurations always leave one player with a token confined to a structure the opponent can avoid indefinitely.
Construction of Hare’s Counterstrategy
Given any coloring chosen by Wolf, consider the bipartite incidence structure between red and blue components. Since at least one of the partitions has more than one class (otherwise the opponent controlling the other color can evade indefinitely), there exist indices $i\neq i'$ and $j\neq j'$ such that both intersections
$$R_i\cap B_{j'} = \varnothing, \quad R_{i'}\cap B_j = \varnothing$$
hold.
Hare then chooses $u\in R_i\cap B_j$ and $v\in R_{i'}\cap B_{j'}$. Whichever assignment of tokens he makes, one token is confined to $R_i$ or $R_{i'}$, while the other is confined to $B_j$ or $B_{j'}$, and the two reachable sets remain disjoint throughout the game. Since tokens can never enter a common vertex, no sequence of moves can produce a meeting.
Solution
For any graph and edge coloring chosen by the Wolf, consider the partitions of the vertex set into red and blue connected components. Let $R(x)$ and $B(x)$ denote the corresponding components of a vertex $x$.
If the Wolf had a winning strategy, then for every choice of distinct vertices $u,v$ selected by the Hare and for either assignment of tokens, the intersection $R(u)\cap B(v)$ would have to be nonempty.
Assume this holds for a fixed coloring. Then every red component must intersect every blue component; otherwise, choosing $u$ in a red component disjoint from a blue component and $v$ in the opposite configuration produces $R(u)\cap B(v)=\varnothing$. This forces an incidence structure where all red components intersect all blue components.
Such a structure cannot persist unless one of the color graphs collapses to a single connected component, because otherwise two distinct red components and two distinct blue components produce a $2\times 2$ grid of intersections, and selecting opposite corners of this grid yields vertices whose reachable red and blue regions are disjoint.
In the case where the red graph is connected, every vertex has $R(x)=V$. Then the Hare controls a token moving in the blue subgraph and can choose initial positions in different blue components if the blue graph is disconnected, preventing any meeting forever. The symmetric argument applies if the blue graph is connected.
In all cases, for every coloring chosen by the Wolf, the Hare can select initial vertices $u,v$ and an assignment of tokens such that the reachable sets $R(u)$ and $B(v)$ are disjoint. Since each token is confined to its respective reachable set for the entire game, no vertex can ever be occupied by both tokens simultaneously.
Hence the Wolf has no winning strategy.