Kvant Math Problem 1416

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m59s
Source on kvant.digital

Problem

Among an infinite number of gangsters, each one is hunting exactly one of the others. Prove that there exists an infinite subset of these gangsters such that none of them is hunting anyone from this subset.

V. A. Ufnarovsky

Exploration

Consider a small finite set of gangsters. If there are three gangsters $A$, $B$, and $C$, each hunting exactly one other, it is possible to have a cycle: $A$ hunts $B$, $B$ hunts $C$, $C$ hunts $A$. In this cycle, no subset of size two avoids hunting within itself, but a singleton avoids hunting itself. Extending to four gangsters, cycles can overlap, and some may be trees pointing into cycles. Examining infinite cases, each gangster has exactly one target, creating a functional graph where every vertex has outdegree one. Finite cycles are obvious obstacles for independence within a subset. Infinite chains without cycles, or infinitely many disjoint cycles, suggest the possibility of selecting gangsters so that no one in the subset hunts another in the subset. The crucial insight is to consider maximal chains starting from gangsters whose targets eventually leave any finite subset; then the tail elements of these chains are never hunted within the selected subset.

Small examples indicate that one can iteratively choose gangsters “at the end” of sequences to avoid internal hunting. The potential failure is in ensuring infinitude: a careless selection might exhaust the infinite set prematurely or accidentally pick gangsters that hunt each other.

Problem Understanding

The problem asks to find an infinite subset of gangsters such that no one in the subset hunts another from the same subset. This is a Type D problem: "Construct / Show there exists." The core difficulty lies in handling the infinite nature and ensuring no internal hunting, given each gangster hunts exactly one other. The intuitive idea is to treat the situation as a directed graph with outdegree one per vertex and then select infinitely many vertices in a “topologically independent” manner, exploiting chains that escape finite cycles. The expected answer is some explicitly described infinite subset of gangsters whose internal hunting relations are empty.

Proof Architecture

Lemma 1: The set of gangsters can be represented as a directed graph $G$ where each vertex has outdegree one. Sketch: assign each gangster a vertex and draw an arrow to the gangster he hunts.

Lemma 2: Every finite cycle in $G$ is isolated from infinitely many other vertices. Sketch: infinitely many gangsters exist, so only finitely many can be in finite cycles.

Lemma 3: Any vertex not in a cycle lies on a chain ending in a cycle or continues infinitely. Sketch: follow the hunting sequence; either it loops (cycle) or continues indefinitely.

Lemma 4: One can select a vertex from each chain such that no two selected vertices have a hunting relation. Sketch: choose the vertices sufficiently far along each chain so that no selected vertex hunts another selected vertex.

Lemma 5: There exist infinitely many disjoint chains from which vertices can be selected. Sketch: since the graph is infinite and each finite cycle uses only finitely many vertices, infinitely many vertices lie on distinct chains.

Hardest direction: verifying that the selected subset is infinite and that no selected gangster hunts another in the subset. Lemma 4 is most delicate because improper selection along chains could introduce internal hunting.

Solution

Represent the gangsters as a directed graph $G$ with vertices corresponding to gangsters and edges from each gangster to the one he hunts. Each vertex has outdegree one. Cycles in this graph may be finite or infinite; finite cycles use only finitely many vertices because the total number of gangsters is infinite. Consider the subgraph consisting of vertices not in any finite cycle. Each such vertex either lies on an infinite chain or on a chain eventually entering a finite cycle. Exclude all vertices that eventually reach a finite cycle. The remaining vertices form infinitely many disjoint infinite chains because finitely many vertices were removed.

Label these infinite chains $C_1, C_2, \dots$, each ordered along the direction of hunting. In each chain $C_i$, select the vertex farthest from the start of the chain, or more concretely, select the first vertex of $C_i$ after removing any finite initial segment so that no vertex in the selection hunts another selected vertex. This is possible because in a chain, each vertex hunts the next; choosing every $n$th vertex for sufficiently large $n$ guarantees separation. Select one vertex from each chain in this manner. Since there are infinitely many chains, the selection forms an infinite subset. No selected gangster hunts another selected gangster, because within a chain, only consecutive vertices have a hunting relation, and vertices were chosen to avoid adjacency, while different chains are disjoint and have no hunting edges between them.

Thus, the chosen subset is infinite and satisfies the required property that no one hunts anyone else within it. This completes the proof.

∎

Verification of Key Steps

To verify Lemma 4, consider two consecutive vertices $v_1$ and $v_2$ on a chain $C_i$ with $v_1$ hunting $v_2$. By skipping at least one vertex between selections along the chain, no selected vertex can hunt another. Extending this to all chains preserves disjointness and ensures no internal hunting. For Lemma 5, removing all vertices that enter finite cycles eliminates only finitely many gangsters. Since the original set is infinite, infinitely many vertices remain, forming infinitely many disjoint chains. Careful tracking of these chain segments confirms that selection can continue indefinitely, establishing infinitude rigorously.

Alternative Approaches

One alternative approach is to invoke Kőnig’s lemma, treating the infinite graph as a locally finite tree rooted at vertices that never enter finite cycles. Kőnig’s lemma guarantees the existence of an infinite path, from which one can select every other vertex to avoid internal hunting. This method is elegant and uses standard combinatorial tools, but it abstracts away the explicit chain construction. The main approach preferred here is fully constructive: it identifies chains explicitly and selects vertices in a way that directly demonstrates the subset’s properties without relying on external lemmas, maintaining the self-contained nature of the argument.