Baltic Way 2021 · Problem 6

Let $G = (V, E)$ be a graph with vertex set $V = \{1, 2, \dots, 2n-1\}$ and edge set $E = \{\{i, j\} : |a_i - a_j| = t\}$. Note that $G$ has no odd cycles. Indeed, if $j_1, \dots, j_{2k+1}$ is a cycle, then for all $l = 1, 3, 5, \dots, 2k-1$ the number $a_{jl}$ differs from $a_{j,l}$ by $2t$ or $0$. Hence $a_{j_1}$ differs from $a_{j_{2k+1}}$ by an even multiple of $t$. Therefore there is no edge between $j_1$ and $j_{2k+1}$ contradicting the assumption that $j_1, \dots, j_{2k+1}$ is a cycle.

Since $G$ has no odd cycles, it is bipartite. Therefore $V$ can be split into two disjoint sets $V_1, V_2$ such that there is no edge between any two vertices of $V_1$ and there are no edges between any two vertices in $V_2$. Since $V$ has $2n-1$ elements, one of the sets $V_1, V_2$ has at least $n$ elements. Without loss of generality assume that $V_1$ has at least $n$ elements. Then for $k = 1, 2, \dots, n$ simply define $i_k$ to be the $k$-th least element of $V_1$. $\square$