Height Arrangement

Suppose you have 10 people with different heights in one row. Show that you can always remove 6 of them, so that the remaining 4 are arranged with respect to their heights (either increasing or decreasing).


Mark the first person with number 1. Look for the next person after him, who is taller, and also mark him with number 1. Then look for the first person after the second one, who is taller, and also mark him with number 1. If you find a fourth one, then you already got the four people you are looking for.

If not, mark the first unmarked person with number 2. Look for the next unmarked person after him, who is taller, and also mark him with number 2. Continue with the procedure, until you either find 4 people in the line, whose heights are increasing, or have people who are marked with numbers 1, 2, 3 and 4.

Now pick a person, who is marked with number 4. Then look for the closest person on the left, who is marked with number 3, pick him up. He will be taller, because otherwise the first person would have been labeled 3 as well. Similarly, look for the closest person, marked with 2, on the left of the last one, pick him up. Repeat this once again and you will find 4 people in the line, whose heights are decreasing.