MathDB
Problems
Contests
National and Regional Contests
Taiwan Contests
IMOC Shortlist
2022-IMOC
N2
N2
Part of
2022-IMOC
Problems
(1)
A function that is O(n)
Source: 2022 IMOC N2
9/5/2022
For a positive integer
n
n
n
, define
f
(
x
)
f(x)
f
(
x
)
to be the smallest positive integer
x
x
x
satisfying the following conditions: there exists a positive integer
k
k
k
and
k
k
k
distinct positive integers
n
=
a
0
<
a
1
<
a
2
<
⋯
<
a
k
−
1
=
x
n=a_0<a_1<a_2<\cdots<a_{k-1}=x
n
=
a
0
<
a
1
<
a
2
<
⋯
<
a
k
−
1
=
x
such that
a
0
a
1
⋯
a
k
−
1
a_0a_1\cdots a_{k-1}
a
0
a
1
⋯
a
k
−
1
is a perfect square. Find the smallest real number
c
c
c
such that there exists a positive integer
N
N
N
such that for all
n
>
N
n>N
n
>
N
we have
f
(
n
)
≤
c
n
f(n)\leq cn
f
(
n
)
≤
c
n
.Proposed by Fysty and amano_hina
IMOC
number theory