International Mathematics Competition
for University Students
2018

IMC2018: Day 2, Problem 6

Problem 6. Let \(\displaystyle k\) be a positive integer. Find the smallest positive integer \(\displaystyle n\) for which there exist \(\displaystyle k\) nonzero vectors \(\displaystyle v_1,\ldots,v_k\) in \(\displaystyle \mathbb R^n\) such that for every pair \(\displaystyle i,j\) of indices with \(\displaystyle |i-j|> 1\) the vectors \(\displaystyle v_i\) and \(\displaystyle v_j\) are orthogonal.

(Proposed by Alexey Balitskiy, Moscow Institute of Physics and Technology and M.I.T.)

Solution. First we prove that if \(\displaystyle 2n+1\le k\) then no sequence \(\displaystyle v_1,\ldots,v_k\) of vectors can satisfy the condition. Suppose to the contrary that \(\displaystyle v_1,\ldots,v_k\) are vectors with the required property and consider the vectors

\(\displaystyle v_1,v_3,v_5,\ldots,v_{2n+1}. \)

By the condition these \(\displaystyle n+1\) vectors should be pairwise orthogonal, but this is not possible in \(\displaystyle \mathbb{R}^n\).

Next we show a possible construction for every pair \(\displaystyle k,n\) of positive integers with \(\displaystyle 2n\ge k\). Take an orthogonal basis \(\displaystyle (e_1,\ldots,e_n)\) of \(\displaystyle \mathbb{R}^n\) and consider the vectors

\(\displaystyle v_1=v_2=e_1, \quad v_3=v_4=e_2, \quad\dots,\quad v_{2n-1}=v_{2n}=e_n. \)

For every pair \(\displaystyle (i,j)\) of indices with \(\displaystyle 1\le i,j\le 2n\) and \(\displaystyle |i-j|>1\) the vectors \(\displaystyle v_i\) and \(\displaystyle v_j\) are distinct basis vectors, so they are orthogonal. Evidently the subsequence \(\displaystyle v_1,v_2,\ldots,v_k\) also satisfies the same property.

Hence, such a sequence of vectors exists if and only if \(\displaystyle 2n\ge k\); that is, for a fixed \(\displaystyle k\), the smallest suitable \(\displaystyle n\) is \(\displaystyle \left\lceil\dfrac{k}{2}\right\rceil\).