IMO 1996 SL C7

Origin: IRE | Category: Combinatorics

Problem

Let $U$ be a finite set and let $f$, $g$ be bijective functions from $U$ onto itself. Let

$$S={w\in U:f(f(w))=g(g(w))},$$

$$T={w\in U:f(g(w))=g(f(w))},$$

and suppose that $U=S\cup T$. Prove that for $w\in U$, $f(w)\in S$ if and only if $g(w)\in S$.

Solution

For convenience, we shall write $f^2$, $fg$, $\ldots$ for the functions $f\circ f$, $f\circ g$, $\ldots$.

We need two lemmas.

Lemma 1

If $f(x)\in S$ and $g(x)\in T$, then $x\in S\cap T$.

Proof

The given condition means that

$$f^3(x)=g^2f(x)$$

and

$$gfg(x)=fg^2(x).$$

Since $x\in S\cup T=U$, we have two cases.

Case 1: $x\in S$.

Then

$$f^2(x)=g^2(x),$$

which also implies

$$f^3(x)=fg^2(x).$$

Therefore

$$gfg(x)=fg^2(x)=f^3(x)=g^2f(x),$$

and since $g$ is a bijection, we obtain

$$fg(x)=gf(x),$$

i.e.,

$$x\in T.$$

Case 2: $x\in T$.

Then

$$fg(x)=gf(x),$$

$$g^2f(x)=gfg(x).$$

It follows that

$$f^3(x)=g^2f(x)=gfg(x)=fg^2(x),$$

and since $f$ is a bijection, we obtain

$$x\in S.$$

Hence $x\in S\cap T$ in both cases.

Similarly, $f(x)\in T$ and $g(x)\in S$ again imply $x\in S\cap T$.

Lemma 2

$$f(S\cap T)=g(S\cap T)=S\cap T.$$

Proof

By symmetry, it is enough to prove

$$f(S\cap T)=S\cap T,$$

or in other words that

$$f^{-1}(S\cap T)=S\cap T.$$

Since $S\cap T$ is finite, this is equivalent to

$$f(S\cap T)\subseteq S\cap T.$$

Let

$$f(x)\in S\cap T.$$

Then if $g(x)\in S$ (since $f(x)\in T$), Lemma 1 gives

$$x\in S\cap T;$$

similarly, if $g(x)\in T$, then by Lemma 1,

$$x\in S\cap T.$$

Now we return to the problem.

Assume that

$$f(x)\in S.$$

$$g(x)\notin S,$$

then

$$g(x)\in T,$$

so from Lemma 1 we deduce that

$$x\in S\cap T.$$

Then Lemma 2 claims that

$$g(x)\in S\cap T$$

too, a contradiction.

Analogously, from

$$g(x)\in S$$

we are led to

$$f(x)\in S.$$

This finishes the proof.