India — Team Selection Test, 2006

Let $a_1, a_2, a_3$ be integers such that $0 \le a_1, a_2, a_3 \le M$. Let
$$S_k = \left| \sum_{j=1}^{3} u_{jk} a_j \right|, \quad k = 1, 2.$$
Then Cauchy-Schwartz inequality gives
$$S_k \le \sqrt{\sum_{j=1}^{3} a_j^2} \sqrt{\sum_{j=1}^{3} u_{jk}^2} \le \sqrt{3M^2} \sqrt{N^2} = \sqrt{3MN^2}.$$
We have used $a_j^2 \le M^2$ and $\sum_{j=1}^3 u_{jk}^2 \le (\sum_{j=1}^3 |u_{jk}|)^2 \le N^2$.
Since $M$ is a positive integer, $M \ge 1$, so that $\sqrt{(M+1)^3 - 1} \ge \sqrt{3}$. Thus we have
$$0 \le S_k \le MN \sqrt{(M+1)^3 - 1},$$
for $k = 1, 2$. Divide the interval $[0, MN\sqrt{(M+1)^3 - 1}]$ into $(M + N)^3 - 1$ equal parts, each of length $MN/\sqrt{(M+1)^3 - 1}$. If we consider ordered triples $(a_1, a_2, a_3)$ of integers such that $0 \le a_1, a_2, a_3 \le M$, there are $(M+1)^3$ such triples and these give $(M+1)^3$ values for $S_k$. Hence by pigeon-hole principle, we can find two triples $(A_1, A_2, A_3)$ and $(B_1, B_2, B_3)$ such that $0 \le A_1, A_2, A_3, B_1, B_2, B_3 \le M$ and the corresponding $S$-values lie in the same subinterval. Thus
$$|S_k(A_1, A_2, A_3) - S_k(B_1, B_2, B_3)| \le \frac{MN}{\sqrt{(M+1)^3 - 1}} \le \frac{MN}{l},$$
because $l^2 < (M+1)^3$ implies that $l^2 \le (M+1)^3 - 1$. Taking $\xi_j = A_j - B_j$, $j = 1, 2, 3$, we see that $|\xi_j| \le M$ and
$$\left| \sum_{j=1}^{3} u_{jk} \xi_j \right| \le |S_k(A_1, A_2, A_3) - S_k(B_1, B_2, B_3)| \le \frac{MN}{l}.$$
Note that estimate does not depend on $k$ and hence valid for $k = 1, 2$.