Making an array of five numbers increasing or decreasing by removing two elements, proof needed.

Question

I need to prove this, I have a long proof, and I'm wondering if there is a shorter one. You have an array of five elements $x_1, x_2, x_3, x_4, x_5$. Prove that you can always acquire a sorted array (increasing or decreasing) by removing just two elements.

For the proof I found: The strategy will first try to find three adjacent sorted elements and if found, remove the other two.

So let's assume that $x_1 \le x_2$, then for the strategy to not work $x_2 \ge x_3$ should hold true and so on. So we have two worst case scenarios:

1. $x_1 \le x_2 \ge x_3 \le x_4 \ge x_5$
2. $x_1 \ge x_2 \le x_3 \ge x_4 \le x_5$

To prove that there is always a solution we need to start analyzing every case, then we'd found an answer.

Is there any faster way to prove this? Thanks in advance.

Answer 1

Without loss of generality, assume that $x_1 \le x_2$. (Otherwise, reverse all the inequalities, and the proof stands by symmetry.)

As you say, if there are three adjacent sorted elements, then we are done. If not, we must have $x_1 \le x_2 \ge x_3 \le x_4 \ge x_5$.

Now consider the two cases $x_2 \le x_4$ and $x_2 \ge x_4$.

Answer 2

If the sign sequence of the differences $x_{k+1}-x_k$ $\>(1\leq k\leq4)$ contains a run of two equals, say $++$, we are done. If not, this sequence is $+-+-$ or $-+-+$. In this case remove $x_3$ and obtain a sign sequence containing a run of two equals, whatever ${\rm sgn}(x_4-x_2)$.