uniolympiads Ελληνικά

IMC 2018, Day 2, Problem 6

Let kk be a positive integer. Find the smallest positive integer nn for which there exist kk nonzero vectors v1,…,vkv_1, \dots, v_k in Rn\mathbb{R}^n such that for every pair i,ji, j of indices with ∣i−j∣>1|i - j| > 1 the vectors viv_i and vjv_j are orthogonal.

Original from the official PDFLet k be a positive integer. Find the smallest positive integer n for which there exist k nonzero vectors v 1 , . . . , v k in R n such that for every pair i, j of indices with |i − j| > 1 the vectors v i and v j are orthogonal. Problem 6.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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

Solution. First we prove that if 2n+1≤k2n+1 \le k then no sequence v1,…,vkv_1,\dots,v_k of vectors can satisfy the condition. Suppose to the contrary that v1,…,vkv_1,\dots,v_k are vectors with the required property and consider the vectors

v1,v3,v5,…,v2n+1.v_1, v_3, v_5, \dots, v_{2n+1}.
By the condition these n+1n+1 vectors should be pairwise orthogonal, but this is not possible in Rn\mathbb{R}^n.

Next we show a possible construction for every pair k,nk,n of positive integers with 2n≥k2n \ge k. Take an orthogonal basis (e1,…,en)(e_1,\dots,e_n) of Rn\mathbb{R}^n and consider the vectors

v1=v2=e1,v3=v4=e2,…,v2n−1=v2n=en.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 (i,j)(i,j) of indices with 1≤i,j≤2n1 \le i,j \le 2n and ∣i−j∣>1|i-j| > 1 the vectors viv_i and vjv_j are distinct basis vectors, so they are orthogonal. Evidently the subsequence v1,v2,…,vkv_1, v_2, \dots, v_k also satisfies the same property.

Hence, such a sequence of vectors exists if and only if 2n≥k2n \ge k; that is, for a fixed kk, the smallest suitable nn is ⌈k2⌉\left\lceil\dfrac{k}{2}\right\rceil.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?