MathDB

Given a natural number

n

, for which we can find a prime number less than

\sqrt{n}

that is not a divisor of

n

. The sequence

a_1, a_2,... ,a_n

is the numbers

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}

, (

i_1 <...< i_k

) and the longest decreasing substring

a_{j_1} > ... > a_{j_l}

, (

j_1 < ... < j_l

) . Prove that at least one of these two subsequnsces

a_{i_1} , . . . , a_{i_k}

and

a_{j_1} > ... > a_{j_l}

contains a number that is not a divisor of

n

Problem Statement