AoPS - Problem

Source: Stars Of Mathematics 2014, Juniors, Problem 3

Tags: algebra, combinatorics

mavropnevma

09.03.2015 15:19

i) Show there exist (not necessarily distinct) non-negative real numbers $a_1,a_2,\ldots,a_{10}$; $b_1,b_2,\ldots,b_{10}$, with $a_k+b_k \leq 4$ for all $1\leq k \leq 10$, such that $\max\{|a_i-a_j|, |b_i-b_j|\} \geq \dfrac{4}{3} > 1$ for all $1\leq i < j \leq 10$. ii) Prove for any (not necessarily distinct) non-negative real numbers $a_1,a_2,\ldots,a_{11}$; $b_1,b_2,\ldots,b_{11}$, with $a_k+b_k \leq 4$ for all $1\leq k \leq 11$, there exist $1\leq i < j \leq 11$ such that $\max\{|a_i-a_j|, |b_i-b_j|\} \leq 1$. (Dan Schwarz)

Let $(a_i,b_i)$ be points on the plane. The condition is that the points lie on or in the triangle with vertices $(0,0), (0,4), (4,0)$, and $\max \{|a_i-a_j|, |b_i-b_j|\}$ is the Chebyshev distance. i) Consider the points $(ik, jk)$ for $0 \le i+j \le 3$, $i,j$ integers, where $k = \frac{4}{3}$. ii) Cover the triangle with ten squares $(i,j)-(i,j+1)-(i+1,j+1)-(i+1,j)$ where $0 \le i+j \le 3$, $i,j$ integers. By Pigeonhole Principle, with $11$ points and $10$ squares, two of the points fall in the same square; their Chebyshev distance is not more than $1$.