Iranian Mathematical Olympiad

Define $f(A)=\max (A)$ when $A$ is finite. Evidently, $f$ is $A$-predictor when $A$ is finite. We extend $f$ to all subsets of $\mathbb{N}$. We say two subsets $A,B$ are equivalent if $B$ is derived from $A$ by adding and deleting a finite number of elements; i.e. $A\Delta B$ is finite. This is an equivalence relation. By the Axiom of Choice, we can select an element from each class of equivalency. For an arbitrary proper subset $A$, let $S_A$ be the selected element from the class of $A$. So, $A\Delta S_A$ is finite. Define $f(A)=\max (A\Delta S_A)$ when $A\ne S_A$ and define $f(S_A)$ arbitrarily. We claim this function is $A$-predictor for all subsets $A\subseteq \mathbb{N}$.

Let $x$ be a natural number such that $x\notin A$. $A$ and $A\cup \{x\}$ are equivalent, so $S_A=S_{A\cup \{x\}}$. So $$f(A\cup \{x\})=f(A\Delta \{x\})=\max ((A\Delta \{x\})\Delta S_A)=\max ((A\Delta S_A)\Delta \{x\}).$$ For $x>\max (A\Delta S_A)$ we have $(A\Delta S_A)\Delta \{x\}=(A\Delta S_A)\cup \{x\}$. therefore $f(A\cup \{x\})=x$ and the claim is proved. □