Problem 1478

Solution:

For any person $A$, let $f^{0}(x)=x$, let $f(A)$ be $A$'s best friend, and define $f^{k+1}(A)=f\left(f^{k}(A)\right)$, so any person who is a $k$-best friend is $f^{k}(A)$ for some person $A$; clearly a $k$-best friend is also an $\ell$-best friend for all $\ell<k$. Let $X$ be a popular person. For each positive integer $k$, let $x_{k}$ be a person with $f^{k}\left(x_{k}\right)=X$. Because $X$ only has finitely many friends, infinitely many of the $f^{k-1}\left(x_{k}\right)$ (all of whom designated $X$ as best friend) must be the same person, who must be popular.

If people can have infinitely many friends, consider people $X_{i}$ for positive integers $i$ and $P_{i, j}$ for $i<j$ positive integers. $X_{i}$ designates $X_{i+1}$ as her best friend; $P_{i, i}$ designates $X_{1}$ as her best friend; $P_{i, j}$ designates $P_{i+1, j}$ as her best friend if $i<j$. Then all $X_{i}$ are popular, but $X_{1}$ is not the best friend of a popular person.

Solution:

For any set $S$ of people, let $f^{-1}(S)$ be the set of people who designated someone in $S$ as their best friend. Since each person has only finitely many friends, if $S$ is finite then $f^{-1}(S)$ is finite.

Let $X$ be a popular person and put $V_{0}=\{X\}$ and $V_{k}=f^{-1}\left(V_{k-1}\right)$. All $V_{i}$ are finite and (since $X$ is popular) nonempty.

If any two sets $V_{i}, V_{j}$, with $0 \leq i<j$ are not disjoint, define $f^{i}(x)$ for positive integers $i$ as in Solution 1. It follows $\emptyset \neq f^{i}\left(V_{i} \cap V_{j}\right) \subseteq f^{i}\left(V_{i}\right) \cap f^{i}\left(V_{j}\right) \subseteq V_{0} \cap V_{j-i}$, thus $X \in V_{j-i}$. But this means that $f^{j-i}(X)=X$, therefore $f^{n(j-i)}(X)=X$. Furthermore, if $Y=f^{j-i-1}(X)$, then $f(Y)=X$ and $f^{n(j-i)}(Y)=Y$, so $X$ is the best friend of $Y$, who is popular.

If all sets $V_{n}$ are disjoint, by König's infinity lemma there exists an infinite sequence of (distinct) $x_{i}, i \geq 0$, with $x_{i} \in V_{i}$ and $x_{i}=f\left(x_{i+1}\right)$ for all $i$. Now $x_{1}$ is popular and her best friend is $x_{0}=X$.

If people can have infinitely many friends, proceed as in Solution 1.