Problem
ALG-B2-M01-P029 Rigid differences
#29
★★★★★ Level 5 of 5
Numbers \(u_1,\ldots,u_m\) satisfy \(u_i-u_j\ge i^2-j^2\) for all \(i,j\). Prove that in fact all differences are equal: \(u_i-u_j=i^2-j^2\).
Hint 1. Write the condition twice: for \((i,j)\) and for \((j,i)\).
Hint 2. One gives a lower bound, the other an upper bound.
For the pair \((i,j)\), the condition gives \(u_i-u_j\ge i^2-j^2\). For the pair \((j,i)\), it gives \(u_j-u_i\ge j^2-i^2\), i.e. \(u_i-u_j\le i^2-j^2\). The lower and upper bounds coincide, so \(u_i-u_j=i^2-j^2\).
Module training problem. Method tags: bounds, squeeze, sequence.