MathDB

every sequence of 1000 numbers has >= k non-overlapping ascending pairs

Source: 2022 Dutch IMO TST 1.4

December 3, 2022

combinatorics

Problem Statement

In a sequence

a_1, a_2, . . . , a_{1000}

consisting of

1000

distinct numbers a pair

(a_i, a_j )

with

i < j

is called ascending if

a_i < a_j

and descending if

a_i > a_j

. Determine the largest positive integer

k

with the property that every sequence of

1000

distinct numbers has at least

k

non-overlapping ascending pairs or at least

k

non-overlapping descending pairs.

Back to Problems View on AoPS