uniolympiads English

IMC 2018, Ημέρα 2, Θέμα 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.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 1. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;