uniolympiads English

IMC 2015, Ημέρα 1, Θέμα 5

Let n≥2n \ge 2, let A1,A2,…,An+1A_1, A_2, \dots, A_{n+1} be n+1n + 1 points in the nn-dimensional Euclidean space, not lying on the same hyperplane, and let BB be a point strictly inside the convex hull of A1,A2,…,An+1A_1, A_2, \dots, A_{n+1}. Prove that ∠AiBAj>90∘\angle A_iBA_j > 90^\circ holds for at least nn pairs (i,j)(i, j) with 1≤i<j≤n+11 \le i < j \le n + 1.

Πρωτότυπο από το επίσημο PDFLet n ≥ 2 , let A 1 , A 2 , . . . , A n+1 be n + 1 points in the n -dimensional Euclidean space, not lying on the same hyperplane, and let B be a point strictly inside the convex hull of A 1 , A 2 , . . . , A n+1 . Prove that ∠A i BA j > 90 ◦ holds for at least n pairs (i, j) with 1 ≤ i < j ≤ n + 1 .

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

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

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

Επίσημη λύση

(Proposed by Géza Kós, Eötvös University, Budapest)

Solution. Let vi=BAi→\mathbf{v}_i = \overrightarrow{BA_i}. The condition ∠AiBAj>90∘\angle A_iBA_j>90^\circ is equivalent with vi⋅vj<0\mathbf{v}_i\cdot\mathbf{v}_j<0. Since BB is an interior point of the simplex, there are some weights w1,…,wn+1>0w_1,\ldots,w_{n+1}>0 with ∑i=1n+1wivi=0\sum\limits_{i=1}^{n+1} w_i\mathbf{v}_i = \mathbf{0}.

Let us build a graph on the vertices 1,…,n+11,\ldots,n+1. Let the vertices ii and jj be connected by an edge if vi⋅vj<0\mathbf{v}_i\cdot\mathbf{v}_j<0. We show that this graph is connected. Since every connected graph on n+1n+1 vertices has at least nn edges, this will prove the problem statement.

Suppose the contrary that the graph is not connected; then the vertices can be split in two disjoint nonempty sets, say VV and WW such that V∪W={1,2,…,n+1}V\cup W = \{1,2,\ldots,n+1\}. Since there is no edge between the two vertex sets, we have vi⋅vj≥0\mathbf{v}_i\cdot\mathbf{v}_j\ge 0 for all i∈Vi\in V and j∈Wj\in W.

Consider

0=(∑i∈V∪Wwivi)2=(∑i∈Vwivi)2+(∑i∈Wwivi)2+2∑i∈V∑i∈Wwiwj(vi⋅vj).0 = \left(\sum_{i\in V\cup W} w_i\mathbf{v}_i\right)^2 = \left(\sum_{i\in V} w_i\mathbf{v}_i\right)^2 + \left(\sum_{i\in W} w_i\mathbf{v}_i\right)^2 + 2\sum_{i\in V}\sum_{i\in W} w_iw_j(\mathbf{v}_i\cdot\mathbf{v}_j).
Notice that all terms are nonnegative on the right-hand side. Moreover, ∑i∈Vwivi≠0\sum\limits_{i\in V} w_i\mathbf{v}_i\ne\mathbf{0} and ∑i∈Wwivi≠0\sum\limits_{i\in W} w_i\mathbf{v}_i\ne\mathbf{0}, so there are at least two strictly nonzero terms, contradiction.

Remark 1. The number nn in the statement is sharp; if vn+1=(1,1,…,1)\mathbf{v}_{n+1} = (1,1,\ldots,1) and vi=(0,…,0⏟i−1,−1,0,…,0⏟n−i)v_i = (\underbrace{0,\ldots,0}_{i-1},-1,\underbrace{0,\ldots,0}_{n-i}) for i=1,…,ni = 1,\ldots,n then vi⋅vj<0\mathbf{v}_i\cdot\mathbf{v}_j<0 holds only when i=n+1i = n+1 or j=n+1j = n+1.

Remark 2. The origin of the problem is here: http://math.stackexchange.com/questions/476640/n-simplex-in-an-intersection-of-n-balls/789390

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

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

Πώς πήγε;