uniolympiads English

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

Let XX be a set of (2k−4k−2)+1\binom{2k-4}{k-2} + 1 real numbers, k≥2k \ge 2. Prove that there exists a monotone sequence {xi}i=1k⊆X\{x_i\}_{i=1}^{k} \subseteq X such that

∣xi+1−x1∣≥2∣xi−x1∣|x_{i+1} - x_1| \ge 2|x_i - x_1|

for all i=2,…,k−1i = 2, \dots, k - 1.

Πρωτότυπο από το επίσημο PDFLet X be a set of 2k−4 k−2 + 1 real numbers, k ≥ 2. Prove that there exists a monotone sequence {x i } ki=1 ⊆ X such that |x i+1 − x | ≥ 2|x i − x | for all i = 2, . . . , k − 1. [20 points]

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

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

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

Επίσημη λύση

Solution. We prove a more general statement:

Lemma. Let k,l≥2k, l \ge 2, let XX be a set of (k+l−4k−2)+1\binom{k+l-4}{k-2} + 1 real numbers. Then either XX contains an increasing sequence {xi}i=1k⊆X\{x_i\}_{i=1}^k \subseteq X of length kk and

∣xi+1−x1∣≥2∣xi−x1∣∀i=2,…,k−1,|x_{i+1} - x_1| \ge 2|x_i - x_1| \quad \forall i = 2, \ldots, k-1,
or XX contains a decreasing sequence {xi}i=1l⊆X\{x_i\}_{i=1}^l \subseteq X of length ll and
∣xi+1−x1∣≥2∣xi−x1∣∀i=2,…,l−1.|x_{i+1} - x_1| \ge 2|x_i - x_1| \quad \forall i = 2, \ldots, l-1.

Proof of the lemma. We use induction on k+lk+l. In case k=2k = 2 or l=2l = 2 the lemma is obviously true.

Now let us make the induction step. Let mm be the minimal element of XX, MM be its maximal element. Let

Xm={x∈X:x≤m+M2},XM={x∈X:x>m+M2}.X_m = \{x \in X : x \le \frac{m+M}{2}\}, \quad X_M = \{x \in X : x > \frac{m+M}{2}\}.
Since (k+l−4k−2)=(k+(l−1)−4k−2)+((k−1)+l−4(k−1)−2)\binom{k+l-4}{k-2} = \binom{k+(l-1)-4}{k-2} + \binom{(k-1)+l-4}{(k-1)-2}, we can see that either
∣Xm∣≥((k−1)+l−4(k−1)−2)+1,or∣XM∣≥(k+(l−1)−4k−2)+1.|X_m| \ge \binom{(k-1)+l-4}{(k-1)-2} + 1, \quad \text{or} \quad |X_M| \ge \binom{k+(l-1)-4}{k-2} + 1.

In the first case we apply the inductive assumption to XmX_m and either obtain a decreasing sequence of length ll with the required properties (in this case the inductive step is made), or obtain an increasing sequence {xi}i=1k−1⊆Xm\{x_i\}_{i=1}^{k-1} \subseteq X_m of length k−1k-1. Then we note that the sequence {x1,x2,…,xk−1,M}⊆X\{x_1, x_2, \ldots, x_{k-1}, M\} \subseteq X has length kk and all the required properties.

In the case ∣XM∣≥(k+(l−1)−4k−2)+1|X_M| \ge \binom{k+(l-1)-4}{k-2} + 1 the inductive step is made in a similar way. Thus the lemma is proved.

The reader may check that the number (k+l−4k−2)+1\binom{k+l-4}{k-2} + 1 cannot be smaller in the lemma.

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

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

Πώς πήγε;