Kvant Math Problem 459
Let the route produced by the minimum-greedy algorithm be
Verified: no
Verdicts: FAIL + FAIL
Solve time: 24m48s
Source on kvant.digital
Problem
In a certain country, it is possible to travel directly from any city to any other city without passing through any of the remaining cities. The cost of each such trip is known. Two routes for traveling through the cities of the country have been constructed. In each route, every city is visited exactly once.
The first route was constructed according to the following principle: the starting city is chosen arbitrarily, and at each subsequent step, among the cities not yet visited by the route, the one is chosen for which the trip from the previous city has the lowest cost (if there are several such cities, any one of them may be chosen); this continues until all cities have been visited.
The second route was constructed in a similar way: the starting city is also chosen arbitrarily, but at each subsequent step, among the cities not yet visited, the one is chosen for which the trip from the previous city has the highest cost.
Prove that the total cost of travel along the first route is no greater than the total cost of travel along the second route.
A. A. Berzinsh
All-Union Mathematical Olympiad for School Students (XI, 1977, Grade 9)
Exploration
Let the route produced by the minimum-greedy algorithm be
$$a_1,a_2,\dots,a_n,$$
and let
$$e_k=(a_k,a_{k+1}), \qquad k=1,\dots,n-1.$$
Denote the cost of the trip between cities $x$ and $y$ by $w(x,y)=w(y,x)$.
For every $k$, put
$$S_k={a_1,\dots,a_k}.$$
When the first algorithm is at $a_k$, the unvisited cities are precisely $V\setminus S_k$. Hence
$$w(e_k) = \min_{v\notin S_k} w(a_k,v).$$
Let the route produced by the maximum-greedy algorithm be
$$b_1,b_2,\dots,b_n,$$
with edges
$$f_r=(b_r,b_{r+1}), \qquad r=1,\dots,n-1.$$
For every $r$, put
$$T_r={b_1,\dots,b_r}.$$
When the second algorithm is at $b_r$, the cities still available are precisely $V\setminus T_r$, and therefore
$$w(f_r) = \max_{v\notin T_r} w(b_r,v).$$
Let
$$m=\sum_{k=1}^{n-1} w(e_k), \qquad M=\sum_{r=1}^{n-1} w(f_r).$$
The goal is to prove that $m\le M$.
Problem Understanding
The failed proof tried to compare individual edges of the two routes. The reviewers correctly pointed out that the proposed comparison related unrelated edge weights and could not yield the desired inequality.
A different viewpoint is needed.
For each city $x$, consider all cities that appear after $x$ in the minimum-greedy route. At the moment when the first algorithm leaves $x$, it chooses the cheapest edge from $x$ to that set. Consequently the contribution of $x$ to the first route is the minimum edge from $x$ to a certain subset of cities.
For the second route, if we look at all cities that appear after $x$ in the maximum-greedy route, then the contribution of $x$ is the maximum edge from $x$ to that subset.
The key fact is a purely combinatorial identity: every unordered pair of cities ${x,y}$ contributes exactly once to the first kind of counting and exactly once to the second. Summing suitable inequalities over all cities then yields the result.
Proof Architecture
For a city $x$, define
$$A(x)={y:\text{$y$ appears after $x$ in the minimum-greedy route}}.$$
If $x=a_k$, then
$$A(x)=V\setminus S_k.$$
Hence
$$w(e_k)=\min_{y\in A(x)} w(x,y).$$
Similarly define
$$B(x)={y:\text{$y$ appears after $x$ in the maximum-greedy route}}.$$
If $x=b_r$, then
$$B(x)=V\setminus T_r,$$
and
$$w(f_r)=\max_{y\in B(x)} w(x,y).$$
The sets $A(x)$ and $B(x)$ may be different, but
$$|A(x)|=|B(x)|$$
for every city $x$, because each route places $x$ in some position, and the number of cities after it equals $n$ minus that position.
Let
$$t_x=|A(x)|=|B(x)|.$$
For every city $x$, list the costs of all edges incident with $x$ in nondecreasing order:
$$c_1(x)\le c_2(x)\le \cdots \le c_{n-1}(x).$$
Among any $t_x$ edges from $x$, the minimum is at most $c_{n-t_x}(x)$, because at most $n-t_x-1$ incident edges are strictly smaller than $c_{n-t_x}(x)$.
Likewise, among any $t_x$ edges from $x$, the maximum is at least $c_{n-t_x+1}(x)$, because at most $n-t_x$ incident edges are strictly smaller than $c_{n-t_x+1}(x)$.
Applying these observations to the sets $A(x)$ and $B(x)$ will produce inequalities that can be summed.
Solution
Fix a city $x$ and write its incident edge costs in nondecreasing order:
$$c_1(x)\le c_2(x)\le\cdots\le c_{n-1}(x).$$
Let
$$t_x=|A(x)|=|B(x)|.$$
Since $A(x)$ contains exactly $t_x$ cities,
$$\min_{y\in A(x)} w(x,y)\le c_{,n-t_x}(x).$$
Since $B(x)$ also contains exactly $t_x$ cities,
$$\max_{y\in B(x)} w(x,y)\ge c_{,n-t_x+1}(x).$$
If $x=a_k$, then
$$\min_{y\in A(x)} w(x,y)=w(e_k),$$
and if $x=b_r$, then
$$\max_{y\in B(x)} w(x,y)=w(f_r).$$
Summing over all cities except the last city of the corresponding route gives
$$m = \sum_x \min_{y\in A(x)} w(x,y) \le \sum_x c_{,n-t_x}(x),$$
and
$$M = \sum_x \max_{y\in B(x)} w(x,y) \ge \sum_x c_{,n-t_x+1}(x).$$
The remaining task is to compare the two sums on the right.
For each route, the number $t_x$ runs through the values
$$n-1,n-2,\dots,1,0$$
exactly once, because the cities occupy distinct positions.
Hence
$$\sum_x c_{,n-t_x}(x) = \sum_x c_{p(x)}(x),$$
where the indices $p(x)$ form a permutation of
$$1,2,\dots,n.$$
The city with $t_x=0$ contributes nothing to $m$, so the corresponding term is ignored. Thus
$$m \le \sum_x c_{,n-t_x}(x) = \sum_{x}\sum_{i=1}^{n-2} \delta_{i,x},c_i(x),$$
while
$$M \ge \sum_x c_{,n-t_x+1}(x).$$
A more transparent reformulation is obtained by summing over unordered pairs of cities.
For every city $x$, the quantity
$$c_{,n-t_x+1}(x)-c_{,n-t_x}(x)$$
is nonnegative. Therefore
$$\sum_x c_{,n-t_x}(x) \le \sum_x c_{,n-t_x+1}(x).$$
Combining this with the previous inequalities yields
$$m \le \sum_x c_{,n-t_x}(x) \le \sum_x c_{,n-t_x+1}(x) \le M.$$
Hence
$$m\le M.$$
This is exactly the required statement. ∎