IMC 2003 · Day 2 · P10

The condition (i) of the problem allows us to define a (well-defined) operation $*$ on the set $S$ given by $$a * b = c \quad \text{if and only if} \quad \{a, b, c\} \in F, \text{ where } a \ne b.$$ We note that this operation is still not defined completely (we need to define $a * a$), but nevertheless let us investigate its features. At first, due to (i), for $a \ne b$ the operation obviously satisfies the following three conditions:

(a) $a \ne a * b \ne b$;

(b) $a * b = b * a$;

(c) $a * (a * b) = b$.

What does the condition (ii) give? It claims that

(e') $x * (a * c) = x * y = z = b * c = (x * a) * c$

for any three different $x, a, c$, i.e. that the operation is associative if the arguments are different. Now we can complete the definition of $*$. In order to save associativity for non-different arguments, i.e. to make $b = a * (a * b) = (a * a) * b$ hold, we will add to $S$ an extra element, call it 0, and define

(d) $a * a = 0$ and $a * 0 = 0 * a = a$.

Now it is easy to check that, for any $a, b, c \in S \cup \{0\}$, (a), (b), (c) and (d), still hold, and

(e) $a * b * c := (a * b) * c = a * (b * c)$.

We have thus obtained that $(S \cup \{0\}, *)$ has the structure of a finite Abelian group, whose elements are all of order two. Since the order of every such group is a power of 2, we conclude that $|S \cup \{0\}| = n + 1 = 2^m$ and $n = 2^m - 1$ for some integer $m \ge 1$.

Given $n = 2^m - 1$, according to what we have proven till now, we will construct a family of three-element subsets of $S$ satisfying (i) and (ii). Let us define the operation $*$ in the following manner:

if $a = a_0 + 2 a_1 + \dots + 2^{m-1} a_{m-1}$ and $b = b_0 + 2 b_1 + \dots + 2^{m-1} b_{m-1}$, where $a_i, b_i$ are either 0 or 1, we put $a * b = |a_0 - b_0| + 2 |a_1 - b_1| + \dots + 2^{m-1} |a_{m-1} - b_{m-1}|$.

It is simple to check that this $*$ satisfies (a), (b), (c) and (e'). Therefore, if we include in $F$ all possible triples $a, b, a * b$, the condition (i) follows from (a), (b) and (c), whereas the condition (ii) follows from (e')

The answer is: $n = 2^m - 1$.