Maths Olympiad Prep

Library / /50 of 63

, 2010

Combinatorics Difficulty 8.7 Shortlist Prove it Turkey

Let AA be the set of points in the plane whose coordinates are integers and let

FF be the collection of all functions from AA to {1,1}\{1, -1\}. We call a function ff in FF perfect if every function gg in FF that differs from ff at finitely many points satisfies the condition
0<d(P,Q)<2010f(P)f(Q)g(P)g(Q)d(P,Q)0 \sum_{0 < d(P,Q) < 2010} \frac{f(P)f(Q) - g(P)g(Q)}{d(P,Q)} \geq 0
where d(P,Q)d(P, Q) denotes the distance between PP and QQ. Show that there exist infinitely many perfect functions that are not translates of each other.

Solution

Let LL be a line in the plane, and let π1\pi_1 and π2\pi_2 be the corresponding open half-planes. We set
fL(P)={1if Pπ1L,1if Pπ2. f_L(P) = \begin{cases} 1 & \text{if } P \in \pi_1 \cup L, \\ -1 & \text{if } P \in \pi_2. \end{cases}
We will show that fLf_L is a perfect function. Then the family {fL:(0,0)L}F\{f_L : (0,0) \in L\} \subset \mathcal{F} consists of infinitely many perfect functions that are not translates of each other.

Let gg be a function in F\mathcal{F} differing from fLf_L at finitely many points, and let
K±={(P,Q):fL(P)fL(Q)g(P)g(Q)=±2 and 0<d(P,Q)<2010}. K_{\pm} = \{(P, Q) : f_L(P)f_L(Q) - g(P)g(Q) = \pm 2 \text{ and } 0 < d(P, Q) < 2010\}.
Then
0<d(P,Q)<2010fL(P)fL(Q)g(P)g(Q)d(P,Q)=(P,Q)K+2d(P,Q)(P,Q)K2d(P,Q) \sum_{0 < d(P,Q) < 2010} \frac{f_L(P)f_L(Q) - g(P)g(Q)}{d(P,Q)} = \sum_{(P,Q) \in K_+} \frac{2}{d(P,Q)} - \sum_{(P,Q) \in K_-} \frac{2}{d(P,Q)}

We will prove that this expression is nonnegative by defining an injection m:KK+m: K_- \to K_+ that satisfies d(m(P,Q))=d(P,Q)d(m(P, Q)) = d(P, Q).

Let (P,Q)K(P, Q) \in K_-. Then fL(P)fL(Q)f_L(P) \neq f_L(Q) and g(P)=g(Q)g(P) = g(Q). Consider the line \ell passing through the points PP and QQ. Let P0=PP_0 = P, P1=QP_1 = Q, and let PiP_i be the unique point on \ell such that d(Pi,Pi1)=d(P,Q)d(P_i, P_{i-1}) = d(P, Q) and PiPi2P_i \neq P_{i-2} for i2i \ge 2, and d(Pi,Pi+1)=d(P,Q)d(P_i, P_{i+1}) = d(P, Q) and PiPi+2P_i \neq P_{i+2} for i1i \le -1.

Since fLf_L and gg differ at finitely many points, we know that fL(Pi)=g(Pi)f_L(P_i) = g(P_i) for all ii with sufficiently large i|i|. In particular, gg changes sign finitely many times, but at least once on \ell. Let kk be the smallest integer such that g(Pk)g(Pk+1)g(P_k) \neq g(P_{k+1}). We define m(P,Q)=(Pk,Pk+1)m(P, Q) = (P_k, P_{k+1}).

(Pk,Pk+1)K+(P_k, P_{k+1}) \in K_+ as fL(Pk)fL(Pk+1)g(Pk)g(Pk+1)=1(1)=2f_L(P_k)f_L(P_{k+1}) - g(P_k)g(P_{k+1}) = 1 - (-1) = 2, and we have d(Pk,Pk+1)=d(P,Q)d(P_k, P_{k+1}) = d(P, Q) by construction. Finally, since (P,Q)(P, Q) is the only pair among (Pi,Pi+1)(P_i, P_{i+1}), iZi \in \mathbb{Z}, satisfying fL(Pi)fL(Pi+1)f_L(P_i) \neq f_L(P_{i+1}), mm is injective.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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