Competition problem — Algebra — Maths Olympiad Prep

Library / /2 of 12

Algebra Difficulty 4.7 AIME Prove it Bulgaria

Let $A$ be a set with $n \ge 2$ elements and let $f_1, \dots, f_k : A \to \mathbb{R}$ be functions. Prove that there exist functions $g_1, \dots, g_{n-1} : A \to \mathbb{R}$ such that
$\max_{1 \le i \le k} |f_i(x) - f_i(y)| = \max_{1 \le i \le n-1} |g_i(x) - g_i(y)|$
for any $x, y \in A$ .

Solution

Let $A = \{a_1, a_2, \dots, a_n\}$ and set
$d(x, y) = \max_{1 \le i \le k} |f_i(x) - f_i(y)|, \quad g_i(x) = d(x, a_i) - d(a_i, a_i), \quad 1 \le i \le n-1$
and $d'(x, y) = \max_{1 \le i \le n-1} |g_i(x) - g_i(y)|$ . Since
$|g_i(x) - g_i(y)| = |d(x, a_i) - d(y, a_i)| \le d(x, y) \quad (\text{why?})$
then $d'(x, y) \le d(x, y)$ . On the other hand,
$d(a_j, a_i) = g_i(a_j) - g_i(a_i) \le d'(a_j, a_i), \quad 1 \le i \le n-1, 1 \le j \le n$

d(a_n, a_n) = 0 = d'(a_n, a_n) \text{ and hence } d'(x, y) = d(x, y).

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.