IMC 1994/1/6

#1

Έστω $f \in C^2[0,N]$ με |f'(x)| < 1

και

για κάθε $x \in [0,N]$ . Έστω $0 \leqslant m_0 < m_1 < \cdots < m_k \leqslant N$ ακέραιοι ώστε οι n_i = f(m_i)

για $i=0,1,\ldots,k$ να είναι επίσης ακέραιοι. Για $i=1,2,\ldots,k$ ορίζουμε $b_i = n_i - n_{i-1}$ και $a_i = m_i - m_{i-1}$ .

(α) Να δειχθεί ότι $\displaystyle{ -1 < \frac{b_1}{a_1} < \frac{b_2}{a_2} < \cdots < \frac{b_k}{a_k} < 1}$

(β) Να δειχθεί ότι για κάθε A > 1

δεν υπάρχουν περισσότεροι από N/A

δείκτες

με

.

(γ) Να δειχθεί ότι $k \leqslant 3N^{2/3}$ . [Δηλαδή δεν υπάρχουν περισσότερα από $3N^{2/3}$ ακέραια σημεία στην καμπύλη y = f(x)

για $x \in [0,N]$ .]

dement · #2

Για το (α), ανισότητες όπως η $\displaystyle \frac{b_1}{a_1} < \frac{b_2}{a_2}$ αποδεικνύονται με ΘΜΤ (υπάρχουν $\displaystyle \xi_1 \in (m_0,m_1), f'(\xi_1) = \frac{b_1}{a_1}$ και $\displaystyle \xi_2 \in (m_1,m_2), f'(\xi_2) = \frac{b_2}{a_2}$ οπότε $f'(\xi_1) < f'(\xi_2)$ αφού f''(x) > 0

). Οι "ακριανές" ανισότητες είναι άμεση συνέπεια του |f'(x)| < 1

.

Το (β) είναι συνέπεια του $\displaystyle \sum_j a_j \leq N$ . Πράγματι, $\displaystyle N \geq \sum_j a_j \geq \sum_{a_j \geq A} a_j \geq n A \implies n \leq N/A$ όπου

ο αριθμός των δεικτών

με $a_j \geq A$ .

Το (γ) προφανώς ισχύει για N=1

. Έστω $N \geq 2$ .

Mπορούμε να έχουμε το πολύ 2A-2

δείκτες

με $a_j = A, b_j \neq 0$ (υπάρχουν 2A-2

μη μηδενικοί ρητοί με παρονομαστή

στο

). Μαζί με τη μοναδική περίπτωση b_k = 0

, έχουμε το πολύ $\displaystyle 1 + \sum_{j=1}^{A} (2j-2) = A(A-1)+1$ δείκτες με $a_j \leq A$ .

Συμπεραίνουμε ότι ο συνολικός αριθμός των δεικτών (μαζί με τον πρώτο, m_0

) φράσσεται άνω από το $q(A) \equiv 2 + A(A-1) + N/(A+1)$ για κάθε $A \in \mathbb{N}$ .

Ισχύει επίσης ότι φράσσεται άνω από το A^2 + 2N/A

για κάθε $A \geq 1$ . Αυτό επειδή, για $N \geq 2$ , έχουμε $A^2 + 2N/A \geq \max \left( q(A-1), q(A) \right)$ άρα, λόγω κυρτότητας της

, ισχύει $A^2 + 2N/A \geq q(\lfloor A \rfloor)$ .

Τέλος, θέτοντας $A = N^{1/3}$ , έχουμε άνω φράγμα το $3N^{2/3}$ που ολοκληρώνει την απόδειξη.

IMC 1994/1/6

IMC 1994/1/6

Re: IMC 1994/1/6

Μέλη σε σύνδεση