Problem

Source: Russian TST 2018, Day 8 P2 (Group NG), P3 (Groups A & B)

Tags: combinatorics, graph theory



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.