LeetCode Problem 3253

Difficulty: 🟡 Medium
Topics: —

Solution

=== 1996-N5 ===

IMO 1996 Shortlist N5

Origin: ROM

Problem

Let $N_0$ denote the set of nonnegative integers. Find a bijective function $f$ from $N_0$ into $N_0$ such that for all $m, n \in N_0$,

$$f(3mn + m + n) = 4f(m)f(n) + f(m) + f(n).$$

Solution

We first observe that the given functional equation is equivalent to

$$4f((3m + 1)(3n + 1) - 1) + 1 = (4f(m) + 1)(4f(n) + 1).$$

This gives us the idea of introducing a function $g : 3N_0 + 1 \to 4N_0 + 1$ defined as

$$g(x) = 4f\bigl(x-1\bigr) + 1.$$

By the above equality, $g$ will be multiplicative, i.e.,

$$g(xy) = g(x)g(y)$$

for all $x, y \in 3N_0 + 1$.

Conversely, any multiplicative bijection $g$ from $3N_0 + 1$ onto $4N_0 + 1$ gives us a function $f$ with the required property:

$$f(x) = g(3x+1) - 1.$$

It remains to give an example of such a function $g$. Let $P_1, P_2, Q_1, Q_2$ be the sets of primes of the forms $3k+1$, $3k+2$, $4k+1$, and $4k+3$, respectively. It is well known that these sets are infinite. Take any bijection $h$ from $P_1 \cup P_2$ onto $Q_1 \cup Q_2$ that maps $P_1$ bijectively onto $Q_1$ and $P_2$ bijectively onto $Q_2$.

Now define $g$ as follows: $g(1) = 1$, and for $n = p_1 p_2 \cdots p_m$ (the $p_i$’s need not be different) define

$$g(n) = h(p_1) h(p_2) \cdots h(p_m).$$

Note that $g$ is well-defined. Indeed, among the $p_i$’s an even number are of the form $3k+2$, and consequently an even number of $h(p_i)$’s are of the form $4k + 3$. Hence the product of the $h(p_i)$’s is of the form $4k + 1$. Also, it is obvious that $g$ is multiplicative. Thus, the defined $g$ satisfies all the required properties.