tmua.me Medium Set E Paper 2 · Question 20

Ten distinct real numbers are written in a row. A subsequence is a choice of some of these numbers that keeps their original order.

The following proof shows that there is a strictly increasing or strictly decreasing subsequence of at least four terms.

Assume that no such subsequence exists. Write the numbers as $a_1,\ldots,a_{10}$ .

[Missing argument]

Thus we have ten different pairs $(r_i,s_i)$ , with each coordinate equal to $1$ , $2$ or $3$ . However, there are only $3\times3=9$ possible pairs, a contradiction.

Which option correctly completes the proof?

ALet

r_i,s_i

be the greatest lengths of strictly increasing and strictly decreasing subsequences ending at

a_i

, respectively. For

i<j

, appending

a_j

gives

r_j>r_i

a_i<a_j

, and

s_j>s_i

a_i>a_j

BLet

r_i

be one plus the number of earlier terms smaller than

a_i

, and

s_i

one plus the number larger. Neither label exceeds

3

, and

r_i+s_i=i+1

makes the pairs distinct.

CLet

r_i,s_i

be the greatest lengths of strictly increasing and strictly decreasing blocks of consecutive terms ending at

a_i

, respectively. For any

i<j

, appending

a_j

extends one such block, so a label increases.

DLet

r_i,s_i

be the greatest lengths of strictly increasing subsequences ending and starting at

a_i

, respectively. For

i<j

, either

r_j>r_i

s_i>s_j

, according to the order of

a_i,a_j

ELet

r_i,s_i

be the greatest lengths of strictly increasing and strictly decreasing subsequences among

a_1,\ldots,a_i

, respectively. Moving from

i

to any later

j

introduces a new term, so at least one label increases.

examday

tmua.me Medium Set E Paper 2 · Q20