Ascending/Descending Numbers
If you have a card deck, go grab it. Got it? Now, take out cards from 1 (ace) through 9. Shuffle them and lay them out on the table, one card after the next (so you get a random ordering). How many ascending numbers can you find? How about descending numbers? Can we rearrange these cards so there are smaller ascending/descending subsequences?
The Rules of the Game
Let’s start with a smaller set of numbers: 1-4. We need to order these numbers such that if we read the sequence from left to right, no more than 2 numbers are ascending and no more than 2 numbers are descending. That might sound a bit confusing, so here’s an example:
When we scan this sequence for ascending numbers, we only find the pairs (1, 3) and (1, 2). It may be helpful to look at the yellow circles; you can see from the red arrows in the figure below that 1 ascends to 3, and if we skip 3, 1 also ascends to 2.
So, all is well for ascending numbers. How about descending numbers? We have 4, 3… uh oh, 2! That’s 3 descending numbers!
That means we haven’t found a correct ordering yet. Let’s keep searching.
What if we switch the positions of the 3 and the 4? Would this ordering work?
It looks like we have ascending pairs (3, 4), (1, 4) and (1, 2), but no more than two ascending. Check! Then, we have the descending pairs (3, 1), (3, 2) and (4, 2), but again, no more than two descending. Check check!
So we’ve found a sequence that works! But can we find any more? Try some different orderings yourself first, then keep scrolling for the answer…
Actually, there are three more orderings that satisfy the requirements! I’ll let you check yourself that these work.
But our end goal isn’t just to find a length-4 ordering. Can you find a viable ordering of length 5? 6? How about 9? (Hint: you may need longer than length-2 ascending/descending subsequences. Read on for more information.) Keep exploring to see what you can find!
If you need further clarification of the rules, check out this Math Monday session with Javier Haro:
More Insight: How it works
Now that we’ve found viable orderings for the numbers 1-4, let’s try to find one for 1-5. Now, we are trying to order these numbers so that only the smallest-sized descending and ascending subsequences exist in our ordering. Try this for subsequences of length 2, then scroll for the answer!
Spoiler: Creating an ordering of the numbers 1-5 with at most 2 ascending or 2 descending numbers is impossible!
Think about it this way. Take any ordering that works for 1-4; let’s say 2, 1, 4, 3. Now, no matter where you place a 5, you’re adding a third number to an existing ascending or descending subsequence, creating a new subsequence of length 3.
In this case, if you place 5 anywhere after 4, you add to the ascending sequences (2, 4) and (1, 4) to create (2, 4, 5) (as shown above) and (1, 4, 5). Similarly, if you place 5 anywhere before 4, you add a third number to the descending sequence (4, 3) to create (5, 4, 3).
So our ordering of length 5 has to have ascending/descending subsequences of (at least) length 3. Actually, the same applies for our orderings of length 6, 7, 8, and 9! Why is that? Well, any ordering of length n can have ascending and descending subsequences of at the very least the square root of n. That means that for n=4, we can have subsequences of length sqrt(4)=2, but from n=5 to n=9, the square root is some decimal above 2 (or for length 9, exactly 3), which rounds up to 3. For orderings of length 10-16 we’ll get subsequences of length at least 4, then at least 5 from 17-25, and so on.
This rule is also known as the Erdős-Szekeres theorem, which (in simple terms) says that any (random) length-n ordering of numbers must have some ascending or descending subsequence with length at least sqrt(n). For more information on this theorem and an easy-to-follow proof, click here!
Strategy
Ok, so now we know how long the increasing/decreasing sequences have to be. But how can we strategically find a viable ordering?
Let’s look at the numbers 1 through 9. I believe there are 1,724 orderings that satisfy our rules for ascending and descending subsequences no greater than 3. It’s such a big number, it seems like it should be easy to find one! That is, until you realize that there are 9 factorial (9!) or 362,880 total ways to order those numbers. If you pick a random ordering, you have a 0.48% chance of getting it right – unfortunately, the odds are against you.
So how do we tip the odds in our favor? Is there a way we could get it right every time, without going through the grueling guess-and-check process? Here’s an ordering for 1-9 that works (check for yourself!).
Notice how similar the pattern of the yellow dots looks to one of our solutions of length 4:
We have this simple pattern where we arrange decreasing subsequences of length sqrt(n) in order from smallest to largest.
This means that for any ordering of length perfect square n=m^2, we have decreasing subsequences in order so the first is {m, m-1, … , 1}, then {2m, 2m-1, … , m+1}, then {3m, 3m-1, … , 2m+1}, and so on until the final decreasing subsequence {m^2, (m^2)-1, … , (m-1)*(m)+1}. This sounds more complicated than it is, so here’s what n=16 would look like, for clarification:
Success! Now, if you want to get working orderings of length n=10 to n=15, simply eliminate the numbers in the sequence you don’t need, maintaining the ordering of the other numbers. So n=13 would look like (4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 13) and n=10 would be (4, 3, 2, 1, 8, 7, 6, 5, 10, 9).
Why does this work? Well, since we created sqrt(n) valid decreasing subsequences that increase in average value as we go to the right, the only decreasing subsequences in the entire ordering are the ones we created. Perfect! Then, the only way to get an increasing subsequence is by taking one number from each of those sqrt(n) decreasing subsequences, which means we can have a maximum length of 1*sqrt(n) for each increasing subsequence.
This specific ordering may work every time, but it isn’t the only ordering. Remember, there are still 1,723 more orderings for n=9! Who knows, maybe you could even stumble across another trick that works for all length-n orderings!
Keep exploring exploring the wide world of ascending/descending numbers – you never know what you’ll find!