MathLabs

Problem 2

Suppose 997 points are given in the plane. Every segment joining two points has its midpoint coloured red. Prove that there are at least 1991 red points. Find a special case with exactly 1991 red points.
Step 3 of 4: Prove strict interlacing
Previous stepNext step
mi<ni<mi+1(1≤i≤995).m_i<n_i<m_{i+1}\quad(1\le i\le995).
Detailed analysis

Both sequences are strictly increasing. Moreover, yi+1<yi+2y_{i+1}<y_{i+2} gives mi<nim_i<n_i, while yi<yi+1y_i<y_{i+1} gives ni<mi+1n_i<m_{i+1}. Thus all 996 m-values and 995 n-values are distinct.