Prove that it is possible to erase 90 of them leaving a sequence of 11 numbers that are in either a strictly increasing or strictly decreasing order.

Following my previous comment, I now see this is a 'piece of cheese' problem, i.e where you just need to show the result, i.e a non-continuous sequence of (at least) 11 numbers.

Assume we have just 1 real number. Then any other number we choose must either be bigger or smaller, so one way or another we have the desired result.

Now assume we have two real numbers. a,b. Say a>b. If the next number, c, is less than b, then we are done. So c>b.  Now if the next number, d, is >c then we are done, So d<c. But if c is also <a, we are done still, so c>a. Essentially we have a square arrangement, with a,b,c,d, at the corners:

            c

a       

                     d   

      b

Now it should be obvious that wherever we add the next element, we will complete a line of 3 somewhere. And we can do the same if a<b, too.

And that's all there is to it, if we consider the relative positions of the elements in the sequence, rather than their absolute values, and just consider the optimum arrangement rather than the tons of suboptimal ones.

If we increase the diagram still further, so that  we are allowed 3 elements per line, then we must run out of choices after 3 lines of 3 are filled up. The tenth number will complete a line of 4, just like in tic-tac-toe.

In the puzzle we have 101 distinct numbers, which is 10^2+1. We know that we can legally organise no more than 10x10, so at best at least one subsequence must contain 11 elements.

Edited on January 29, 2016, 10:41 am

Posted by broll on 2016-01-29 08:55:48