Shortlisted

Problems
(with solutions)
 Shortlisted
Problems
(with solutions)

Functional Equations Online Olympiad

30 May 2020
Thanks to all of the personnel below who helped to do this contest and wouldn’t be possible
without them, including: proposals, testing problems, advices, marking schemes, marking
papers, etc. Also we would like to thank Artur Vllahiu for designing the logo of contest.

F(EOO 2020) Personnel (sorted alphabetically by surname):

• Dorlir Ahmeti (Contest Coordinator)
• Christian Bernert
• Silouanos Brazitikos
• Demetres Christofides
• Victor Domı́nguez
• Enkel Hysnelaj
• Athanasios Kontogeorgis
• Valmir Krasniqi
• Papon Tan Lapate
• ThE-dArK-lOrD
• Amir Parvardi
• Aditya Guha Roy
• Carl Schildkraut
• Brandon Wang
 Problems
Algebra

A1
Find all functions f : R → R such that for any real numbers x and y,

2xyf (xy) ≥ (xy)2 + xf (x)f (y 2 ).

A2
Find all functions f : N → N such that for any positive integers m and n,

f (f (m) + n) + f (f (n)) = f (m + f (n)) + f (m + 1)

A3
Let H be a non-empty subset of R, such that H 6= {0}, and such that H is closed under
addition ( it means for all x, y ∈ H we have x + y ∈ H ). Find all functions f : H → R such
that satisfy both of the following conditions:

i ) f (x + y) = f (x) + f (y) for all x, y ∈ H.

ii ) f (x) ≤ f (y) for all x, y ∈ H such that x ≤ y.

A4
Find all functions f : R+ → R such that for any positive real numbers x, y and z,

f (x2 + y 2 + z 2 ) = f (xy) + f (yz) + f (zx)

A5
Find all functions f : R+ → R+ such that for any positive real numbers x and y,

f (x + f (x) + f (y)) = x + f (x + y)

7
A6
Find all functions f : R+ → R+ such that for any positive real numbers x, y and z satisfying
√ √ √
condition x + y = z,

f (x)2 + f (y)2 + f (z)2 = xf (y) + yf (z) + zf (x)

A7
Let n be a fixed positive integer. Find all n-tuples of positive integers a1 , a2 , ..., an , such
that there exist a non-linear function f : R → R, which satisfy the following condition,

f (xa1 1 + xa2 + ... + xann ) = f (x1 )a1 + f (x2 )a2 + ... + f (xn )an

for any real numbers x1 , x2 , ..., xn .

(Note: A linear function is of the form ax + b for all reals x, where a and b are real
constants.)

A8
Find all functions f : R → R such that for any real numbers x and y,

f (2xy + f (x + y)) = xf (y) + yf (x)

8
Combinatorics

C1
Find all functions f : N → R such that for any simple connected planar graph G,

f (V + E) + f (F ) = 2f (E + 1)

where V, E and F are numbers of vertices, edges and faces of the graph G.

C2
Given a group G of people, we define a(G) to be the least number of tables needed such
that each person from the group sits in one of them with no two friends sitting on the same
table, and b(G) to be the least number of tables needed such that each person from the
group sits in one of them with no two enemies sitting on the same table.

Consider all functions f : N → N such that for each group G of n people we have

f (n) 6 f (a(G)) + f (b(G)) and f (2) = 1.

Find all possible values of f (2020).

Note: We assume that for all pair of people in a group, they are either both friends with
each other or both enemies with each other.

C3
A real number c > 0 is given. Ana and Bob play the following game on the x, y-coordinate
plane. First, Bob will choose a function f : R → [0, 2020], then the set of nice points will

be defined as (x, y) ∈ R2 | f (x + f (y)) = y . After this, Ana will choose to stand on one
nice point and then Bob will choose to stand on another one. Atfer this, they will take
turns moving with Ana making the first move. On each of their turn, Bob can move to any
nice point not more than 2020 times from his current position and Ana can move to any
nice point not more than c units from her current position. Ana wins if and only if, after
finetly many turns, she ends up at the same point as Bob. Find the least number c such
that Ana can win no matter how Bob choose the function f , or show that such number c
doesn’t exist.

9
Geometry

G1
Let P be the set of all points on a fixed plane. Find all functions f : P → P such that for
any two different points A and B on the set P, the points f (A), f (B) and MAB are collinear
( where MAB is the midpoint of segment AB ).

G2
Let P be the set of all points on a fixed plane and let O be a fixed point onf this set P. Find
all fucntions f : P \ {O} → P \ {O} such that for all points A, B ∈ P \ {O} with AB = AO,
point f (B) lie on the circle with diameter Of (A).

G3
Let L and P be the sets of all lines and all points on the same fixed plane, respectively. Find
all functions f : L → P such that, for any two non-parallel lines `1 , `2 ∈ L, the points f (`1 ),
f (`2 ) and `1 ∩ `2 are collinear.

G4
Let P be the set of all points on a fixed plane. Find all functions f : P → P such that for
any two different points A and B on the set P, the points A, B, f (A) and f (B) are concyclic
or collinear.

10
Number Theory

N1
Find all functions f : N0 → R such that

f (w2 + x2 + y 2 + z 2 ) = f (w2 + x2 ) + f (y 2 + z 2 )

for all non-negative integers w, x, y and z.

N2
Let k be a fixed positive integer. Find all functions f : N → N such that for any distinct
positive integers a1 , a2 , ..., ak , there exist a permutation of its b1 , b2 , ..., bk such that,

f (a1 ) f (a2 ) f (ak )

+ + ... +
b1 b2 bk

is a positive integer.

N3
Find all functions f : Z → N such that, f (2m + n)! + f (2n + m) is a prime number, for all
integers m and n.

N4
Find all functions f : N → N such that for all positive integers x, y and z,

ϕ(f (xyz) + f (xy + yz + zx − x − y − z + 1) + f (x + y + z − 2)) f (x) + f (y) + f (z)

=
2 3

11
12
 Solutions
Algebra

A1
Find all functions f : R → R such that for any real numbers x and y,

2xyf (xy) ≥ (xy)2 + xf (x)f (y 2 )


x, if x 6= 0
Answer. f (x) = where c is any non-positive constant real number.
c, if x = 0
Solution. The given functions clearly work, so it remains only to prove that no others do.
Write the given condition on x and y as P (x, y). Taking P (1, 1) we have:

2f (1) ≥ 1 + f (1)2 ⇒ 0 ≥ (1 − f (1))2 ⇒ f (1) = 1.

Taking P (x, 1) for x 6= 0 we have:

f (x)
2xf (x) ≥ x2 + xf (x)f (1) = x2 + xf (x) ⇒ xf (x) ≥ x2 ⇒ ≥1
x

Now taking P 1, x1 for x 6= 0 and using last relation we have:

1
 

2 1 f (x) f x2 f (x)
2 = 2f (1) ≥ 1 + xf (x)f ⇒1≥ · 1 ≥1⇒ = 1 ⇒ f (x) = x.
x2 x x2
x

Hence f (x) = x for all x 6= 0. Now taking P (0, x) we have that both sides are equal to 0. If
we take P (x, 0) for x 6= 0 we have 0 ≥ 2x2 f (0) ⇒ 0 ≥ f (0). This gives us the desired result.

13
A2
Find all functions f : N → N such that for any positive integers m and n,

f (f (m) + n) + f (f (n)) = f (m + f (n)) + f (m + 1)


c, if n 6= 1
Answer. f (n) = where c and d are either any positive contstant integers
d, if n = 1
greater then 1 or c = d = 1.

Solution. Taking m = n in the condition, we have

f (f (n)) = f (n + 1). (1)

If f (a) = f (b) then f (a + 1) = f (f (a)) = f (f (b)) = f (b + 1) by relation (1). An easy

induction then shows that f (a + k) = f (b + k) for all positive integers a, b and k such that
f (a) = f (b). In particular, this relation holds for a = f (n), b = n + 1, whence the previous
result implies:
f (f (n) + k) = f (n + 1 + k) (2)

for all positive integers n and k. A double application of relation (2) yields

f (f (n) + m) = f (n + 1 + m) = f (m + 1 + n) = f (f (m) + n) (3)

Thus, by relation (3), relation (1) transforms to f (f (n)) = f (m + 1). Fixing n and varying
m, this immediately implies that f (m) is constant for m ≥ 2 so for some c, d ∈ N we have
f (n) = c if n ≥ 2 and f (1) = d. By f (f (1)) = f (m + 1), we see that if c or d is equal
to 1 then the other one is 1 too, and the constant function 1 clearly works. Otherwise, if
f (1) = d > 1 and f (n) = c > 1 for n ≥ 2, both sides of condition are equal to 2c. It follows
that the functions listed above are the only ones satisfying the equation.

14
A3
Let H be a non-empty subset of R, such that H 6= {0}, and such that H is closed under
addition (for all x, y ∈ H we have x + y ∈ H). Find all functions f : H → R that satisfy
both of the following conditions:

i ) f (x + y) = f (x) + f (y) for all x, y ∈ H.

ii ) f (x) ≤ f (y) for all x, y ∈ H such that x ≤ y.

Answer. f (x) = cx for all x ∈ H, where c is any non-negative constant real number.

Solution. Clearly the type of functions above satisfy the conditions. Now we prove that
these are the only ones. If H = {0}, then it is clear, so we now take H 6= {0}. From first
condition if x ∈ H, then by easy induction we have:

f (nx) = nf (x) for all x ∈ H and any positive integer n. (1)

f (r)
Now let any fixed number r ∈ H \ {0} and lets write c = r . Without loss of generality
assume that r > 0; we will prove that f (x) = cx for all x ∈ H. Let x be any number in the
set H. It is clear that x + mr, mr ∈ H where m is a fixed positive integer such that x + mr
is positive. Now for all positive integers n, there exists a positive integer an such that

n(x + mr)
an ≤ < an + 1 ⇒ an r ≤ n(x + mr) ≤ (an + 1)r.
r

Using second condition we have f (an r) ≤ f (n(x + mr)) ≤ f ((an + 1)r); then from relation
(1) we have:

can r c(an + 1)r

can r = an f (r) ≤ nf (x+mr) ≤ (an +1)f (r) = c(an +1) ⇒ ≤ f (x+mr) ≤ .
n n

an r (an +1)r an r
Now since n ≤ x + mr ≤ n , taking n large enough we have n → x + mr and also
(an +1)r
n → x + mr, hence from the last relation we have c(x + mr) ≤ f (x + mr) ≤ c(x + mr),
which means f (x + mr) = c(x + mr). Now, the first condition with relation (1) gives us
that

c(x + mr) = f (x + mr) = f (x) + f (mr) = f (x) + mf (r) = f (x) + cmr ⇒ f (x) = cx.

Finally, taking any two different numbers x, y ∈ H such that x < y, we should have cx ≤
cy ⇒ c(x − y) ≤ 0 ⇒ c ≥ 0, as desired.

15
A4
Find all functions f : R+ → R such that for any positive real numbers x, y and z,

f (x2 + y 2 + z 2 ) = f (xy) + f (yz) + f (zx)

Answer. f (x) = 0 for all positive real numbers x.

Solution. Clearly f (x) = 0 for all positive real numbers x satisfies the condition. Now we
prove that this is the only one. Denote by P (x, y, z) the given condition.
√ √ √
Taking P ( 2x, 2x, 2x) we have:

f (6x) = 3f (2x) (1)

√ √ √
Taking P (2 x, x, x) we have:

f (6x) = f (x) + 2f (2x) (2)

Substracting (1) and (2) we have:

f (2x) = f (x) (3)

√ √ √
Taking P (4 x, x, x) and using relation (3) we have:

f (18x) = f (x) + f (4x) = f (x) + f (2 · 2x) = f (x) + f (2x) = f (x) + f (x) = 2f (x) (4)

Using relation (1) twice and then relation (3) we have

f (18x) = f (6 · 3x) = 3f (2 · 3x) = 3f (6x) = 3 · 3f (2x) = 9f (2x) = 9f (x) (5)

Finally substracting (4) and (5) we have 2f (x) = 9f (x) ⇒ f (x) = 0 for all x ∈ R+ .

16
A5
Find all functions f : R+ → R+ such that for any positive real numbers x and y,

f (x + f (x) + f (y)) = x + f (x + y)

Answer. f (x) = x for all positive real numbers x.

Solution. Clearly the above function satisfy condition. Lets write with P (x, y) the initial
condition. Adding y + f (y) both sides of initial condition we will have

y + f (y) + f (x + f (x) + f (y)) = x + y + f (x + y) + f (y)

⇒ f (y + f (y) + f (x + f (x) + f (y))) = f (x + y + f (x + y) + f (y)). (1)

Now taking P (x + y, y) we have

f (x + y + f (x + y) + f (y)) = x + y + f (x + 2y).

And taking P (y, x + f (x) + f (y)) we get

f (y + f (y) + f (x + f (x) + f (y))) = y + f (x + y + f (x) + f (y)).

So from last two relations and using (1) we have

f (x + y + f (x) + f (y)) = x + f (x + 2y).

Swapping x and y in the last relation we have

f (x + y + f (x) + f (y)) = y + f (y + 2x).

Subtracting last two relations we have

x + f (x + 2y) = y + f (y + 2x) ⇒ f (x + 2y) − (x + 2y) = f (y + 2x) − (y + 2x).

Claim. f (x + 2n y) − (x + 2n y) = f (y + 2n x) − (y + 2n x) for all positive real numbers x and

any positive integer n.

17
Proof: For n = 1 it is clear from last relation. Now let suppose it is true for all n < k, we
prove it is true also for n = k. From induction hypothesis we have:

f (x + 2k−1 · 2y) − (x + 2k−1 · 2y) = f (2y + 2k−1 x) − (2y + 2k−1 x)

So, it is enough to prove that f (y + 2k x) − (y + 2k x) = f (2y + 2k−1 x) − (2y + 2k−1 x).

Write 2k−1 x = z; we need that f (y + 2z) − (y + 2z) = f (z + 2y) − (z + 2y), which is true
by our base case of n = 1.

Now take any two positive real numbers a, b. We can suppose that a > b, then choose a
sufficiently large positive integer n so that 2n b > a (clearly 2n a > b). Now, pick

2n a − b 2n b − a
x= n
and y = n
4 −1 4 −1

in the claim. This gives f (b) − b = f (a) − a, hence f (x) − x is constant for all positive real
number x. So, f (x) = x + c for all positive real number x and a constant c. Substituting
this into the given condition, we have that f (x + f (x) + f (y)) = 2x + y + 3c and also we
have x + f (x + y) = 2x + y + c, so we have 2x + y + 3c = 2x + y + c ⇒ c = 0. This means
that f (x) = x for all positive real numbers x, and in it clearly works, so this is the only
solution.

18
A6
Find all functions f : R+ → R+ such that for any positive real numbers x, y and z satisfying
√ √ √
condition x + y = z,

f (x)2 + f (y)2 + f (z)2 = xf (y) + yf (z) + zf (x)

x
Answer. f (x) = 2 for all positive real numbers x.

Solution. Write the given condition as P (x, y, z). Fix a positive real number a, and let
m, c be real numbers such that f (a) = ma + c and f (4a) = 4ma + c. We will prove that
1
m= 2 and c = 0, regardless of the value of a, thus implying the desired claim.

Claim. f (n2 a) = mn2 a + c for all n ∈ N.

Proof. We will prove this by induction. Note that this is true for n = 1, 2 by definition.
Now let suppose it is true for all n < k, we will prove it is true also for n = k > 2. Now
clearly the left sides of P (a, (k − 1)2 a, k 2 a) and P ((k − 1)2 a, a, k 2 a) are equal with each
other, so also the right sides of them should be equal, so

af ((k − 1)2 a) + (k − 1)2 af (k 2 a) + k 2 af (a) = (k − 1)2 af (a) + af (k 2 a) + k 2 af ((k − 1)2 a).

Now, using the inductive hypothesis, the above expressions simplify to

a(m(k−1)2 a+c)+(k−1)2 af (k 2 a)+k 2 a(ma+c) = (k−1)2 a(ma+c)+af (k 2 a)+k 2 a(m(k−1)2 a+c).

Now, an easy calculation shows that f (k 2 a) = mk 2 a + c, as desired.

Back to the problem, we can see that for any k ∈ N, P (k 2 a, 4k 2 a, 9k 2 a) using the previous
claim implies that 49k 4 a2 m + 14k 2 ac = 98k 4 a2 m2 + 28k 2 amc + 3c2 . Since this is true for
infinitely many k, we must have 3c2 = 0 =⇒ c = 0 and 49a2 m = 98a2 m2 =⇒ m = 21 , as
x
desired. We are left to prove that f (x) = for all x ∈ R+ satisfy the equation and is thus
2
√ √ √
the only solution. From condition and keeping in mind that x + y = z we will have,
 x 2  y 2  z 2 y z x
+ + =x· + y · + z · ⇔ x2 + y 2 + z 2 = 2(xy + yz + zx)
2 2 2 2 2 2

⇔ x2 + y 2 + z 2 − 2(xy + yz + zx) = 0
√ √ √ √ √ √ √ √ √ √ √ √
⇔ ( x + y + z)( x + y − z)( y + z − x)( z + x − y) = 0, as desired.

19
A7
Let n be a fixed positive integer. Find all n-tuples of positive integers a1 , a2 , ..., an , such
that there exist a non-linear function f : R → R, which satisfy the following condition,

f (xa1 1 + xa2 + ... + xann ) = f (x1 )a1 + f (x2 )a2 + ... + f (xn )an

for any real numbers x1 , x2 , ..., xn .

(Note: A linear function is of the form ax + b for all reals x, where a and b are real
constants.)

Answer. We claim the answer is sequences of length 1, sequences where all mi = 1, and
all sequences of all even terms.

Solution. Part 1. For these sequences, nonlinear solutions exist.

Proof. For n = 1 the equation reduces to f (x)m = f (xm ), a solution of which is f (x) = x2
for all reals. If all mi = 1, this is simply additivity, for which pathological solutions exist
with Hamel bases. If all mi are even, we claim the function f (x) = |x| works. Indeed, we
have f (x) = x for all real x ≥ 0 and

|f (x)| = |x| =⇒ f (x)2k = x2k = f x2k

for all positive integers k, so

n
! n n
X X X
f xm
i
i
= xm
i
i
= f (xi )mi ,
i=1 i=1 i=1

finishing this part.

Part 2. For all other sequences, all solutions are linear (or constant).

Proof. Define g(x) = f (x) − f (0). We first prove the following:

Claim. g is additive over R.

Proof. We first have that, setting all xi to be 0,

n
X
f (0) = f (0)mi . (1)
i=1

20
setting all xi to be 0 except xk (for any 1 ≤ k ≤ n), that

 
n
X
f (xm
k )
k
= f (0)mi  + f (xk )mk ,
i=1,i6=k

which equals

f (xk )mk + f (0) − f (0)mk .

This means that

g (xm
k ) = f (xk )
k mk
− f (0)mk . (2)

Using this in the original equation gives

n
! n
!
X X
g xm
i
i
=f xm
i
i
− f (0)
i=1 i=1
" n
#
X
mi
= f (xi ) − f (0)
i=1
" n #
X
= (g (xm
i )
i
+ f (0) mi
) − f (0)
i=1
n
X n
X
= g (xm
i )+
i
f (0)mi − f (0)
i=1 i=1
n
X
= g (xm
i ).
i

i=1

Without loss of generality, let m1 be odd. Setting all xi to be 0 except x1 , x2 gives

g (xm m2 m1 m2
1 + x2 ) = g (x1 ) + g (x2 ) ,
1

which means that, for all a, b ∈ R with b ≥ 0, g(a + b) = g(a) + g(b). Taking a = −t, b = 2t
with t > 0 gives

g(t) = g(2t) + g(−t) = g(t) + g(t) + g(−t) =⇒ g(−t) = −g(t),

21
which means for s, t > 0,

g(−s) + g(−t) = −g(s) − g(t) = −g(s + t) = g(−s − t),

so additivity holds even when both variables are < 0, finishing the proof.

In particular, g is additive over R≥0 , which gives that, for all real α ≥ 0, and integer n,
g(nα) = ng(α), which implies that, for all rational r > 0,

g(rα) = rg(α).

Let c = f (0) and let x, y ≥ 0 so y ∈ Q. Let m be one of the elements of the sequence {mi }
so that m > 1. By 2, we have that

m  
X m
g xk y m−k = g ((x + y)m )


k
k=0

= (g(x + y) + c)m − cm
= (g(y) + g(x) + c)m − cm
m  
X m
= −cm + (g(x) + c)k g(y)m−k .
k
k=0
m  
X m 
cm (g(x) + c)k g(y)m−k − g xk y m−k


=
k
k=0
m  
X m m−k 
(g(x) + c)k g(1)m−k − g xk .


= y
k
k=0

The right side of this equation is a polynomial in y that equals cm for infinitely many y, so
it is in fact identically equal to cm ; this means that for all 0 ≤ k < m,

(g(x) + c)k g(1)m−k = g xk .

Setting k = 1 gives

(g(x) + c)g(1)m−1 = g(x) =⇒ cg(1)m−1 = g(x) 1 − g(1)m−1 ,

which implies that g is constant or g(1)m−1 = 1 and c = 0. In the former case we are done,
so we restrict our focus to the latter case, for which we may say that for all 0 ≤ k ≤ m,

22
 g(x)k g(1)m−k = g xk .

In particular, for k = 2, we have

g(x)2 g(1)m−2 = g x2 .

As g(1)m−1 = 1, g(1) = ±1. Applying our additivity lemma to z, x2 for any real z, we have
that

g(z + x2 ) = g(z) + g(x2 ) = g(z) ± g(x)2 ,

where the ± sign is identical for all x, z. This means that g is either monotonically increasing
(if g(1) = 1 or m is even) or monotonically decreasing (if g(1) = −1 and m is odd). This
combined with additivity over R gives the desired result.

23
A8
Find all functions f : R → R such that for any real numbers x and y,

f (2xy + f (x + y)) = xf (y) + yf (x)

Answer. f (x) = 0 for all x ∈ R or f (x) = 1 − x for all x ∈ R.

Solution. It is easy to show that the above functions satisfy the condition. We show now
that these are the only ones. Lets write with P (x, y) the initial condition.

Taking P (x, 0) we have

f (f (x)) = xf (0) ∀x ∈ R (1)

Case 1. f (0) 6= 0.

From (1) clearly the function is injective. Taking x = 1 in relation (1) and using

injectivity we have f (f (1)) = f (0) ⇒ f (1) = 0.

Now taking P (x − 1, 1) and using injectivity we have

f (2x − 2 + f (x)) = f (2(x − 1) · 1 + f (x − 1 + 1)) = (x − 1)f (1) + f (x − 1) = f (x − 1)

⇒ 2x − 2 + f (x) = x − 1 ⇒ f (x) = 1 − x ∀x ∈ R

Case 2. f (0) = 0.

Relation (1) transforms to

f (f (x)) = 0 ∀x ∈ R (2)

1 1


Taking P 2, −2 we have

   
1 1
f − =f − + f (0)
2 2
  
1 1 1
=f − +f −
2 2 2
   
1 1 1 1
= f − − f ,
2 2 2 2

which gives that f − 12 = −f 1

2 .

24
Taking P f (x) − 12 , 21 and using relation (2) with the previous relation we have that

   
1 1
f f (x) − = f f (x) − + f (f (x))
2 2
  
1 1 1
= f f (x) − + f f (x) − +
2 2 2
     
1 1 1 1
= f (x) − f + f f (x) −
2 2 2 2

which gives      
1 1 1 1
f f (x) − = − f (x) − f −
2 2 2 2
and thus      
1 1 1
f f (x) − = −2 f (x) − f − ∀x ∈ R. (3)
2 2 2

Claim. f − 21 = −f 1



2 = 0.
1
Proof. Taking P f − 2 , − 12 and using (2) and (3) we have

             
1 1 1 1 1 1 1
f −f − +f f − − =− f f − +f − f −
2 2 2 2 2 2 2
 2
1
=f − ,
2

which implies that

          2
1 1 1 1 1
f −f − −2 f − − f − =f − .
2 2 2 2 2

This gives that

 2 !  2
1 1
f −2f − =f − .
2 2

25
Now taking P f − 12 , −f − 12 and using (2) and (3) and the previous relation we have

 2  2 !
1 1
f − = f −2f −
2 2
 2 !
1
= f −2f − + f (0)
2
 2     !
1 1 1
= f −2f − +f f − −f −
2 2 2
         
1 1 1 1
=f − f −f − −f − f f −
2 2 2 2
         
1 1 1 1
=f − f f −f − f f −
2 2 2 2
= 0,

so f − 12 = f 1



2 = 0 as desired.

Now, (3) becomes

 
1
f f (x) − =0 ∀x ∈ R. (4)
2

Taking P x, − 12 and using (2) we have

         
1 1 1 f (x)
0 = f f −x + f x − = f xf − − f (x) = f −
2 2 2 2

 
f (x)
⇒f − =0 ∀x ∈ R (5)
2

Taking P (x, x) we have

f (2x2 + f (2x)) = 2xf (x) (6)

We show now that f (x) = 0 for all x ∈ R.

Suppose that on the contrary there exists a ∈ R such that f (a) 6= 0.

26
  
Taking P − f (a) 1
2 , 2f (a) and using relations (4) and (5) we have

  
1 f (a) 1
0=f − +f − +
2 2 2f (a)
   
f (a) 1 1 f (a)
=− f + f −
2 2f (a) 2f (a) 2
 
f (a) 1
=− f
2 2f (a)
 
1
⇒f =0
2f (a)

 
Now, taking P 2a2 + f (2a), 2f1(a) and using (2) and (6) we have

   
2

1 2 1
0 = f f 2 2a + f (2a) · + f 2a + f (2a) +
2f (a) 2f (a)
   
2

1 1 2


= f 2a + f (2a) f + f 2a + f (2a)
2f (a) 2f (a)
 
1
=f · 2af (a)
2f (a)
= f (a),

a contradiction. Thus, we have f (x) = 0 for all x ∈ R, finishing the proof.

27
Combinatorics

C1
Find all functions f : N → R such that for any simple connected planar graph G,

f (V + E) + f (F ) = 2f (E + 1)

where V, E and F are numbers of vertices, edges and faces of the graph G.

Answer. f (n) = an + b for all n ∈ N and any constants a, b ∈ R.

Solution. First we show that these all work. We make use of Euler’s formula V −E +F = 2
for any planar graph; this gives

f (V + E) + f (F ) = a(V + E) + b + aF + b = a(V + E + F ) + 2b = 2(a(E + 1) + b) = 2f (E + 1).

Now, we show that on other functions work. First, take n points on a plane which lie on a
line and connect points on the order. This graph is then connected and has n vertices, n − 1
edges and 1 face, so we have

f (2n − 1) + f (1) = 2f (n) ⇒ f (2n − 1) = 2f (n) − f (1).

Now take a convex n − 1-gon (where n ≥ 5) and connect one of its diagonals. This gives us
a graph with n − 1 vertices, n edges and 3 faces, so we have

f (2n − 1) + f (3) = 2f (n + 1) ⇒ f (2n − 1) = 2f (n + 1) − f (3).

From this and the last relation we have

f (3) − f (1)
2f (n + 1) − f (3) = 2f (n) − f (1) ⇒ f (n + 1) − f (n) =
2

for all n ≥ 5. From this we have that function f (n) is linear for n ≥ 5, so there exist
constants a, b ∈ R such that f (n) = an + b for all n ≥ 5. From the last relations we can
easily find that f (1) = a + b and f (3) = 3a + b. Now take a quadrilateral; we have 4 vertices,
4 edges and 2 faces, so we have

f (8) + f (2) = 2f (5) ⇒ 8a + b + f (2) = 2(5a + b) ⇒ f (2) = 2a + b.

Finally, take a convex pentagon and draw two diagonals from same vertex. This gives 5

28
vertices, 7 edges and 4 faces, so we have

f (12) + f (4) = 2f (8) ⇒ 12a + b + f (4) = 2(8a + b) ⇒ f (4) = 4a + b,

so f (n) = an + b for all n ∈ N, as desired.

29
C2
Given a group G of people, we define a(G) to be the least number of tables needed such
that each person from the group sits in one of them with no two friends sitting on the same
table, and b(G) to be the least number of tables needed such that each person from the
group sits in one of them with no two enemies sitting on the same table.

Consider all functions f : N → N such that for each group G of n people we have

f (n) 6 f (a(G)) + f (b(G)) and f (2) = 1.

Find all possible values of f (2020).

Note: We assume that for all pair of people in a group, they are either both friends with
each other or both enemies with each other.

Answer. f (2020) ∈ {1, 2, . . . , 11} and all values in this set are possible.

Solution. Given n > 2, let us write Gn for the group of n people {x1 , . . . , xn } such that xi
and xj are friends if and only if either i 6 dn/2e < j or j 6 dn/2e < i.

Observe that a(Gn ) = 2 by sitting x1 , . . . , xdn/2e on the first table and the rest on the second
table. Obviously we need at least two tables as x1 and xn must sit on different tables.

Observe also that b(Gn ) = dn/2e by sitting xi on the same table with xn−i for each i 6
dn/2e. Obviously we need that many tables as x1 , . . . , xdn/2e must sit on different tables.

From the above, it follows that

f (n) 6 f (dn/2e) + f (2) = f (dn/2e) + 1.

By (strong) induction, it now follows that f (n) 6 dlog2 ne for each n > 2. Indeed this is
true for n = 2 while if it is true for all n such that n 6 2k then it is also true for all n such
that 2k < n 6 2k+1 as
f (n) 6 f (dn/2e) + 1 6 k + 1.

So f (2020) 6 11.

Claim. Let G be a group of n people with a(G) = a and b(G) = b, then we have ab > n.

Proof. Consider a seating arrangement with tables numbered from 1 to a such that no two
friends sit on the same table, and a seating arrangement with tables numbered from 1 to a
such that no enemies sit on the same table. For each person x, consider the ordered pair
(ix , jx ) where ix is the number of table on which x sits in the first arrangement and jx is
the number of table on which x sits on the second arrangement. Note that if x and y are

30
friends then ix 6= iy , while if x and y are enemies then jx 6= jy . So in any case we have
(ix , jx ) 6= (iy , jy ). Therefore every person gets a distinct pair and so the claim follows.

We will now show that f (n) = dlogr ne satisfies the functional equation for all r > 2. This
√
will complete the proof as taking r = k 2020 for k = 1, 2, . . . , 11 we will get f (2020) = k.

This function obviously satisfies f (2) = 1. Furthermore, we also have

f (n) = dlogr ne 6 dlogr abe = dlogr a + logr be 6 dlogr ae + dlogr be = f (a) + f (b).

So f satisfies the functional equation as required.

Another function achieving f (2020) = k, for k = 1, 2, . . . , 11 is


dlog ne n 6 2019
2
f (n) =
k n > 2020

There are a couple of variations of these idea. The proof is similar to the above.

31
C3
A real number c > 0 is given. Ana and Bob play the following game on the x, y-coordinate
plane. First, Bob will choose a function f : R → [0, 2020], then the set of nice points will

be defined as (x, y) ∈ R2 | f (x + f (y)) = y . After this, Ana will choose to stand on one
nice point and then Bob will choose to stand on another one. Atfer this, they will take
turns moving with Ana making the first move. On each of their turn, Bob can move to any
nice point not more than 2020 times from his current position and Ana can move to any
nice point not more than c units from her current position. Ana wins if and only if, after
finetly many turns, she ends up at the same point as Bob. Find the least number c such
that Ana can win no matter how Bob choose the function f , or show that such number c
doesn’t exist.

Answer. c = 4040.

Solution. First, we will show that for c < 4040, Bob can choose a function f so that he
x
can run away from April indefinitely. Consider the function f (x) = 2020{ 2020 }. We can see
that the sets of valid point in this case is {(x, y) | 2020|x, y ∈ [0, 2020)}. The strategy for
Bob is to choose the initial point with at least 4040 higher x-coordinate values than April’s
initial point, then keep moving from (x, y) to (x + 2020, y) every turn. Since April cannot
move to the point 4040 units from the current position, she will only be able to jump to
points with x-coordinate value differ from the current position at most 2020. This means
that, after finitely many turns, the x-coordinate value of April’s position will be at least
2020 less than that of Bob’s position. Thus, Bob will always be able to run away from April.
Now, we will show that April can always chase Bob if c ≥ 4040.

Claim. From any nice point, April can reach any other nice point.

Proof. Let (x0 , y0 ) and (x1 , y1 ) be the coordinates for the start and the end, respectively.
W.l.o.g assume that x1 ≥ x0 . Now, consider the following move pattern: (x, y) → (x0 , y 0 ) =
(x + 2021 − f (f (x + 2021)), f (x + 2021))

We can see that this move is always valid since

(x − x0 )2 + (y − y 0 )2 = (2021 − f (f (x + 2021)))2 + (f (x + 2021) − y)2

≤ 20212 + 20202
< 40402

Moreover, this move will allow April to increase her x-coordinate by k ∈ [1, 2021]. Thus,
after finitely many moves, April will reach a point with higher x-coordinate than x1 for the
first time. Let this point be (x2 , y2 ).

32
Since in the previous position, the x-coordinate position is not more than x1 , we have
x2 − x1 ≤ 2021. Thus,

(x2 − x1 )2 + (y2 − y1 )2 ≤ 20212 + 20202

< 40402

This means that April can move from (x2 , y2 ) to (x1 , y1 ).

Back to the main problem. Let Bi be Bob’s position after his ith move. First, April will
move to B0 in finitely many turn. Let Bob’s position before she make the last move be Bn .
After this, in any of her turns, April will jump from Bk to Bk+2 . We can see that this move
is valid since |Bk Bk+2 | ≤ |Bk Bk+1 | + |Bk+1 Bk+2 | ≤ 4040. Moreover, we can see that they
will meet at B2n . Thus, we are done.

33
Geometry

G1
Let P be the set of all points on a fixed plane. Find all functions f : P → P such that for
any two different points A and B on the set P, the points f (A), f (B) and MAB are collinear
( where MAB is the midpoint of segment AB ).

Answer. f (P ) = P for all P ∈ P or f (P ) = X for all P ∈ P where X is any fixed point.

Solution. Clearly f (P ) = P for all P ∈ P is a solution, so we may henceforth assume f is

not the identity, so there exists a fixed point A such that X = f (A) 6= A. We will show that
f (P ) = X for all P ∈ P. Construct an equilateral triangle ABC such that X is its centroid.
Let Q, R and S be midpoints of segments AB, BC and CA, respectively. Define a point D
such that BCAD is a parallelogram, and let T and U be the midpoints of the segments AD
and BD, respectively. Let E be reflection of point C to the points B. From the condition,
points X = f (A), f (B) and Q are collinear, so f (B) ∈ l(XQ), similarly f (C) ∈ l(XS).

Claim. f (B) 6= C and f (C) 6= B.

Proof. Suppose the contrary; without loss of generality, let f (B) = C. From the condition,
the points C = f (B), f (C) and R are collinear, so f (C) ∈ l(CR), hence f (C) = l(XS) ∩
l(CR) = B. From condition points f (D), C = f (B) and U are collinear, so f (D) ∈ l(CU ).
From condition points f (D), B = f (C) and Q, so f (D) ∈ l(BQ). From condition points
f (D), X = f (A) and T are collinear, so f (D) ∈ l(T X). So f (D) is the intersection of the
lines l(CU ), l(BQ) and l(T X), which clearly cannot happen, as desired.

Now from condition points f (E), f (C) and B are collinear, and from the claim we have
f (E) ∈ l(Bf (C)) = l(XS). Again from condition f (E), X = f (A) and U are collinear, so
f (E) ∈ l(XU ), which means f (E) = l(XS) ∩ l(XU ) = X. Now take any point P different
from A, E and F . Let M and N be midpoints of segments P E and P A, respectively. From
our condition, the points f (P ), X = f (E) and M are collinear, so f (P ) ∈ l(XM ) and also
from condition points f (P ), X = f (A) and N are collinear, so f (P ) ∈ l(XN ). Hence finally
we have f (P ) = l(XM ) ∩ l(XN ) = X, as desired.

34
G2
Let P be the set of all points on a fixed plane and let O be a fixed point on this set P. Find
all fucntions f : P \ {O} → P \ {O} such that for all points A, B ∈ P \ {O} with AB = AO,
point f (B) lie on the circle with diameter Of (A).

Answer. f (P ) = P0 for all P ∈ P \ {O}, where P0 is fixed point on the set P \ {O}.

Solution. Clearly the function above satisfies the condition. We prove that it is the only
one.

Claim. If A, B are different points such that AB < AO and AB < BO, then f (A) = f (B).

Proof. Let l1 and l2 denote the perpendicular bisectors of AO and BO, respectively. Since
AB < BO, we can easily see that B and O must lie on different sides with respect to
l1 . Thus, the circle with center B and radius BO intersects l1 at some point C satisfying
BO = BC. Similarly, we can find a point D ∈ l2 satisfying AO = AD.

Since C ∈ l1 , we must have CO = CA. Similarly, we must have DO = DB. Hence,

• f (C) lies on the circle with diameter Of (B) =⇒ Of (B) ≥ Of (C).

• f (D) lies on the circle with diameter Of (A) =⇒ Of (A) ≥ Of (D).

• f (A) lies on the circle with diameter Of (C) =⇒ Of (C) ≥ Of (A).

• f (B) lies on the circle with diameter Of (D) =⇒ Of (D) ≥ Of (B).

Combining all inequalities gives Of (A) = Of (B) = Of (C) = Of (D). Since f (C) lies on
the circle with diameter Of (B), we must have f (B) = f (C), and since f (A) lies on the
circle with diameter Of (C), we must have f (A) = f (C) = f (B), as desired. 

Finally, for any two different points A and B, let min{OA, OB} = c, and draw a finite-
length path from A to B that does not come closer to O than c units. It is easy to
see that we can choose a finite sequence of points C1 , C2 , . . . , Cn on the path such that
AC1 , C1 C2 , . . . , Cn−1 Cn , Cn B are all shorter than c. Thus, f (A) = f (C1 ) = f (C2 ) = · · · =
f (Cn ) = f (B). Hence, f (A) and f (B) are the same for any A and B and thus f is a fixed
point for any point on the set P \ {O}.

35
G3
Let L and P be the sets of all lines and all points on the same fixed plane, respectively. Find
all functions f : L → P such that, for any two non-parallel lines `1 , `2 ∈ L, the points f (`1 ),
f (`2 ) and `1 ∩ `2 are collinear.

Answer. Given distinct points x, y we write `xy for the unique line containing x and y.
There are two kinds of functions that are solutions to the equation.

• There is point x such that f (`) = x for every line `.

• There are distinct points x, y such that f (`) = x for every line ` 6= `xy , and f (`xy ) = y.

Solution. Claim 1. There is a line ` such that f (`) ∈

/ `.

Proof. Assume for contradiction that f (`) ∈ ` for all line `. Pick a fixed line ` and let
x = f (`). Pick distinct x1 , x2 ∈ ` such that they are also distinct from x and pick a
point x3 ∈
/ `. Since x1 = ` ∩ `xx1 , then x, x1 and f (`xx1 ) are collinear. So f (`xx1 ) ∈ `.
Since also f (`xx1 ) ∈ `xx1 then f (`xx1 ) = ` ∩ `xx1 = x1 . Similarly f (`xx2 ) = x2 . But then
x1 = f (`xx1 ), x2 = f (`xx2 ) and x3 = `xx1 ∩ `xx2 are non-collinear, a contradiction.

Given a line ` we will write S(`) for the set of all lines which are not parallel to ` and which
also pass through f (`). We also write T (`) for the set of all lines which are not parallel to
` and do not pass through f (`).

/ `, then f (`0 ) = x` for all `0 ∈ S(`) except at

Claim 2. Given a line ` such that x` = f (`) ∈
most one.

Proof. Assume for contradiction that f (`1 ) 6= x 6= f (`2 ) for some distinct lines `1 , `2 ∈ S(`).
Since x` = f (`), f (`1 ) and `1 ∩ ` are collinear, then f (`1 ) ∈ `1 . Similarly, f (`2 ) ∈ `2 . But
now f (`1 ), f (`2 ) and x` = `1 ∩ `2 are non-collinear, a contradiction.

/ `, then f (`0 ) = x` for all `0 ∈ T (`).

Claim 3. Given a line ` such that x` = f (`) ∈

Proof. Given `0 ∈ T (`), pick distinct `1 , `2 ∈ S(`) which are non-parallel to `0 and with
f (`1 ) = f (`2 ) = f (`) = x` . Since f (`0 ), x` = f (`1 ) and `1 ∩ ` are collinear, then f (`0 ) ∈ `1 .
Similarly f (`0 ) ∈ `2 . So f (`0 ) = x` as required.

/ `, and a line `0 parallel to ` and not passing

Claim. Given a line ` such that x` = f (`) ∈
through x` , then f (`0 ) = x` .

Proof. Take any line `00 non-parallel to ` and `0 with x` ∈

/ `00 . Then `00 ∈ T (`), so by
Claim 3 f (`1 ) = x` . We also have `0 ∈ T (`00 ) so since x` ∈
/ `00 , again by Claim 3 we have
f (`0 ) = f (`).

36
Now by Claims 1-4 it follows that if there is a point x such that every line except at most
one maps to x. If there is a line ` which does not map to x, by Claims 2-4 it must pass
through x. Furthermore it must map to a point y ∈ ` as otherwise by Claim 2 there would
be other lines mapping to y as well.

37
G4
Let P be the set of all points on a fixed plane. Find all functions f : P → P such that for
any two different points A and B on the set P, the points A, B, f (A) and f (B) are concyclic
or collinear.

Solution. In the following approach there are eight classes of functions satisyfing the
equation. They can be combined into fewer classes but we leave them like this which is the
order in which they are ‘discovered’ by the proof.

Let S = {A : f (A) 6= A}. Given three distinct points X, Y, Z we will write C(X, Y, Z) for
the unique circle/line thourgh these points

Case 1. Assume S = ∅. Then f is the identity function which clearly satisfies the conditions.

Case 2. Assume |S| = 1. Then f is the identity function except at one point. This also
clearly satisfies the conditions.

Case 3. Assume |S| > 2. For each A ∈ S let `A be the line through A and A0 .

Case 3A. Assume the lines `A for A ∈ S are all parallel (we allow the case in which they
are equal).

Case 3Ai. Assume the lines `A for A ∈ S are all equal to a fixed line `. So there is a
fixed line ` such that if A ∈
/ ` then f (A) = A while if A ∈ ` then f (A) ∈ `. Clearly such a
function satisfies the conditions.

Case 3Aii. Two lines `A , `B are (parallel but) not equal. Then A, A0 , B, B 0 cannot be
on the same line so they are concyclic. The center of the circle belongs on the common
perpendicular bisector ` of AA0 and BB 0 . Pick any point X 6= A, B. We may assume
/ `A . If X 0 6= X then X 0 ∈ `X which is parallel to `A . The points A, A0 , X, X 0 are not
X ∈
collinear, so they must be concyclic and the center of this circle is the common perpendicular
bisector of AA0 and XX 0 . So X 0 = g(X) where g is the reflection on `.

So there is a line ` such that f (A) = A or f (A) = g(A) for all A, where g is reflection on `.
Clearly such a function satisfies the conditions.

Case 3B. There are two points A, B with `A and `B non-parallel.

Case 3Bi. A0 = B or B 0 = A. Without loss of generality assume the former. Since `A , `B

are non-parallel, then A, A0 , B 0 are distinct and non-parallel. Let C = C(A, A0 , B 0 ). Given
X ∈ C with X 6= A, B, we must have X ∈ C(A, A0 , X) = C. Given X ∈
/ C we must have
X ∈ C(A, A0 , X) ∩ B, B 0 , X = {B, X}.

Case 3Bi1. If X 0 = X for each X ∈

/ C, then there is a circle C such that f (X) = X for
X∈
/ C and f (X) ∈ C for X ∈ C. Clearly such a function satisfies the conditions.

38
Case 3Bi2. If X 0 = B for some X ∈
/ C. for all Y ∈
/ C we already know that f (Y ) ∈ {Y, B}.
/ C(X, X 0 , B 0 ) we have f (Y ) ∈ {Y, B}. So for all
A similar proof shows that for all Y ∈
Y 6= B, B 0 we have f (Y ) ∈ {Y, B}.

So there is a fixed point B such that every point distinct from B is mapped to itself or B,
while B can be mapped anywhere else. Clearly such a function satisfies the conditions.

Case 3Bii. The points A, A0 , B, B 0 are all distinct. They cannot be collinear, so they are
concyclic. Say C = C(A, A0 , B). We may assume that there is an X ∈
/ C with X 0 6= X as
otherwise we get the conclusion of case 3Bi1. Let O be the point of intersection of AA0 and
BB 0 .

Case 3Bii1. Assume O is outside C and therefore not on the segments AA0 or BB 0 . By the
power of O with respect to C we have (OA)(OA0 ) = (OB)(OB 0 ). Say they are both equal
to R2 and let C 0 be the circle centred at O of radius R. Let g be the inversion on C 0 .

Observe that O0 ∈ `A = C(A, A0 , O) and similarly O0 ∈ `B , so O0 = O.

/ C with C 6= O. Let C1 = C(A, A0 , C). If C ∈ `A , then C1 = `A and since g(C)

Pick C ∈
is on the line OC, then g(C) ∈ `A . If C ∈
/ `A then C1 is a circle. Since (OC)(Og(C)) =
R2 = (OA)(OA0 ) with g(C) on the same line as OC and on the same side of O as C, then
g(C) ∈ C1 . Similarly, g(C) ∈ C2 = C(B, B 0 , C). Since C1 and C2 intersect in at most two
points, then C1 ∩ C2 = {C, g(C)}, so C 0 = C or C 0 = g(C).

/ C such that X 0 6= X. We may assume X ∈

Pick X ∈ / `A . Then C 00 = C(A, A0 , X) is a circle.
Repeating the arguments of the previous paragraph, if C ∈ / C 00 , then C 0 = C or C 0 = g(C).
In particular, we have C 0 = C or C 0 = g(C) for all C 6= A, A0 . Of course A0 = g(A). Also,
A00 = A0 or A00 = g(A0 ) as A0 ∈
/ (X, B, B 0 ).

To conclude this case, there is a circle C 0 such that f (A) = A or f (A) = g(A) for all A,
where g is inversion on C 0 . (Inversion of the centre is undefined so the centre is fixed by
f .) The converse of the power of the point theorem shows that this function satisfies the
conditions.

Case 3Bii2. Assume O is inside C and therefore belongs on both AA0 or BB 0 . By the
power of O with respect to C we have (OA)(OA0 ) = (OB)(OB 0 ). Say they are both equal
to R2 and let C 0 be the circle centred at O of radius R. Let g be the inversion on C 0 followed
by inversion on O.

An entirely similar argument as in Case 3Bii1 with only difference the facts that A0 , B 0 , C 0
belong on the other side of OA, OB, OC, then A, B, C respectively we get that there is a
circle C 0 such that f (A) = A or f (A) = g(A) for all A, where g is inversion on C 0 . (Inversion
of the centre is undefined so the centre is fixed by f .) The converse of the power of the
point theorem shows that this function satisfies the conditions.

39
Number Theory

N1
Find all functions f : N0 → R such that

f (w2 + x2 + y 2 + z 2 ) = f (w2 + x2 ) + f (y 2 + z 2 )

for all non-negative integers w, x, y and z.

Answer. f (n) = cn for any non-negative integer n and any real constant c.

Solution. Clearly the type of functions above satisfy condition. Now we show these are
the only ones. Taking x = y = z = w = 0 we have f (0) = f (0) + f (0) ⇒ f (0) = 0.

Now we prove by induction that f (n) = cn for all non-negative integers n (where c = f (1)).
For n = 0 and n = 1 it is clearly true. Now we show that it is also true for all positive
integer n ≥ 2. Suppose that it is true f (k) = ck for all k < n; we will prove that also
f (n) = cn.

Case 1. n is not a perfect square.

Legendre’s Four Square Theorem says that for all non-negative integer n there exist non-
negative integers x, y, z and w such that n = x2 + y 2 + z 2 + w2 . Since n is not a perfect
square then at least two of the numbers x, y, z and w are not zero; suppose without loss of
generality that they are x and z. Now, we have

x2 + y 2 < x2 + y 2 + z 2 + w2 = n and w2 + z 2 < x2 + y 2 + z 2 + w2 = n,

whence we have f (x2 + y 2 ) = c(x2 + y 2 ) and f (z 2 + w2 ) = c(z 2 + w2 ). This gives

f (n) = f (x2 + y 2 + z 2 + w2 ) = f (x2 + y 2 ) + f (z 2 + w2 ) = c(x2 + y 2 ) + c(w2 + z 2 ) = cn.

Case 2. n is an even perfect square.

Let n = (2r)2 . Since 2r2 < (2r)2 , we have f (2r2 ) = c(2r2 ), so taking x = y = z = w = r we
see that
f (n) = f (4r2 ) = 2f (2r2 ) = 2(c(2r2 )) = c(2r)2 = cn.

40
Case 3. n is an odd perfect square.

Method 1. Let n = (2s + 1)2 . Taking x = 2s + 1, y = z = 0 and w = 1 we will have that

f (4s2 + 4s + 2) = f ((2s + 1)2 ) + f (1) = f ((2s + 1)2 ) + c.

Also, taking x = z = s + 1 and y = w = s we will have that

f (4s2 + 4s + 2) = 2f ((s + 1)2 + s2 ) = 2f (2s2 + 2s + 1).

By last two relations we have

f ((2s + 1)2 ) + c = 2f (2s2 + 2s + 1) ⇒ f ((2s + 1)2 ) = 2f (2s2 + 2s + 1) − c.

Now since 2s2 + 2s + 1 < (2s + 1)2 we have f (2s2 + 2s + 1) = c(2s2 + 2s + 1), which gives
us that

f ((2s + 1)2 ) = 2c(2s2 + 2s + 1) − c = c(4s2 + 4s + 1) = c(2s + 1)2 = cn

as desired.

Method 2. Let n = (2s + 1)2 = (2s)2 + 4s + 1. Recall that Legendre’s Three Square Theorem
says that every number m 6= 4a (8b + 7) can be expressed as the sum of three non-negative
perfect square. Since for any non-negative integers a and b we have 4a (8b + 7) ≡ 0, 3
(mod 4), we know that 4s + 1 6= 4a (8b + 7) for any non-negative integers a and b, whence
we have non-negative integers y, z and w such that 4s + 1 = y 2 + z 2 + w2 .

We can suppose that z 6= 0, so n = (2s)2 + y 2 + z 2 + w2 . Now, as before, we have

(2s)2 + y 2 < (2s)2 + y 2 + z 2 + w2 = n and z 2 + w2 < (2s)2 + y 2 + z 2 + w2 = n,

so we know f ((2s)2 + y 2 ) = c((2s)2 + y 2 ) and f (z 2 + w2 ) = c(z 2 + w2 ). Then, applying the

problem condition with these y, z, w and x = 2s gives us

f (n) = f ((2s)2 +y 2 +z 2 +w2 ) = f ((2s)2 +y 2 )+f (z 2 +w2 ) = c((2s)2 +y 2 )+c(z 2 +w2 ) = cn.

Comment. There are other possible way to solve the problem. For example to prove
f (n) = cn only for perfect squares n using induction with the identity n2 + 1 + n2 + 1 =
(n + 1)2 + 02 + (n − 1)2 + 02 . Than finishing using Legendre’s Four Square Theorem.

41
N2
Let k be a fixed positive integer. Find all functions f : N → N such that for any distinct
positive integers a1 , a2 , ..., ak , there exist a permutation of its b1 , b2 , ..., bk such that,

f (a1 ) f (a2 ) f (ak )

+ + ... +
b1 b2 bk

is a positive integer.

Answer. f (n) = ng(n) for all positive integers n and any function g : N → N.

Solution. Clearly the the type of functions above satisfy condition, since if we take bi = ai
forall i = 1, 2, ..., k the expression is equal with g(a1 ) + g(a2 ) + ... + g(ak ), which clearly is a
positive integer. We show now these are the only ones. It remains to prove n | f (n) for all
positive integers n and the result will follow. Let Pk (a1 , a2 , . . . , ak ) denote the statement of
the problem.

Claim. Let 2k + 1 positive integers x1 , x2 , . . . , xk , y1 , y2 , . . . , yk , p be such that p is prime,

p | y1 and p - xi , yi for every i ∈ {2, 3, . . . , k}. If

x1 x1 xk
+ 0 + ··· + 0 = m
y10 y2 yk

is an integer for some permutation y10 , y20 , . . . , yk0 , then y10 = y1 and p | x1 .

Proof. Let l such that yl0 = y1 , and let

 
xl x1 xl−1 xl+1 xk q
=m− 0 + ··· + 0 + 0 + ··· + 0 =
y1 y1 yl−1 yl+1 yk r

for some relatively prime integers q and r. Since p - yi for i 6= 1, r must not be divisible by
p either. Now, xl /y1 = q/r, and p | y1 , p - r, so p | xl . Since p - x2 , x3 , . . . , xn the only way
for this to happen is that l = 1 and p | x1 , as desired. 

For any pairwise distinct positive integers a1 , a2 , . . . , ak−1 , choose a prime p larger than ai
and f (ai ) for all i = 1, 2, . . . , k − 1. By the claim, Pk (a1 , a2 , . . . , ak−1 , p) yields bk = p and
p | f (p). So
f (a1 ) f (a2 ) f (ak−1 )
+ + ··· +
b1 b2 bk−1
is an integer itself, where b1 , b2 , . . . , bk−1 is a permutation of a1 , a2 , . . . , ak−1 . This proves
that Pk−1 (a1 , a2 , . . . , ak−1 ) must also hold.

After repeatedly iterating this we eventually get P1 (a1 ), which means exactly that a1 | f (a1 )
for all positive integers a1 , as desired.

42
N3
Find all functions f : Z → N such that, f (2m + n)! + f (2n + m) is a prime number, for all
integers m and n.

Answer. There are two types of functions that satisfy the condition:

 
1, if n 6∈ A 1, if n 6∈ B
f (n) = or f (n) =
2, if n ∈ A 2, if n ∈ B

where A is any subset of the set 3Z − 2 and B is any subset of 3Z − 1.

Solution. Firstly, we see that the system k = 2m + n and l = 2n + m has a solution (m, n)
in integers given (k, l) if and only if 3|k + l, as can be seen by solving the system. By setting
m = n in the given condition, we see that f (3n)! + f (3n) is a prime number, from which
it follows that f (3n) = 1; otherwise, if f (3n) ≥ 2 for some n ∈ Z, then f (3n)! + f (3n) is
divisible with f (3n) and greater than f (3n), so it is composite, a contradiction. Now, we
only need to find the values of f at integers that are not multiples of 3.

Claim. If f (a)! + f (b) and f (b)! + f (a) are prime numbers then f (a), f (b) ∈ {1, 2}, and
they are not both 2.

Proof. We can without loss of generality assume that f (a) ≤ f (b). We first show f (a) = 1.
Assume for the sake of contradiction that f (a) ≥ 2, then

f (a) ≤ f (b) ⇒ f (a)|f (b)!,

so f (b)! + f (a) is divisible by f (a) and greater then f (a), and is thus a composite number,
a contradiction. So, f (a) = 1. This means that f (b) + 1 and f (b)! + 1 are both prime
numbers. Write f (b) + 1 = g(b), so g(b) is a prime number. From this, (g(b) − 1)! + 1
is also a prime number. But from Wilson’s theorem we have (g(b) − 1)! + 1 ≡ −1 + 1
(mod g(b)) ≡ 0 (mod g(b)), hence we have (g(b) − 1)! + 1 is a prime number and divisible
by g(b), so (g(b) − 1)! + 1 = g(b). This means that f (b) = g(b) − 1 is its own factorial, and
this is it either 1 or 2, as desired.

Now from condition and claim we have f (n) ∈ {1, 2} for all n ∈ Z. Clearly f (n) = 1 for all
n ∈ Z satisfy condition. Now suppose that there exists k0 ≡ 1 (mod 3) such that f (k0 ) = 2,
then f (l) = 1 for all l ≡ 2 (mod 3). Now, we may pick any value in {1, 2} for each k ≡ 1

43
(mod 3), which gives us the solutions

1, if n 6∈ A
f (n) =
2, if n ∈ A,

where A is any subset of the set 3Z − 2. By similar logic, we also get the functions

1, if n 6∈ B
f (n) =
2, if n ∈ B,

where B is any subset of the set 3Z − 1.

Comment: The function f (n) = 1 for all integers n can be written in both of the above
forms, with A = ∅ or B = ∅.

44
N4
Find all functions f : N → N such that for all positive integers x, y and z,

ϕ(f (xyz) + f (xy + yz + zx − x − y − z + 1) + f (x + y + z − 2)) f (x) + f (y) + f (z)

=
2 3

Answer. f (x) = 3c for all positive integers x and any non-negative constant integer c.

Solution. Let P (x, y, z) denote the given equation. Note that this equation immediately
implies that f (x) + f (y) + f (z) is divisible by 3 for any x, y, z.

P (1, 1, 1) =⇒ ϕ(3f (1)) = 2f (1). If p|f (1) for some prime p 6= 3, then we will have
2 p−1
ϕ(3f (1)) ≤ 3 × p × 3f (1) < 2f (1), a contradiction. Thus, f (1) = 3c for some non-
negative integer c.

ϕ(3f (x)) f (x) + 2f (1)

P (1, 1, x) =⇒ = (1)
2 3
ϕ(2f (xy) + f (x + y − 1)) f (x) + f (y) + f (1)
P (1, x, y) =⇒ = (2)
2 3

For any x ∈ N, we have v3 (ϕ(3f (x))) ≥ v3 (3f (x)) − 1 = v3 (f (x)). If v3 (f (x)) 6= v3 (f (1)),
then by (1), we have

v3 (ϕ(3f (x))) = v3 (2f (x) + 4f (1)) − 1

= min{v3 (f (x)), v3 (f (1))} − 1
< v3 (f (x))

which is a contradiction. Thus, v3 (f (x)) = v3 (f (1)) = c for all x ∈ N.

Now, for any a ∈ N, we have two cases:

Case 1. f (a) is odd.

ϕ(3f (a)) f (a)+2f (1)

In this case, (1) again implies that 2 = 3 is odd. We can see that if p|3f (a) for
some odd prime p 6= 3, then 2(p−1) = ϕ(3p)|ϕ(3f (a)) =⇒ 2|p−1| ϕ(3f2(a)) , a contradiction.

Thus, f (a) must be a power of 3. Since v3 (f (a)) = c, we have f (a) = 3c = f (1).

45
Case 2. f (a) is even.

ϕ(2f (a2 )+f (2a−1)) 2f (a)+f (1)

In this case, (2) implies that 2 = 3 is odd. By the same argument
2
as in the first case, we can see that 2f (a ) + f (2a − 1) has no prime divisor other than 2
2
2f (a)+f (1)
and 3. This means that 3 = ϕ(2f (a )+f
2
(2a−1))
also has no prime divisor other than
2f (a)+f (1)
2 and 3. However, as 3 is odd, it must be equal to 3b−1 for some positive b. This
b c
3 −3
means that f (a) = 2 . (It’s also true that b ≥ c + 2, because if b = c + 1, then f (a) = 3c
is odd.)

Now we will prove that if f (x), f (y) are even, then they’re equal.

By the same argument as in Case 2, we can see that f (x) + f (y) + f (1) is a power of 3. Let
3r −3c 3s −3c
f (x) = 2 and f (y) = 2 and assume WLOG that r ≥ s, then f (x) + f (y) + f (1) =
3r +3s r−1 3r 3r +3s 3r +3s
2 is a power of 3. As 3 < 2 < 2 ≤ 3r , we have 2 = 3r =⇒ r = s =⇒
f (x) = f (y), as desired.

b
−3c 3b −3c
Now, we can see that f (x) ∈ {3c , 3 2 } for some b ≥ c + 2 such that 2 is even. Assume
3b −3c
that f (h) = 2 for some h, then

P (h, h, h) =⇒ ϕ(f (h3 ) + f (3h2 − 3h + 1) + f (3h − 2)) = 3b − 3c .

Since f (h3 ) + f (3h2 − 3h + 1) + f (3h − 2) is divisible by 3, we have

2(f (h3 ) + f (3h2 − 3h + 1) + f (3h − 2))

ϕ(f (h3 ) + f (3h2 − 3h + 1) + f (3h − 2)) ≤
3

3(3b −3c )
This implies that f (h3 ) + f (3h2 − 3h + 1) + f (3h − 2) ≥ 2 . Hence, f (h3 ) = f (3h2 −
b c
3 −3
3h + 1) = f (3h − 2) = 2 . However, this also means that

3(3b − 3c )
 
ϕ = 3b − 3c
2

3(3b −3c )
Since 2 is both divisible by 2 and 3, we can see that

3(3b − 3c ) 1 2 3(3b − 3c )
 
3b − 3c = ϕ ≤ × × < 3b − 3c
2 2 3 2

which is a contradiction. Thus, f (x) = 3c for all x ∈ N which is clearly a solution.

46