MathDB
Problems
Contests
National and Regional Contests
Latvia Contests
Latvia BW TST
2016 Latvia Baltic Way TST
6
6
Part of
2016 Latvia Baltic Way TST
Problems
(1)
subsequences of permutations of 1-n with no divisors of n
Source: 2016 Latvia BW TST P6
12/17/2022
Given a natural number
n
n
n
, for which we can find a prime number less than
n
\sqrt{n}
n
that is not a divisor of
n
n
n
. The sequence
a
1
,
a
2
,
.
.
.
,
a
n
a_1, a_2,... ,a_n
a
1
,
a
2
,
...
,
a
n
is the numbers
1
,
2
,
.
.
.
,
n
1, 2,... ,n
1
,
2
,
...
,
n
arranged in some order. For this sequence, we will find the longest ascending subsequense
a
i
1
<
a
i
2
<
.
.
.
<
a
i
k
a_{i_1} < a_{i_2} < ... < a_{i_k}
a
i
1
<
a
i
2
<
...
<
a
i
k
, (
i
1
<
.
.
.
<
i
k
i_1 <...< i_k
i
1
<
...
<
i
k
) and the longest decreasing substring
a
j
1
>
.
.
.
>
a
j
l
a_{j_1} > ... > a_{j_l}
a
j
1
>
...
>
a
j
l
, (
j
1
<
.
.
.
<
j
l
j_1 < ... < j_l
j
1
<
...
<
j
l
) . Prove that at least one of these two subsequnsces
a
i
1
,
.
.
.
,
a
i
k
a_{i_1} , . . . , a_{i_k}
a
i
1
,
...
,
a
i
k
and
a
j
1
>
.
.
.
>
a
j
l
a_{j_1} > ... > a_{j_l}
a
j
1
>
...
>
a
j
l
contains a number that is not a divisor of
n
n
n
.
number theory
Sequence