uniolympiads English

IMC 1994, Ημέρα 1, Θέμα 6

Let f∈C2[0,N]f \in C^2[0, N] and ∣f′(x)∣<1|f'(x)| < 1, f′′(x)>0f''(x) > 0 for every x∈[0,N]x \in [0, N]. Let 0≤m0<m1<⋯<mk≤N0 \le m_0 < m_1 < \dots < m_k \le N be integers such that ni=f(mi)n_i = f(m_i) are also integers for i=0,1,…,ki = 0, 1, \dots, k. Denote bi=ni−ni−1b_i = n_i - n_{i-1} and ai=mi−mi−1a_i = m_i - m_{i-1} for i=1,2,…,ki = 1, 2, \dots, k.

a) Prove that

−1<b1a1<b2a2<⋯<bkak<1.-1 < \frac{b_1}{a_1} < \frac{b_2}{a_2} < \dots < \frac{b_k}{a_k} < 1.

b) Prove that for every choice of A>1A > 1 there are no more than N/AN/A indices jj such that aj>Aa_j > A.

c) Prove that k≤3N2/3k \le 3N^{2/3} (i.e. there are no more than 3N2/33N^{2/3} integer points on the curve y=f(x)y = f(x), x∈[0,N]x \in [0, N]).

Πρωτότυπο από το επίσημο PDF(25 points) Let f ∈ C 2 [0, N ] and |f 0 (x)| < 1, f 00 (x) > 0 for every x ∈ [0, N ]. Let 0 ≤ m 0 < m 1 < · · · < m k ≤ N be integers such that n i = f (m i ) are also integers for i = 0, 1, . . . , k. Denote b i = n i − n i−1 and a i = m i − m i−1 for i = 1, 2, . . . , k. a) Prove that b 1 b 2 b k −1 < < < ··· < < 1. a 1 a 2 a k b) Prove that for every choice of A > 1 there are no more than N/A indices j such that a j > A. c) Prove that k ≤ 3N 2/3 (i.e. there are no more than 3N 2/3 integer points on the curve y = f (x), x ∈ [0, N ]).

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

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

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

Επίσημη λύση

Solution. a) For i=1,2,…,ki=1,2,\dots,k we have

bi=f(mi)−f(mi−1)=(mi−mi−1)f′(xi)b_i=f(m_i)-f(m_{i-1})=(m_i-m_{i-1})f'(x_i)
for some xi∈(mi−1,mi)x_i\in(m_{i-1},m_i). Hence biai=f′(xi)\dfrac{b_i}{a_i}=f'(x_i) and so −1<biai<1-1<\dfrac{b_i}{a_i}<1. From the convexity of ff we have that f′f' is increasing and biai=f′(xi)<f′(xi+1)=bi+1ai+1\dfrac{b_i}{a_i}=f'(x_i)<f'(x_{i+1})=\dfrac{b_{i+1}}{a_{i+1}} because of xi<mi<xi+1x_i<m_i<x_{i+1}.

b) Set SA={j∈{0,1,…,k} : aj>A}S_A=\{j\in\{0,1,\dots,k\}\ :\ a_j>A\}. Then

N≥mk−m0=∑i=1kai≥∑j∈SAaj>A∣SA∣N\ge m_k-m_0=\sum_{i=1}^ka_i\ge\sum_{j\in S_A}a_j>A|S_A|
and hence ∣SA∣<N/A|S_A|<N/A.

c) All different fractions in (−1,1)(-1,1) with denominators less or equal AA are no more 2A22A^2. Using b) we get k<N/A+2A2k<N/A+2A^2. Put A=N1/3A=N^{1/3} in the above estimate and get k<3N2/3k<3N^{2/3}.

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

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

Πώς πήγε;