February 2002 Exam 2 Solutions

A four hour examination. Iranian Olympiad 2001.

1. Let n = 2^{m}+1 and suppose that f_{1}, …, f_{n} are increasing functions defined on [0, 1] with values in [0, 1] which satisfy:

|f_{i}(x) − f_{i}(y)| ≤ |x − y| ∀x, y ∈ [0, 1], 1 ≤ i ≤ n

and f_{i}(0) = 0 for 1 ≤ i ≤ n. Prove that there exist i ≠ j such that for all x ∈ [0, 1] we have |f_{i}(x) − f_{j}(x)| ≤ 1/m. Solution We call a function ϕ : [0, ∞) → [0, ∞)] simple if for any integer n ≥ 1 we have ϕ(n) − ϕ(n − 1) ∈ {0, 1} and for any n ≥ 0, the retriction of ϕ to [n, n + 1] is a linear function.

LEMMA Suppose that g : [0, ∞) → ℝ is an increasing function such that |g(0)| ≤ 1/2 and for every x, y, ≥ 0 we have |g(x) − g(y)| ≤ |x − y|, then there exists a simple function ϕ such that for every x ≥ 0 we have |ϕ(x) − g(x)| ≤ 1/2.

PROOF We will show that either Case 1 For every x ∈ [0, 1] we have |g(x) ≤ 1/2 or Case 2 for every x ∈ [0, 1] we have |g(x) − x| ≤ 1/2.

If we are not in Case 1, then there exists x_{0} ∈ [0, 1] such that |g(x_{r}0)| > 1/2. Since g is an increasing function. g(x_{0}) > 1/2. If Case 2 failed to hold, there would be x_{1} ∈ [0, 1] such that |g(x_{1})−x_{1}| > 1/2. We know that g(x_{1})−g(0) ≤ x_{1} so g(x_{1})−x_{1} ≤ 1/2 which implies that x_{1} −g(x_{1}) > 1/2. These two inequalties yield that

g(x_{0}) + x_{1} − g(x_{1}) > 1

or

g(x_{0}) − g(x_{1}) > 1 − x_{1} ≥ 0.

Since g is an increasing function, x_{0} ≥ x_{1} and it follows from g(x_{0}) − g(x_{1}) ≤ x_{0} − x_{1} that x_{0} > 1 which is absurd and the Lemma is proved.

Now from this lemma it follows that there is a simple function ϕ_{0} such that |g(x) − ϕ_{0}(x)| ≤ 1/2. It is easy to see that ϕ_{0} can be extended to the whole positive half-line. Now define

g_{i}(x) = \{ \begin{matrix}mf_{i}(x/m) & 0 ≤ x ≤ m \\ mf_{i}(1) & x ≥ m. \end{matrix}

If we apply the Lemma to the functions g_{i}, then we see that there exists a simple function ϕ_{i} such that g_{i}(x) − ϕ_{i}(x) ≤ 1/2. However, there are precisely 2^{m} simple functions when restricted to the integral intervals [0, m] so there exist i ≠ j such that ϕ_{i}(x) = ϕ_{j}(x) for all x ∈ [0, m] which shows that f_{i}(x) − f_{j}(x)| ≤ 1/m for all x ∈ [0, 1].

2. In ΔABC let I and I_{a} denote the incentre and the excentre corresponding to the side BC. Suppose that II_{a} meets BC and the circumcircle of ΔABC at A′ and M respectively. Let N be the midpoint^{1} of the arc MBA. Let S, T be the respective intersection points of NI, NI_{a} with the circumcircle of ΔABC. Prove that S, T, A′ are colinear. Solution We first prove a Lemma. LEMMA. Suppose that the circles Γ_{1}, Γ_{2} are tangent at T. Let I be a point of Γ_{1} suppose that the tangent at I meets Γ_{2} at A and M. If T I meets Γ_{2} at K, then K is the midpoint of arc AKM. PROOF Let Δ be a line parallel to AM passing through I. Since there is a homothety centred at T which maps Γ_{1} to Γ_{2} it follows that Δ is tangent to Γ_{1} at K. So K is indeed the midpoint of arc AKM and the lemma is proved.

Now let Γ denote the circumcircle of triangle ABC and C_{1} be a circle which is tangent to AI and Γ. By the lemma, T is the tangency point of C_{1} and Γ. Let C_{2} be a circle which is tangent to Γ and passes through I_{a}. Apply the lemma to deduce that C_{1}, C_{2} intersect at S. What! S? Yes, it was in the question but has been quiet lately. Now invert centred at N sending I to I_{a}. This inversion swaps C_{1}, C_{2} and we deduce that S, T′, A are colinear.

3. We define an n-variable formula to mean a function of n variables x_{1}, …, x_{n} which can be expressed as a composition of the functions max{a, b, c, …} and min{a, b, c, …}. (For example, max{x_{2}, x_{3}, min{x_{1}, x_{2}, max{x_{4}, x_{5}}}}). Suppose that P (x_{1}, …, x_{n}) and Q(x_{1}, …, x_{n}) are two n-variable formulas, and assume that if x_{i} ∈ {0, 1} for every i, then

P (x_{1}, …, x_{n}) = Q(x_{1}, …, x_{n}).

Prove that P ≡ Q (i.e. P and Q agree at all real arguments x_{1}, x_{2}, …, x_{n}). Solution Suppose (for contradiction) that the result is not true. Thus there are real numbers x_{1} < ⋯ < x_{n} such that P (x_{1}, x_{2}, …, x_{n}) < Q(x_{1}, x_{2}, …, x_{n}). By perturbing and relabelling we may assume that x_{1} < x_{2} < ⋯ < x_{n} since min and max are continuous functions. Thus there exist p ≠ q such that x_{p} = P (x_{1}, …, x_{n}) < Q(x_{1}, …, x_{n}) = x_{q}. Now if we replace x_{1}, …, x_{p} by 0 and x_{p+1}, …, x_{n} by 1, and induction shows that P (x′_{1}, …, x′_{n}) = 0 and Q(x′_{1}, …, x′_{n}) = 1 which contradicts our assumption.

1The original says mindpoint, but I feel uneasy about this.