Track / Stage 8 / 42 of 180 #1742 of 1964

Problem 1742

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.1 Prove it Team Selection Test for IMO 2011 · Turkey · 2011

Let $A$ and $B$ be sets with $2011^2$ and $2010$ elements, respectively. Show that there is a function $f: A \times A \to B$ satisfying the condition $f(x,y) = f(y,x)$ for all $(x,y) \in A \times A$ such that for every function $g: A \to B$ there exists $(a_1, a_2) \in A \times A$ with $g(a_1) = f(a_1, a_2) = g(a_2)$ and $a_1 \neq a_2$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $p = 2011$ , $A = \{(i,j) : 0 \le i, j < p\}$ and $B = \{k : 0 \le k < p-1\}$ . We define $f$ as follows:
$f((i_1, j_1), (i_2, j_2)) = \begin{cases} \dfrac{j_1 - j_2}{i_1 - i_2} \pmod{p} & \text{if } i_1 \neq i_2 \text{ and } \dfrac{j_1 - j_2}{i_1 - i_2} \neq -1 \pmod{p} \\ 0 & \text{otherwise} \end{cases}$
In other words, we send a pair of points to the slope of the line passing through them unless they lie on a line with slope $\infty$ or $-1$ , in which case we send it to $0$ .

Let $g: A \to B$ be a function. Since $\dfrac{|A|}{|B|} = \dfrac{p^2}{p-1} > p$ , there is a value in $B$ that is taken at least $p+1$ times by $g$ . Since there are exactly $p$ lines with slope equal to this value, there is at least a pair of points lying on the same one of these lines.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.