Competition problem — Algebra — Maths Olympiad Prep

Library / /50 of 61

Algebra Difficulty 7.1 National olympiad, round 2 Prove it Belarus

On planet Automoria there live a (possible infinite) number Automorians. Any Automorian have feelings like love and respect. It is known that
1) each Automorian loves exactly one Automorian and respects exactly one Automorian;
2) if $A$ loves $B$ , then every Automorian respecting $A$ also loves $B$ ;
3) if $A$ respects $B$ , then every Automorian loving $A$ also respects $B$ ;
4) for every Automorian there is somebody loving him.
Is it true that every Automorian respects the Automorian he loves?

Solution

Answer: yes.
Denote by $f(x)$ and $g(x)$ the Automorians whom the Automorian $x$ loves and respects, respectively. The first condition of the problem implies that $f$ and $g$ are well defined functions on the set of Automorians. We have to prove that these functions are equal.

Take any Automorian $x$ , then he respects $g(x)$ , who in turn loves $f(g(x))$ . Using the second condition of the problem we see that this Automorian is also loved by $x$ , thus
$f(g(x)) = f(x). \qquad (1)$
Similarly we get from the third condition that
$g(f(x)) = g(x). \qquad (2)$
The fourth condition implies that the function $f$ must be surjective.

Equation (2) gives $f(g(f(x))) = f(g(x))$ and using (1) we obtain $f(f(x)) = f(x)$ . Since $f$ is surjective, we must have $f(x) = x$ for every Automorian $x$ . Then (1) now gives $g(x) = f(g(x)) = f(x) = x$ and hence $f(x) = g(x) = x$ .

Thus, every Automorian loves and respects himself only.

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.