International Mathematics Competition for University StudentsJuly 22 – 28 2018, Blagoevgrad, Bulgaria  
Ivan is Watching You
Day 1
Day 2
Results
Download

Problem 6Problem 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 ij> 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_{2n1}=v_{2n}=e_n. \) For every pair \(\displaystyle (i,j)\) of indices with \(\displaystyle 1\le i,j\le 2n\) and \(\displaystyle ij>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\). 