# Puzzle of the Week for 11 November 1998: Solution

It is not possible to arrange 10 different numbers in such a way that no 4 are in either ascending or descending order.

It is, however, quite difficult to prove this. In fact, it was not proven until quite recently that at least one ordered sequence of at least n items will appear in any arrangement of 1+(n-1)2 distinct items. Thus, if n=4, we need at least 1+(4-1)2 = 10 items to ensure that at least 4 of them will appear in an ordered sequence.

This problem involves a branch of graph theory called Ramsey theory, named after its discoverer, Frank Ramsey (1903-1930). The subject matter of Ramsey theory is the occurrence of (apparent) order within (apparent) disorder. Many important unsolved problems remain within Ramsey theory, and it is an active area of research in mathematics today.

See the hints for the solution of a simpler version of this problem.

One way to answer the original question is by exhaustive search: list all of the possible arrangements (permutations) of 10 numbers and show that each contains at least one ordered sequence of at least 4 numbers. This is a bit more work than you should attempt to do on paper! (How many permutations are there?) A computer program can answer this question fairly quickly, and you can learn to write such a program much faster than you would be able to list all of the arrangements of 10 numbers. If you decide to try this, here is another question you might be able to answer: what is the probability that a randomly chosen arrangement of 10 different numbers contains an ordered sequence of 5 or more numbers? If you make 10 measurements during a science experiment (or record XYZ Corporation's stock prices, or the winning lottery number, on 10 days) and find that 5 of them form an ordered sequence, should you believe that this pattern is significant?