Puzzle of the Week for 11 November 1998: Hints

Think about a simpler version of this problem. For example, show that at least 3 numbers from any ordering of 5 different numbers are in ascending or descending order.

Here's one way to prove the simpler statement above. Consider the first three numbers in the set of five. If those three are in ascending or descending order, the statement is correct in this case. If the first three numbers are not in ascending or descending order, we must have an arrangement similar to one of the following:

(a)

1 3 2 x y

(b)

2 3 1 x y

(c)

2 1 3 x y

(d)

3 1 2 x y

Now suppose the fourth number is larger than the fifth (x > y). Let's compare the fourth number to the largest of the first three (call this w):

1. If w > x, we have three numbers in descending order (w > x > y).
2. Otherwise, w < x:
   1. If we have case (a), (b), or (c), we have three numbers in ascending order: a smaller number to the left of w, and a larger number (x) to the right of w.
   2. Otherwise, we have case (d), and the second, third, and fourth numbers are in ascending order.

Follow a similar chain of reasoning to show that at least three numbers in the set are arranged in ascending or descending order if x < y.

Links

• Puzzle
• Solution
• Puzzle Archives
• Home