Maths Olympiad Prep

Library / /27 of 29

Combinatorics Difficulty 6.9 National olympiad Prove it Silk Road Mathematics Competition

a) In this country there are 10241024 cities, numbered with integers from 00 to 10231023;
b) Two cities with numbers mm and nn are connected by a single road if and only if the binary notations of mm and nn differ in exactly one digit;
c) During the tourist's trip in that country, 88 roads will be closed for repairing.

Prove that the tourist can organize a closed path by working roads of the Compland which passes through every city exactly once.

Solution

Remind that nn-dimensional binary cube (boolean) is a graph with vertices labeled by binary sequences of length nn, and there is an edge between any two vertices if and only if their sequences differ only in one corresponding coordinate (digit).

Then our problem is equivalent to the following: prove that if from a 1010-dimensional binary cube we remove 88 edges, then we always obtain a hamiltonian graph (i.e., a graph having a hamiltonian cycle – a closed path passing through all vertices of the graph exactly once).

By induction on nn let's prove a more general statement:
If from an nn-dimensional binary cube, n>1n > 1, we remove arbitrary (n2)(n-2) edges, then the obtained graph is hamiltonian.

Proof: For n=2n=2 the statement is obvious, there is nothing to remove.

Assume that for n=k>1n = k > 1 the statement is true, and prove it for n=k+1n = k + 1.

Let V={(a0,a1,,ak):ai{0,1},0ik}V = \{(a_0, a_1, \dots, a_k) : a_i \in \{0, 1\}, 0 \le i \le k\} be the set of vertices of the (k+1)(k+1)-dimensional cube C=V,EC = \langle V, E \rangle, where EE is a set of edges. Let's take an arbitrary removed edge eEe \in E. W.l.o.g. we may assume that it connects vertices u=(0,b1,,bk)u = (0, b_1, \dots, b_k) and v=(1,b1,,bk)v = (1, b_1, \dots, b_k).

Then consider the sets of vertices
V0={(0,a1,,ak):ai{0,1},1ik} V^0 = \{(0, a_1, \dots, a_k) : a_i \in \{0, 1\}, 1 \le i \le k\}
and
V1={(1,a1,,ak):ai{0,1},1ik}, V^1 = \{(1, a_1, \dots, a_k) : a_i \in \{0, 1\}, 1 \le i \le k\},
which form a partition of VV; and corresponding subgraphs C0=V0,EV0C^0 = \langle V^0, E \setminus V^0 \rangle and C1=V1,EV1C^1 = \langle V^1, E \setminus V^1 \rangle.

Note that:
1) Subgraphs C0C^0 and C1C^1 are identical to kk-dimensional binary cubes;
2) A mapping (0,a1,,ak)f(1,a1,,ak)(0, a_1, \dots, a_k) \to^f (1, a_1, \dots, a_k) is an isomorphism from C0C^0 to C1C^1.

Let DED \subset E be the set of all removed edges, D=n2=k1|D| = n - 2 = k - 1. Then we have a partition D=D0D1D2D = D_0 \cup D_1 \cup D_2, where DiD_i is the set of edges removed from subgraph CiC^i, i=0,1i = 0, 1, and D2D_2 is the set of removed edges which "connect" C0C^0 and C1C^1. In particular, eD2e \in D_2.

Since f(D0)D1k2|f(D_0) \cup D_1| \le k - 2, then by the induction hypothesis in C1C^1 there is a hamiltonian cycle v=v1,v2,,v2kv = v_1, v_2, \dots, v_{2^k}, which does not use the edges from f(D0)D1f(D_0) \cup D_1. Then u=u1,u2,,u2ku = u_1, u_2, \dots, u_{2^k} is a hamiltonian cycle in C0C^0, where f(ui)=vif(u_i) = v_i for 1i2k1 \le i \le 2^k, not passing through the edges of D0D_0.

u=u1,u2,,ui,vi,vi1,,v1,v2k,v2k1,,vi+1,ui+1,,u2k u = u_1, u_2, \dots, u_i, v_i, v_{i-1}, \dots, v_1, v_{2^k}, v_{2^k-1}, \dots, v_{i+1}, u_{i+1}, \dots, u_{2^k}
is a hamiltonian cycle in CC, not passing through the edges of DD. The statement is proved. \square

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.