MathDB

Iberoamerican Olympiad 2014, Problem 6

Source:

September 25, 2014

functionalgorithminductioninequalitiesnumber theory unsolvednumber theory

Problem Statement

Given a set

X

and a function

f: X \rightarrow X

, for each

x \in X

we define

f^1(x)=f(x)

and, for each

j \ge 1

,

f^{j+1}(x)=f(f^j(x))

. We say that

a \in X

is a fixed point of

f

if

f(a)=a

. For each

x \in \mathbb{R}

, let

\pi (x)

be the quantity of positive primes lesser or equal to

x

.
Given an positive integer

n

, we say that

f: \{1,2, \dots, n\} \rightarrow \{1,2, \dots, n\}

is catracha if

f^{f(k)}(k)=k

, for every

k=1, 2, \dots n

. Prove that:
(a) If

f

is catracha,

f

has at least

\pi (n) -\pi (\sqrt{n}) +1

fixed points. (b) If

n \ge 36

, there exists a catracha function

f

with exactly

\pi (n) -\pi (\sqrt{n}) + 1

fixed points.

Back to Problems View on AoPS