### International Mathematics Competition for University Students

July 22 – 28 2018, Blagoevgrad, Bulgaria

Home

Results
Individuals
Teams

Official IMC site

### 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$.