Maths Olympiad Prep

Library / /33 of 37

Algebra Difficulty 8.4 Shortlist Find the answer

Let n4n \ge 4 be an integer. Find all functions W:{1,,n}2RW : \{1, \dots, n\}^2 \to \mathbb R such that for every partition [n]=ABC[n] = A \cup B \cup C into disjoint sets, aAbBcCW(a,b)W(b,c)=ABC. \sum_{a \in A} \sum_{b \in B} \sum_{c \in C} W(a,b) W(b,c) = |A| |B| |C|.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n4 n \ge 4 be an integer. We need to find all functions W:{1,,n}2R W : \{1, \dots, n\}^2 \to \mathbb{R} such that for every partition [n]=ABC[n] = A \cup B \cup C into disjoint sets, the following condition holds:
aAbBcCW(a,b)W(b,c)=ABC. \sum_{a \in A} \sum_{b \in B} \sum_{c \in C} W(a,b) W(b,c) = |A| |B| |C|.

To solve this, we denote the function W W by f f for simplicity. We start by considering specific partitions of [n][n].

First, consider the partition P({1},{2},{3,4,5,}) P(\{1\}, \{2\}, \{3, 4, 5, \ldots\}) :
f(1,2)f(2,4)+f(1,2)f(2,5)++f(1,2)f(2,n)=(n2)f(1,2)f(2,3). f(1,2)f(2,4) + f(1,2)f(2,5) + \cdots + f(1,2)f(2,n) = (n-2) - f(1,2)f(2,3).

Next, consider the partition P({1},{3},{2,4,5,}) P(\{1\}, \{3\}, \{2, 4, 5, \ldots\}) :
f(1,3)f(3,4)+f(1,3)f(3,5)++f(1,3)f(3,n)=(n2)f(1,3)f(3,2). f(1,3)f(3,4) + f(1,3)f(3,5) + \cdots + f(1,3)f(3,n) = (n-2) - f(1,3)f(3,2).

Now, consider the partition P({1},{2,3},{4,5,}) P(\{1\}, \{2, 3\}, \{4, 5, \ldots\}) :
f(1,2)f(2,4)+f(1,2)f(2,5)++f(1,2)f(2,n)+f(1,3)f(3,4)+f(1,3)f(3,5)++f(1,3)f(3,n)=2(n3). f(1,2)f(2,4) + f(1,2)f(2,5) + \cdots + f(1,2)f(2,n) + f(1,3)f(3,4) + f(1,3)f(3,5) + \cdots + f(1,3)f(3,n) = 2(n-3).

This simplifies to:
(n2)f(1,2)f(2,3)+(n2)f(1,3)f(3,2)=2(n3)    f(1,2)f(2,3)+f(1,3)f(3,2)=2. (n-2) - f(1,2)f(2,3) + (n-2) - f(1,3)f(3,2) = 2(n-3) \implies f(1,2)f(2,3) + f(1,3)f(3,2) = 2.

Similarly, for any distinct a,b,c a, b, c :
f(a,b)f(b,c)+f(a,c)f(c,b)=2. f(a,b)f(b,c) + f(a,c)f(c,b) = 2.

Considering P({3,4,5,},{2},{1}) P(\{3, 4, 5, \ldots\}, \{2\}, \{1\}) , P({2,4,5,},{3},{1}) P(\{2, 4, 5, \ldots\}, \{3\}, \{1\}) , and P({4,5,},{2,3},{1}) P(\{4, 5, \ldots\}, \{2, 3\}, \{1\}) , we get:
f(3,2)f(2,1)+f(2,3)f(3,1)=2, f(3,2)f(2,1) + f(2,3)f(3,1) = 2,
which generalizes to:
f(a,b)f(b,c)+f(b,a)f(a,c)=2. f(a,b)f(b,c) + f(b,a)f(a,c) = 2.

Thus, we see that:
f(a,c)f(c,b)=f(b,a)f(a,c)    f(a,c)=0orf(c,b)=f(b,a). f(a,c)f(c,b) = f(b,a)f(a,c) \implies f(a,c) = 0 \quad \text{or} \quad f(c,b) = f(b,a).

Suppose f(a,c)=0 f(a,c) = 0 for some ac a \neq c . Considering P({a},{c},[n]{a,c}) P(\{a\}, \{c\}, [n] - \{a,c\}) , we get 0=n2 0 = n-2 , a contradiction. Hence, f(c,b)=f(b,a) f(c,b) = f(b,a) for all distinct a,b,c a, b, c .

This implies that f(x,b) f(x,b) and f(b,x) f(b,x) are constants for each b b and all xb x \neq b . Consequently, f(x,y) f(x,y) is a constant k k if xy x \neq y . From the condition 2k2=2 2k^2 = 2 , we find k=1 k = 1 or k=1 k = -1 .

Therefore, all solutions are of the form where W(a,a) W(a,a) can be any value, and for all distinct a,b[n] a, b \in [n] , W(a,b) W(a,b) equals a constant k k , where k=1 k = 1 or k=1 k = -1 .

The answer is: W(a,b)\boxed{W(a,b)} = k \text{} for all distinct } a, b \text{} and } k = 1 \text{} or } k = -1.}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.