EGMO 2012 Problem 6

There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.)

Each person is required to designate one of their friends as their best friend. If $A$ designates $B$ as her best friend, then (unfortunately) it does not follow that $B$ necessarily designates $A$ as her best friend. Someone designated as a best friend is called a 1-best friend. More generally, if $n>1$ is a positive integer, then a user is an $n$-best friend provided that they have been designated the best friend of someone who is an $(n-1)$-best friend. Someone who is a $k$-best friend for every positive integer $k$ is called popular. (a) Prove that every popular person is the best friend of a popular person. (b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person.

Origin. Romania (Dan Schwarz) (rephrasing by Geoff Smith). Remark. The original formulation of this problem was: Given a function $f: X \rightarrow X$, let us use the notations $f^{0}(X):=X, f^{n+1}(X):=f\left(f^{n}(X)\right)$ for $n \geq 0$, and also $f^{\omega}(X):=\bigcap_{n \geq 0} f^{n}(X)$. Let us now impose on $f$ that all its fibres $f^{-1}(y):=\{x \in X \mid f(x)=y\}$, for $y \in f(X)$, are finite. Prove that $f\left(f^{\omega}(X)\right)=f^{\omega}(X)$.