Let $n \ge 4$ be an integer. Find all functions $W : \{1, \dots, n\}^2 \to \mathbb R$ such that for every partition $[n] = A \cup B \cup C$ into disjoint sets, \[ \sum_{a \in A} \sum_{b \in B} \sum_{c \in C} W(a,b) W(b,c) = |A| |B| |C|. \]
Problem
Source: USA January TST for IMO 2016, Problem 2
Tags: algebra, functional equation
17.05.2016 23:00
Of course, $W(k,k)$ is arbitrary for $k \in [n]$. We claim that $W(a,b) = \pm 1$ for any $a \neq b$, with the sign fixed. (These are all solutions.) First, let $X_{abc} = W(a,b)W(b,c)$ for all distinct $a$, $b$, $c$, so the given condition is \[ \sum_{a,b,c \in A \times B \times C} X_{abc} = |A| |B| |C|. \]Consider the given equation with the particular choices * $A = \{1\}$, $B = \{3\}$, $C = \{2,4,\dots,n\}$. * $A = \{2\}$, $B = \{3\}$, $C = \{1,4,\dots,n\}$. * $A = \{1,2\}$, $B = \{3\}$, $C = \{4,\dots,n\}$. Adding the first two and subtracting the second gives $X_{132} + X_{231} = 2$. Similarly, $X_{132} + X_{312} = 2$, and in this way, we get that $X_{231} = X_{312}$. Then, $W(2,3)W(3,1) = W(3,1)W(1,2)$, Clearly, $W(3,1) \neq 0$, or else take $A=\{3\}$, $B=\{1\}$ in the original given to get a contradiction. Thus, $W(1,2) = W(2,3)$. Analogously, for any distinct $a$, $b$, $c$ we have $W(a,b) = W(b,c)$. For $n \ge 4$ this is enough to imply $W(a,b) = \pm 1$ for $a \neq b$ where the choice of sign is the same for all $a$ and $b$.
17.05.2016 23:01
oops sniped by v_Enhance
13.05.2021 17:31
Horrible problem. Solution with awang11. Abbreviate $W(a,b)W(b,c)$ to $abc$ for convenience. Write \begin{align*} 123+124+\cdots+12n &= n-2\\ 124+125+\cdots+12n+134+135+\cdots+13n&=2n-6\\ 134+135+\cdots+13n-123&=n-4\\ 132+134+\cdots+13n&=n-2. \end{align*}Thus $123+132=2$. Note $1,2,3$ could be arbitrary, so $W(a,b)W(b,c)+W(a,c)W(c,b)=2$. By a similar argument, $W(a,b)W(b,c)+W(b,a)W(a,c)=2$, so $W(b,a)W(a,c)=W(a,c)W(c,b)$. We claim that $W(a,c)$ is nonzero: indeed, if $a=1$ and $c=2$, the first equation implies that, so symmetric arguments suffice. So pick arbitrary $a,b,c,d$ and write \[W(b,a)=W(c,b)=W(d,c)=W(b,d)=W(a,b)=W(d,a)=W(c,d)=W(a,c).\]Thus by varying $a,b,c,d$ this implies $W$ is constant when $a,b$ are distinct, so $W\equiv 1$ or $W\equiv -1$ for distinct $a,b$. If $a,b$ are not distinct, $W$ is arbitrary since no equations refer to any $W(k,k)$.