Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 821. (March 2022)

A. 821. \(\displaystyle a)\) Is it possible to find a function \(\displaystyle f\colon \mathbb{N}^2\to \mathbb{N}\) such that for every function \(\displaystyle g\colon \mathbb{N}\to \mathbb{N}\) and positive integer \(\displaystyle m\) there exists \(\displaystyle n \in \mathbb{N}\) such that set \(\displaystyle \big\{k\in \mathbb{N} : f(n,k)=g(k)\big\}\) has at least \(\displaystyle m\) elements?

\(\displaystyle b)\) Is it possible to find a function \(\displaystyle f\colon \mathbb{N}^2\to \mathbb{N}\) such that for every function \(\displaystyle g\colon \mathbb{N}\to \mathbb{N}\) there exists \(\displaystyle n \in \mathbb{N}\) such that set \(\displaystyle \big\{k\in \mathbb{N} \colon f(n,k)=g(k)\big\}\) has an infinite number of elements?

(7 pont)

Deadline expired on April 11, 2022.


Solution. a)

Yes, it exists.

Let \(\displaystyle F_N\) be the set of functions \(\displaystyle f:\mathbb{N}\to \mathbb{N}\) which take everywhere \(\displaystyle 0\) except for the locations \(\displaystyle \{0,1,...,N\}\) and all values are at most \(\displaystyle N\).

It can be seen that \(\displaystyle F_N\) has finitely many elements for each \(\displaystyle N\), so that we can enumerate in sequence first \(\displaystyle F_1\), then \(\displaystyle F_2, F_3, ...\), the members of the total enumeration being together \(\displaystyle f_0, f_1, f_2, ...\)

Let \(\displaystyle f(n,k)=f_n(k)\), we prove that this satisfies the conditions.

For an arbitrary function \(\displaystyle g:\mathbb{N}\to \mathbb{N}\) and \(\displaystyle m\in \mathbb{Z}^+\), let \(\displaystyle N>m\) and \(\displaystyle N>\max\{g(0),g(1),...,g(m-1)\}\).

Then \(\displaystyle F_N\) contains a function \(\displaystyle f\) such that \(\displaystyle f(0)=g(0), f(1)=g(1),...,f(m-1)=g(m-1)\).

This \(\displaystyle f\) is therefore also included in the enumeration \(\displaystyle f_0, f_1,f_2,...\), so there exists \(\displaystyle n\) for which \(\displaystyle g(0)=f(n,0), g(1)=f(n,1),...,g(m-1)=f(n,m-1)\),

i.e., for which the number of elements in \(\displaystyle \{k\in \mathbb{N}: f(n,k)=g(k)\}\) is at least \(\displaystyle m\).

b)

No. We prove this in a similar way to Cantor's diagonal method:

Suppose that such \(\displaystyle f\) exists. Then, we create a function \(\displaystyle g:\mathbb{N}\to \mathbb{N}\) such that \(\displaystyle g(k)\ne f(n,k)\) for any \(\displaystyle n\le k\). Such \(\displaystyle g\) exists, because for each value we have excluded only finitely many of the infinitely many natural numbers that can be included.

For this function \(\displaystyle g\), for any \(\displaystyle n\in \mathbb{N}\) we have \(\displaystyle f(n,k)\ne g(k)\) if \(\displaystyle k\ge n\), so \(\displaystyle f(n,k)=g(k)\) can be satisfied for only finitely many \(\displaystyle k\).

Therefore \(\displaystyle g\) is a counterexample to our conjecture that there exists an \(\displaystyle n\) for which \(\displaystyle \{k\in \mathbb{N}: f(n,k)=g(k)\}\) is infinite.


Statistics:

12 students sent a solution.
7 points:Diaconescu Tashi, Kökényesi Márk Péter, Lovas Márton, Nádor Benedek, Tarján Bernát, Varga Boldizsár.
6 points:Ben Gillott.
3 points:4 students.
1 point:1 student.

Problems in Mathematics of KöMaL, March 2022