MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2018/2019
A.752
A.752
Part of
KoMaL A Problems 2018/2019
Problems
(1)
Finding the least k-sparse integer
Source: 2018 RMM Shortlist C4
2/21/2019
Let
k
k
k
and
s
s
s
be positive integers such that
s
<
(
2
k
+
1
)
2
s<(2k + 1)^2
s
<
(
2
k
+
1
)
2
. Initially, one cell out of an
n
×
n
n \times n
n
×
n
grid is coloured green. On each turn, we pick some green cell
c
c
c
and colour green some
s
s
s
out of the
(
2
k
+
1
)
2
(2k + 1)^2
(
2
k
+
1
)
2
cells in the
(
2
k
+
1
)
×
(
2
k
+
1
)
(2k + 1) \times (2k + 1)
(
2
k
+
1
)
×
(
2
k
+
1
)
square centred at
c
c
c
. No cell may be coloured green twice. We say that
s
s
s
is
k
−
s
p
a
r
s
e
k-sparse
k
−
s
p
a
rse
if there exists some positive number
C
C
C
such that, for every positive integer
n
n
n
, the total number of green cells after any number of turns is always going to be at most
C
n
Cn
C
n
. Find, in terms of
k
k
k
, the least
k
k
k
-sparse integer
s
s
s
.[I]Proposed by Nikolai Beluhov.
combinatorics