functievergelijking

Opgave - BaMO 1991 vraag 4

Bewijs dat er geen bijectie $f\{1,2,3,\ldots\}\rightarrow\{0,1,2,\ldots\}$ bestaat die voldoet aan $f(mn)=f(m)+f(n)+3f(m)f(n)$ voor alle $m,n\in\{1,2,3,\ldots\}$.

Oplossing

Ok, dan wordt ie al iets uitdagender, ja :grin:

Stel dat er wel een bijectieve functie $f$ bestaat die aan de opgave voldoet. Schrijf $A=\{1,4,7,\ldots\}$. Definieer dan de functie $g(n)\{1,2,3,\ldots\}\to A n\mapsto 3f(n)+1$. Duidelijk is $f$ bijectief als en slechts als $g$ bijectief is. Het is niet moelijk na te gaan dat $g(mn) = g(m)g(n)$.

We noemen $p$ een handig priemgetal als het onontbindbaar is in $A$, i.e. als er geen $(m,n)\in \left(A\setminus\{1\}\right)^2$ bestaat waarvoor geldt dat $p = mn$. Uit deze definitie volgt natuurlijk dat als $g(n) = p$ een handig priemgetal is, dan is $n$ een priemgetal (in $\mathbb{N}$).

Zijn $q_1, q_2, q_3, q_4$ nu verschillende priemgetallen (in $\mathbb{N}$) zodat $q_1 \equiv q_2 \equiv q_3 \equiv q_4 \equiv 2\ (\text{mod } 3)$. Dan zijn de getallen $q_iq_j$ allemaal handige priemgetallen en behoren allemaal tot $A$. Bijgevolg moeten (daar $g$ wordt verondersteld bijectief en dus surjectief te zijn) er priemgetallen (waarom dit priemgetallen moeten zijn, staat hierboven vermeld) $p_1, p_2, p_3, p_4$ bestaan zodat $g(p_1) = q_1q_2, g(p_2) = q_3q_4, g(p_3) = q_1q_3, g(p_4) = q_2q_4$. Maar dan is $g(p_1p_2) = g(p_1)g(p_2) = q_1q_2q_3q_4 = g(p_3)g(p_4) = g(p_3p_4)$, dus (daar $g$ wordt verondersteld bijectief en dus injectief te zijn) $p_1p_2 = p_3p_4$. Maar $p_i$ zijn priemgetallen, dus WLOG $p_1 = p_3$, i.e. $q_1q_2 = g(p_1) = g(p_3) = q_1q_3$, dus $q_2 = q_3$, in contradictie met hoe we $q_i$ gekozen hebben.

Yep, dat werkt... het kan ook zo: daar $f(1)=0$ is $f(n)\ge1$ voor $n>1$. Het is duidelijk dat als $n$ niet priem is, dan $f(n)=f(a\cdot b)=f(a)+f(b)+3f(a)f(b)\ge5$. Dus de getallen $a,b,c,d$ met beelden $1,2,3,4$ moeten zeker priemen zijn.

Nu krijgen we: $\begin{cases}f(at)=4f(t)+1 & f(a^2)=5\\ f(bt)=7f(t)+2 & f(b^2)=16 \\ f(ct)=10f(t)+3 & f(c^2)=33 \\ f(dt)=13f(t)+4 & f(d^2)=56 \end{cases}$.

Dan springt het bijna in je oog: $f(c^2)=f(at)$ voor $f(t)=8$, dus is dan $c^2=at$, maar dat kan niet daar $a$ en $c$ beide priemgetallen zijn. :)