Competition problem — Combinatorics

Library / /29 of 35

Combinatorics Difficulty 6.6 National olympiad Prove it Belarus

Fix a positive integer $n$ and a finite graph with at least one edge; the end points of each edge are distinct, and any two vertices are joined by at most one edge. Vertices and edges are assigned (not necessarily distinct) numbers in the range $0$ through $n-1$ , one number each. A vertex assignment and an edge assignment are compatible if the following condition is satisfied at each vertex $v$ : The number assigned to $v$ is congruent modulo $n$ to the sum of the numbers assigned to the edges incident to $v$ . Fix a vertex assignment and let $N$ be the total number of compatible edge assignments; compatibility refers, of course, to the fixed vertex assignment.
Prove that, if $N \neq 0$ , then the prime divisors of $N$ are all at most $n$ . (In particular, if $n = 2$ and $N \neq 0$ , then $N$ is a power of $2$ .)

Solution

An edge assignment compatible with a fixed vertex assignment will be referred to as a solution relative to that vertex assignment. A solution relative to the all-zero vertex assignment will be referred to as a fundamental solution; the all-zero edge assignment is a fundamental solution.

Fix a vertex assignment and fix a solution (if any). Componentwise subtraction modulo $n$ of the fixed solution from a solution provides a fundamental solution. Conversely, componentwise addition modulo $n$ of the fixed solution to a fundamental solution provides a solution. The two solution assignments are clearly inverse to one another, so the number of solutions is either zero or equal to the number of fundamental solutions. Consequently, it is sufficient to prove the conclusion for the number $N$ of fundamental solutions.

To this end, induct on the number of edges. The base case is clear: A graph with a single edge has a single fundamental solution, namely, the all zero edge assignment.

For the induction step, consider a graph $G$ with at least two edges. Fix an edge $e$ of $G$ and let $G' = G - e$ ; clearly, $G'$ has at least one edge. For each $k$ in the range $0$ through $n-1$ , let $S_k$ be the set of fundamental solutions for $G$ assigning $k$ to $e$ , and let $T_k$ be the set of solutions for $G'$ relative to the vertex assignment sending both end points of $e$ to $n-k$ and all other vertices to zero.

Changing only the $e$ -component of a solution in $S_k$ to zero, and changing the vertex assignment only at the end points of $e$ by sending them both to $n-k$ , enable removal of $e$ from $G$ to provide a bijection from $S_k$ to $T_k$ . Since the size of each non-empty $T_k$ is equal to the number $N'$ of fundamental solutions for $G'$ , so is the size of each non-empty $S_k$ . Consequently, $N = mN'$ , where $m$ is the number of non-empty sets $S_k$ ; incidentally, $m \ge 1$ , since $S_0$ is non-empty — it contains the all zero edge assignment. Finally, the prime divisors of $m$ do not exceed $n$ , since $m \le n$ ; and the prime divisors of $N'$ do not exceed $n$ , by the induction hypothesis. Consequently, the prime divisors of $N = mN'$ do not exceed $n$ either. This completes the induction step and concludes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.