There are $2^n$ airports, numbered with binary strings of length $n{}$. Any two stations whose numbers differ in exactly one digit are connected by a flight that has a price (which is the same in both directions). The sum of the prices of all $n{}$ flights leaving any station does not exceed 1. Prove that one can travel between any two airports by paying no more than 1.
Problem
Source: Russian TST 2018, Day 8 P2 (Group NG), P3 (Groups A & B)
Tags: combinatorics, graph theory
18.04.2023 22:34
Notation: For $s \in \{0,1\}^n$ and $i \in [n]$ define $s^{(i)}$ to be $s$ with $i$-th coordinate flipped. First, observe that it suffices to show the result for two antipodal points (points which differ in all bits). Once this is shown, given two general points $p, q \in \{0,1\}^n$ we can restrict to the coordinates where $p$ and $q$ differ and use the result for antipodal points. So assume WLOG $x= 0^n, y=1^n$; we want to show there is a path between $x$ and $y$ with total length $\leq 1$. For a permutation $\pi: [n] \rightarrow [n]$ define $\pi_k \in \{0,1\}^n$ to be the string $s$ where $s_i=1$ iff $\pi^{-1}(i) \leq k$. Note that each permutation defines a path from $x$ and $y$ as follows: $x = \pi_0 \rightarrow \pi_1 \rightarrow \cdots \rightarrow \pi_{n-1} \rightarrow \pi_n=y$. We shall show that there exists a permutation $\pi$ for which the length of this path is $\leq 1$. To this end we use LP duality. For $p,q \in \{0,1\}^n$ with Hamming distance $\leq 1$ let $d(p,q)$ be the weight of the edge between $p$ and $q$. Suppose, on the contrary, for every permutation $\pi: [n] \rightarrow [n]$, the length of the corresponding path is $>1$. This gives a system of linear inequalities as follows: For each $\pi \in S_n$, $$\displaystyle \sum_{k=0}^{n-1} d (\pi_k, \pi_{k+1}) > 1$$ For each $s \in \{0,1\}^n$, $$ \displaystyle \sum_{i=1}^{n} d(s, s^{(i)}) \leq 1$$ Our goal is to show this system is infeasible. We have variables for each inequality in the dual system. Let's restrict our values for these dual variables as follows: each inequality of type (i) gets value 1; and for inequalities of type (ii), the value for the inequality corresponding to $s$ depends only on $|s|$. Suppose, for strings $s$ with $|s|=k$, the corresponding inequality gets value $A_k$. Then, we see that in order to produce a dual certificate of infeasibility, we need to satisfy the following inequalities: $A_k + A_{k+1} \geq k!(n-k-1)!$ for all $0 \leq k \leq n-1$ (This term arises as follows: for any edge $e=(s,s^{(i)})$ with $|s|=k, s_i=0$, there are exactly $k!(n-k-1)!$-many permutations $\pi$ for which the edge traversed in the step $\pi_k \rightarrow \pi_{k+1}$ is $e$.) $$ \displaystyle \sum_{k=0}^{n} \dbinom{n}{k} A_k \leq n!$$ Set $A_k = \dfrac{k!(n-k)!}{n+1}$. Let's check both constraints: $$ A_k + A_{k+1} = \dfrac{1}{n+1} (k!(n-k)! + (k+1)!(n-k-1)!= k!(n-k-1)! \dfrac{n-k+k+1}{n+1} = k!(n-k-1)! $$ $$ \displaystyle \sum_{k=0}^{n} \dbinom{n}{k} A_k = \displaystyle \sum_{k=0}^{n} \dfrac{n!}{n+1} = n!$$ This completes the proof.
20.08.2023 16:44
By inductive hypothesis it suffices to show that we can go from any string to its bitwise inverse, and by symmetry it suffices to show that we can go from $0\ldots0$ to $1\ldots1$. The idea is to compute the expected price of a random path as a nonnegative linear combination of the sums of prices of flights leaving a station. The probability that any given edge from a string with $k$ bits equal to $1$ to a string with $k+1$ bits equal to $1$ is used in this path is equal to $\frac{1}{(n-k)\binom{n}{k}}=\frac{1}{(k+1)\binom{n}{k+1}}$. Therefore the idea is to weight every binary string with $k$ bits equal to $1$ with the same nonnegative coefficient, say $x_k$, so that the equations $x_k+x_{k+1}=\frac{1}{(k+1)\binom{n}{k+1}}$ hold for all $0 \leq k<n$, and we have $\sum_{k=0}^n \binom{n}{k}x_k \leq 1$—note that the LHS quantity is an upper bound on the expected value, under the assumption that the sum of flight prices for each station is exactly $1$. It turns out that we have a lot of freedom in doing this. First off, if we can find a nonnegative linear combination that satisfies the system of equations, we will in fact have $\sum_{k=0}^n \binom{n}{k}x_k=1$: if we set the weight of every edge to $1/n$, then it is clear that the expected value is exactly $1$ (since every path has price $1$). Therefore we can ignore this condition. Now, if $n$ is even, set $x_{n/2}=0$ and use the equations to obtain all the other $x_k$. Suppose that this doesn't work, so by symmetry there exists some maximal $i<n/2$ such that $x_i<0$; clearly $i \neq n/2-1$. This means that $$x_i+x_{i+1}<x_{i+1}+x_{i+2} \implies (i+1)\binom{n}{i+1}>(i+2)\binom{n}{i+2} \implies i+1>n-i-1 \implies i>\frac{n}{2}-1,$$but this is false. If $n$ is odd, set $x_{(n-1)/2}=x_{(n+1)/2}=\frac{1}{(n+1)\binom{n}{\frac{n+1}{2}}}$ and use the equations to obtain all the other $x_k$. Suppose that this doesn't work, so by symmetry there exists some maximal $i<(n-1)/2$ such that $x_i<0$. Since $i+2 \leq (n+1)/2 \implies x_{i+2}\geq 0$, this means that $$x_i+x_{i+1}<x_{i+1}+x_{i+2} \implies (i+1)\binom{n}{i+1}>(i+2)\binom{n}{i+2} \implies i+1>n-i-1 \implies i>\frac{n}{2}-1 \implies i\geq\frac{n-1}{2},$$since $n$ is odd, which is also false. Hence this choice of weights works, so we are done. $\blacksquare$