IMC 2004, Ημέρα 1, Θέμα 5
Let be a set of real numbers, . Prove that there exists a monotone sequence such that
for all .
Πρωτότυπο από το επίσημο PDF
![Let 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]](/archive/imc/imc-2004-d1-p5.png)
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. We prove a more general statement:
Lemma. Let , let be a set of real numbers. Then either contains an increasing sequence of length and
Proof of the lemma. We use induction on . In case or the lemma is obviously true.
Now let us make the induction step. Let be the minimal element of , be its maximal element. Let
In the first case we apply the inductive assumption to and either obtain a decreasing sequence of length with the required properties (in this case the inductive step is made), or obtain an increasing sequence of length . Then we note that the sequence has length and all the required properties.
In the case the inductive step is made in a similar way. Thus the lemma is proved.
The reader may check that the number cannot be smaller in the lemma.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.