MathDB
Problems
Contests
International Contests
Silk Road
2021 Silk Road
1
1
Part of
2021 Silk Road
Problems
(1)
Maximum of a given substring in sequences
Source: 2021 SRMC P1
6/28/2021
Given a sequence
s
s
s
consisting of digits
0
0
0
and
1
1
1
. For any positive integer
k
k
k
, define
v
k
v_k
v
k
the maximum number of ways in any sequence of length
k
k
k
that several consecutive digits can be identified, forming the sequence
s
s
s
. (For example, if
s
=
0110
s=0110
s
=
0110
, then
v
7
=
v
8
=
2
v_7=v_8=2
v
7
=
v
8
=
2
, because in sequences
0110110
0110110
0110110
and
01101100
01101100
01101100
one can find consecutive digits
0110
0110
0110
in two places, and three pairs of
0110
0110
0110
cannot meet in a sequence of length
7
7
7
or
8
8
8
.) It is known that
v
n
<
v
n
+
1
<
v
n
+
2
v_n<v_{n+1}<v_{n+2}
v
n
<
v
n
+
1
<
v
n
+
2
for some positive integer
n
n
n
. Prove that in the sequence
s
s
s
, all the numbers are the same.A. Golovanov