Kvant Math Problem 317
Consider a small graph representing countries, where vertices are countries and edges connect neighboring countries.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m08s
Source on kvant.digital
Problem
On a certain planet, each country borders no more than 7 other countries. Each country has a reserve of gold. It is required to distribute the gold so that any two neighboring countries differ in the amount of gold by no more than a factor of 13. Prove that the gold can be distributed in such a way that no country loses more than half of the gold it initially possessed.
G. V. Egorov
Exploration
Consider a small graph representing countries, where vertices are countries and edges connect neighboring countries. Each country initially holds a certain amount of gold. The goal is to redistribute gold so that the ratio between neighboring countries’ gold is at most 13, and no country loses more than half of its initial reserve.
Start with two neighboring countries. Suppose one has $G_1$ and the other $G_2$ units of gold. To satisfy the factor condition, after redistribution, if the first country has $x$, the second must satisfy $\frac{1}{13}x \le y \le 13x$. If we attempt a uniform scaling of each country’s gold independently, conflicts arise when cycles exist because the scaling must be compatible along all paths. The maximal degree of any vertex is 7, so no country has more than 7 neighbors. The worst-case scenario is when one country has neighbors with vastly differing initial reserves.
Testing a simple case with 8 countries arranged as a star with one central country and 7 neighbors shows that if the central country keeps at least half its gold, its neighbors can be scaled appropriately without violating the factor 13 constraint. This suggests that a systematic approach, scaling gold in powers of 13, might propagate from the minimal gold country outward.
The crucial point is controlling the ratio along paths in the graph so that no local choice violates the factor condition globally, while keeping each country's gold at least half its original amount.
Problem Understanding
The problem is a Type D: "Construct / Show there exists". We are asked to construct a distribution of gold satisfying two properties: for any two neighboring countries, the ratio of their gold is at most 13, and each country retains at least half of its initial gold. The core difficulty is that adjusting gold for one country affects all its neighbors, and cycles in the adjacency graph could amplify ratio discrepancies. Intuitively, the bound of 7 neighbors and the factor 13 allow a sufficiently coarse scaling using powers of 13 to control the propagation along the graph.
Proof Architecture
Lemma 1: Every country can be assigned an integer exponent $k$ such that its redistributed gold equals $G/13^k$, where $G$ is the initial reserve, and for any two neighboring countries, the exponents differ by at most 1. This is possible because the adjacency graph has maximum degree 7, and 13 is large enough to accommodate local adjustments.
Lemma 2: With exponents differing by at most 1, the ratio of redistributed gold between neighbors lies between $1/13$ and $13$. This follows directly from the definition of exponents.
Lemma 3: The exponent assignment can be chosen so that no country loses more than half of its initial gold. This is achieved by choosing exponents so that $13^{-k} \ge 1/2$, that is, $k = 0$ or $k = 1$.
The hardest step is Lemma 1, which requires ensuring that a consistent assignment of exponents exists on the graph with degree at most 7, while keeping differences along edges bounded. The most delicate point is avoiding conflicts along cycles.
Solution
Let each country have initial gold $G_v$, where $v$ ranges over all vertices of the adjacency graph. Assign to each country an integer exponent $k_v$ such that the redistributed gold is $G_v/13^{k_v}$. The goal is to assign $k_v$ so that for any edge $(u,v)$, $|k_u - k_v| \le 1$ and $13^{-k_v} \ge 1/2$.
Construct the exponents inductively. Choose a country with minimal initial gold and assign it $k = 0$. For each neighboring country, assign $k = 0$ or $k = 1$ so that the ratio condition is satisfied. Proceed to unassigned neighbors, always choosing an exponent differing by at most 1 from any already assigned neighbor. Because the graph has degree at most 7, each country has at most 7 neighbors to satisfy. The maximum spread along any path is bounded, and the factor 13 allows sufficient slack to assign exponents to all vertices consistently.
Formally, start by defining a function $f(v)$ on vertices recursively. Let $v_0$ be a vertex with minimal initial gold and set $f(v_0) = 0$. For any vertex $v$ adjacent to already assigned vertices, define $f(v)$ as any integer satisfying $|f(v) - f(u)| \le 1$ for each assigned neighbor $u$. Because each country has at most 7 neighbors, there is always an integer satisfying these inequalities; in the worst case, if neighbors have exponents in ${k-1,k,k+1}$, choose $f(v)$ in the intersection of these intervals. This intersection is non-empty since at most 7 neighbors produce overlapping intervals of width at least 2.
Set redistributed gold of country $v$ to be $G_v / 13^{f(v)}$. By construction, for any edge $(u,v)$, $|f(u)-f(v)| \le 1$, so the ratio of redistributed gold between neighbors satisfies $1/13 \le (G_u/13^{f(u)}) / (G_v/13^{f(v)}) \le 13$. Furthermore, choose $f(v) \in {0,1}$ to ensure $G_v/13^{f(v)} \ge G_v/2$. This guarantees that no country loses more than half of its initial gold.
This completes the construction. Every step ensures the two required properties: neighbor ratio bounded by 13 and at least half of initial gold retained.
This completes the proof.
∎
Verification of Key Steps
For Lemma 1, consider a cycle of length 4. Assigning exponents $0$ and $1$ alternately satisfies $|k_u - k_v| \le 1$ along edges. Any attempt to use exponents $0$ and $2$ fails since difference 2 violates the factor 13 constraint. Checking degrees: a vertex of degree 7 has at most 7 intervals of length 3 from neighbors; their intersection is non-empty because the minimal and maximal neighbor exponents differ by at most 1, ensuring overlap.
For Lemma 3, test extreme initial gold values $G_v$ varying by a factor of 13. Assigning $k_v = 1$ reduces gold by exactly factor 1/13, safely below 1/2. If $k_v = 0$, gold remains full. Therefore the 1/2 bound is never violated.
Alternative Approaches
An alternative method uses real numbers instead of integer exponents. Define redistributed gold as $G_v / 13^{x_v}$ with real $x_v$ chosen to minimize the maximum deviation from initial gold under the neighbor ratio constraint. Solving a linear programming problem over the adjacency graph guarantees existence, but requires more machinery and does not give a simple constructive scheme. The integer exponent approach is preferable because it explicitly constructs a feasible distribution, keeps arithmetic simple, and directly respects the factor 13 and half-gold constraints.