uniolympiads English

IMC 2019, Ημέρα 2, Θέμα 8

Let x1,…,xnx_1, \dots, x_n be real numbers. For any set I⊂{1,2,…,n}I \subset \{1, 2, \dots, n\} let s(I)=∑i∈Ixis(I) = \sum_{i \in I} x_i. Assume that the function I↦s(I)I \mapsto s(I) takes on at least 1.8n1.8^n values where II runs over all 2n2^n subsets of {1,2,…,n}\{1, 2, \dots, n\}. Prove that the number of sets I⊂{1,2,…,n}I \subset \{1, 2, \dots, n\} for which s(I)=2019s(I) = 2019 does not exceed 1.7n1.7^n.

Πρωτότυπο από το επίσημο PDFLet x 1 , . . . , x n be real numbers. For any set I ⊂ {1, 2, . . . , n} let s(I) = P x i . i∈I Assume that the function I 7→ s(I) takes on at least 1.8 n values where I runs over all 2 n subsets of {1, 2, . . . , n} . Prove that the number of sets I ⊂ {1, 2, . . . , n} for which s(I) = 2019 does not exceed 1.7 n .

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

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

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

Επίσημη λύση

Proposed by Fedor Part and Fedor Petrov, St. Petersburg State University

Solution. Choose disctint sets I1,…,IA⊂{1,2,…,n}I_1, \ldots, I_A \subset \{1, 2, \ldots, n\} where A≥1.8nA \ge 1.8^n, and let J1,…,JB⊂{1,2,…,n}J_1, \ldots, J_B \subset \{1, 2, \ldots, n\} be all sets so that S(Ji)=2019S(J_i) = 2019; for the sake of contradiction, assume that B≥1.7nB \ge 1.7^n.

Every set I⊂{1,2,…,n}I \subset \{1, 2, \ldots, n\} can be identified with a 0−10-1 vector of length nn: the kkth coordinate in the vector is 11 if k∈Ik \in I. Then s(I)=⟨I,X⟩s(I) = \langle I, X\rangle, where X=(x1,…,xn)X = (x_1, \ldots, x_n) and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle stands for the usual scalar product.

For all ordered pairs (a,b)∈{1,…,A}×{1,…,B}(a, b) \in \{1, \ldots, A\}\times\{1, \ldots, B\} consider the vector Ia−Jb∈{−1,0,1}nI_a - J_b \in \{-1, 0, 1\}^n. By the pigeonhole principle, since AB≥(1.8⋅1.7)n>3nAB \ge (1.8\cdot 1.7)^n > 3^n, there are two pairs (a,b)(a, b) and (c,d)(c, d) such that Ia−Jb=Ic−JdI_a - J_b = I_c - J_d. Multiplying this by XX we get s(Ia)−2019=s(Ic)−2019s(I_a) - 2019 = s(I_c) - 2019; that implies a=ca = c. But then Jb=JdJ_b = J_d, that is, b=db = d, and our pairs coincide. Contradiction.

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

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

Πώς πήγε;