IMC / 1994 / Problems / Day 1, P6

IMC 1994 · Day 1 · P6

Let $f \in C^2[0,N]$ and $|f'(x)| < 1$ , $f''(x) > 0$ for every $x \in [0,N]$ . Let $0 \le m_0 < m_1 < \cdots < m_k \le N$ be integers such that $n_i = f(m_i)$ are also integers for $i = 0,1,\dots,k$ . Denote $b_i = n_i - n_{i-1}$ and $a_i = m_i - m_{i-1}$ for $i = 1,2,\dots,k$ .

a) Prove that $-1 < \frac{b_1}{a_1} < \frac{b_2}{a_2} < \cdots < \frac{b_k}{a_k} < 1.$

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 \le 3 N^{2/3}$ (i.e. there are no more than $3 N^{2/3}$ integer points on the curve $y = f(x)$ , $x \in [0,N]$ ).

Solution (official)

a) For $i = 1,2,\dots,k$ we have $b_i = f(m_i) - f(m_{i-1}) = (m_i - m_{i-1}) f'(x_i)$ for some $x_i \in (m_{i-1}, m_i)$ . Hence $\frac{b_i}{a_i} = f'(x_i)$ and so $-1 < \frac{b_i}{a_i} < 1$ . From the convexity of $f$ we have that $f'$ is increasing and $\frac{b_i}{a_i} = f'(x_i) < f'(x_{i+1}) = \frac{b_{i+1}}{a_{i+1}}$ because of $x_i < m_i < x_{i+1}$ .

b) Set $S_A = \{ j \in \{0,1,\dots,k\} : a_j > A \}$ . Then $N \ge m_k - m_0 = \sum_{i=1}^{k} a_i \ge \sum_{j \in S_A} a_j > A |S_A|$ and hence $|S_A| < N/A$ .

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

IMC 1994 · Day 1 · P6

Similar problems