Problem B. 5165. (March 2021)

B. 5165. Given a positive integer \(\displaystyle k\), is there a function \(\displaystyle f \colon \mathbb{N} \to \mathbb{N}\), such that

\(\displaystyle f(x) + f\big(f(x)\big) = x + k \)

for all \(\displaystyle x \in \mathbb{N}\)?

Proposed by M. Lovas, Budapest

(6 pont)

Deadline expired on April 12, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Megjegyzés. Nincs egyértelmű megállapodás arról, hogy \(\displaystyle \mathbb{N}\), a "természetes" számok halmaza tartalmazza-e a \(\displaystyle 0\) számot; ezért is szoktuk elkerülni a "természetes számok" kifejezést a feladatok szövegében. Az itt közzétett megoldás eredeti változata az \(\displaystyle \mathbb{N}=\{1,2,\ldots\}\) esetre volt érvényes. A megoldást úgy módosítottuk, hogy mind az \(\displaystyle \mathbb{N}=\{1,2,\ldots\}\), mind az \(\displaystyle \mathbb{N}=\{0,1,2,\ldots\}\) értelmezéssel is változtatás nélkül el lehessen mondani.

Megoldás. Megmutatjuk, hogy ilyen tulajdonságú függvény nem létezik.

Tegyük fel indirekten, hogy mégis van ilyen függvény; ebből a feltevésből ellentmodásra fogunk jutni. Ehhez előbb a függvény néhány egyszerű tulajdonságát fogjuk igazolni.

1. tulajdonság: A függvény injektív: \(\displaystyle x\ne y\) esetén \(\displaystyle f(x)\ne f(y)\).

Bizonyítás: Ha \(\displaystyle f(x)=f(y)\), akkor ezeket az \(\displaystyle f\)-be behelyettesítve \(\displaystyle f(f(x))=f(f(y)\). Emiatt

\(\displaystyle x = f(x)+f(f(x))-k = f(y)+f(f(y))-k = y. \)

Tehát csak akkor lehet \(\displaystyle f(x)=f(y)\) , ha \(\displaystyle x=y\).

2. tulajdonság: Az \(\displaystyle f(f(x))\) függvény injektív.

Bizonyítás: Az 1. tulajdonságot előbb tetszőleges \(\displaystyle x,y\) számokra, majd az \(\displaystyle f(x),f(y)\) értékekre alkalmazva: ha \(\displaystyle x\ne y\), akkor \(\displaystyle f(x)\ne f(y)\), de akkor \(\displaystyle f(f(x))\ne f(f(y))\).

3. tulajdonság:

\(\displaystyle f(x) \le x+k. \)

Bizonyítás: A függvényegyenletből

\(\displaystyle f(x) \le f(x)+f(f(x)) = x+k. \)

4. tulajdonság:

\(\displaystyle f(f(x)) \le \frac{x}{2}+k. \)

Bizonyítás: A 3. tulajdonságot \(\displaystyle x\) helyett \(\displaystyle f(x)\)-szel felírva

\(\displaystyle f(f(x)) \le f(x) + k; \)

ezután a függvényegyenletből

\(\displaystyle 2f(f(x)) = f(f(x))+f(f(x)) \le \big(f(x)+k\big) + f(f(x)) = \big(f(x)+f(f(x))\big)+k = (x+k)+k. \)

A feladat megoldásához tekintsük az

\(\displaystyle f(f(1)),\, f(f(2)),\, \ldots,\, f(f(2k+4)) \)

nemnegatív egész számokat. A 2. tulajdonság miatt ez \(\displaystyle 2k+4\) különböző szám; a 4. tulajdonság szerint ezek mindegyike legfeljebb \(\displaystyle \frac{2k+4}{2}+k=2k+2\). Ez azonban ellentmondás, mert a \(\displaystyle 0,1,2,\ldots,2k+2\) számok közül nem lehetséges \(\displaystyle 2k+4\) különbözőt kiválasztani.

Az indirekt feltevésünkből ellentmondásra jutottuk; nem létezik ilyen \(\displaystyle f(x)\) függvény.

Statistics:

42 students sent a solution.
6 points:	Bán-Szabó Áron, Bognár 171 András Károly, Csizmadia Miklós, Diaconescu Tashi, Duchon Márton, Fekete Richárd, Kalocsai Zoltán, Kercsó-Molnár Anita, Kerekes Boldizsár, Kovács 129 Tamás, Lovas Márton, Márton Kristóf, Metzger Ábris András, Móricz Benjámin, Nádor Benedek, Seres-Szabó Márton, Simon László Bence, Somogyi Dalma, Szanyi Attila, Sztranyák Gabriella, Terjék András József, Tóth 057 Bálint, Velich Nóra, Virág Rudolf, Zömbik Barnabás.
5 points:	Andó Viola, Baski Bence, Kökényesi Márk Péter, Nagy 551 Levente, Osztényi József, Romaniuc Albert-Iulian, Sógor Bence, Török Ágoston, Varga Boldizsár.
4 points:	1 student.
3 points:	3 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, March 2021