Not understanding sequences question from 2020 Miklos Schweitzer Competition

Solution 1:

Let $X$ be the set of sequences $x:\Bbb N\to\Bbb N$, and let $F:X\to\Bbb N$ be as stated in the problem. For $x,y\in X$ write $x\perp y$ iff $x(k)\ne y(k)$ for each $k\in\Bbb N$.

Observe first that $F(x)\in\operatorname{ran}x$ for each $x\in X$: if $n\in\Bbb N\setminus\operatorname{ran}x$, and $c_n\in X$ is the constant function $c_n(k)=n$ for all $k\in\Bbb N$, then $x\perp c_n$, so $F(x)\ne F(c_n)=n$. We’ll use this fact a number of times.

Let $X_0=\{x\in X:x\text{ is injective}\}$; for each $x\in X_0$ there is a unique $k_x\in\Bbb N$ such that $x(k_x)=F(x)$. We will show first that $k_x=k_y$ for all $x,y\in X_0$ and hence that there is an $\ell\in\Bbb N$ such that $k_x=\ell$ for each $x\in X_0$, i.e., such that $F(x)=x(\ell)$ for each $x\in X_0$.

Let $x,y\in X_0$, and suppose first that $F(x)\ne F(y)$. Let

$$z:\Bbb N\to\Bbb N:k\mapsto\begin{cases} F(y),&\text{if }F(x)\in\{x(k),y(k)\}\\ F(x),&\text{otherwise.}\\ \end{cases}$$

Then $z\in X$, and $z\perp x$ (since $x$ is injective), so $F(z)\ne F(x)$. However, $$F(z)\in\operatorname{ran}z\subseteq\{F(x),F(y)\}\,,$$ so $F(z)=F(y)$, $z\not\perp y$, and there must be some $k_0\in\Bbb N$ such that $z(k_0)=y(k_0)$.

If $y(k_0)=F(x)$, then $z(k_0)=F(y)\ne F(x)=y(k_0)$, so we must have $y(k_0)\ne F(x)$. But then $z(k_0)=y(k_0)\ne F(x)$, and $z(k_0)\in\{F(x),F(y)\}$, so $y(k_0)=z(k_0)=F(y)$, and hence $k_0=k_y$. Moreover, $z(k_y)=F(y)$ implies that $F(x)\in\{x(k_y),y(k_y)\}=\{x(k_y),F(y)\}$, and $F(x)\ne F(y)$, so $x(k_x)=F(x)=x(k_y)$, and therefore $k_x=k_y$.

Now suppose that $F(x)=F(y)=n$, say, and to get a contradiction suppose that $k_x\ne k_y$. For $m\in\Bbb N\setminus\{n\}$ let

$$z_m:\Bbb N\to\Bbb N:k\mapsto\begin{cases} m,&\text{if }k=k_x\\ n,&\text{otherwise.} \end{cases}$$

Then $z_m\in X$, and $z_m\perp x$, so $F(z_m)\ne F(x)=n$, but $F(z_m)\in\operatorname{ran}z_m=\{m,n\}$, so $F(z_m)=m$. Fix $x'\in X_0$ such that $F(x')\ne n$, and let $n'=F(x')$. (E.g., let $$x':\Bbb N\to\Bbb N:k\mapsto n+1+k\,,$$ or take $x'$ to be any enumeration of $\Bbb N\setminus\{n\}$.) At least one of $k_x$ and $k_y$ is different from $k_{x'}$; without loss of generality $k_x\ne k_{x'}$. Fix $m\in\Bbb N\setminus\{n,n'\}$, and let

$$z':\Bbb N\to\Bbb N:k\mapsto\begin{cases} m,&\text{if }k=k_{x'}\\ n',&\text{otherwise;} \end{cases}$$

then $F(z')=m=F(z_m)$, but $z'\perp z_m$, so $F(z')\ne F(z_m)$, and we have the desired contradiction. Thus, we must have $k_x=k_y$ in this case as well, and it follows that $k_x=k_y$ for all $x,y\in X_0$.

Let $\ell\in\Bbb N$ be such that $k_x=\ell$ (and hence $x(\ell)=F(x)$) for all $x\in X_0$; we want to show that $x(\ell)=F(x)$ for all $x\in X$, so let $x\in X$. For each $n\in\Bbb N$ define $y_n\in X$ by recursion as follows:

$$y_n(k)=\begin{cases} n,&\text{if }k=\ell\\ \min\Big(\Bbb N\setminus\big(\{y_n(j):j<k\}\cup\{n,x(k)\}\big)\Big),&\text{otherwise.} \end{cases}$$

In other words, $y_n(\ell)=n$, and for $k\in\Bbb N\setminus\{n\}$, $y_n(k)$ is the smallest natural number different from $x(k)$ and from all $y_n(j)$ with $j<k$. Then $y_n\in X_0$, so $F(y_n)=y_n(\ell)=n$. If $n\ne x(\ell)$, then $y_n\perp x$, and hence $F(x)\ne F(y_n)=n$. Thus, $F(x)$ must be $x(\ell)$, as desired.

I was led to consider the set $X_0$ by the observation that if we replace $X$ by $Y$, the set of bounded sequences of natural numbers, the result is false. To see this, let $\mathscr{U}$ be a free ultrafilter on $\Bbb N$. Let $y\in Y$; $\operatorname{ran}y$ is finite, so there is a unique $m_y\in\Bbb N$ such that $y^{-1}[\{m_y\}]\in\mathscr{U}$. Let

$$F:Y\to\Bbb N:y\mapsto m_y\,,$$

and for each $y\in Y$ let $U_y=y^{-1}[\{m_y\}]\in\mathscr{U}$.

Let $n\in\Bbb N$. If $c_n$ is the constant sequence defined above, then clearly $F(c_n)=m_{c_n}=n$. Now suppose that $x,y\in Y$; then $U_x\cap U_y\ne\varnothing$, so fix $k\in U_x\cap U_y$. If $x\perp y$, then $F(x)=x(k)\ne y(k)=F(y)$, so $F$ has the desired properties. But $\mathscr{U}$ is free, so $\bigcap\mathscr{U}=\varnothing$, and there is therefore no $\ell\in\Bbb N$ such that $y(\ell)=m_y=F(y)$ for all $y\in Y$.

Thus, the original result must depend in some way on the unbounded sequences, and the simplest unbounded sequences are the injective ones.