Can you arrange the numbers from 1 to 100 so there is no ascending or descending subsequence of length greater than 10?

I’m not sure if I’m misunderstanding your question. Why not just arrange them in 5 number sequences from the beginning and the end of the numbers.
1–5 95–100
6–11 89–94
etc

I misunderstood the question, I think.

The idea seems right but ignore my math error.

@Adirondackwannabe, Your approach gives a large ascending sequence 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,... Like I said, the numbers do not have to be consecutive.

@whitenoise , Let me explain again. You are usually pretty good with these, so I must not have explained myself very well. Consider the numbers 1 to 5. If I write them as (1,2,3,4,5) there is an ascending sequence of length 5. If I write them as 1,2,3,5,4 there are ascending sequences of length 4 – (1,2,3,5 ) and (1,2,3,4) – not a whole lot of improvement. There is also a descending sequence of length 2 – (5,4). You should be able to improve things so that the longest ascending or descending sequence in this case is of length 3.

100 = 10^2. Try the problem with 1 to 9, with the longest ascending or descending sequence being of length 3.

I’d do what @Adirondackwannabe did except with longer sequences –
1— 10
20 -11
21–30
40–31
41–50
etc.

And using the same methodology, I can do the 1 -101 with no sequence longer than 10.

Unless you are leaving something out of the instructions.

@LostInParadise No, the longest of any sequence is 5 digits.

Oops, my answer wasn’t clear. 1,2,3,4,5,100,99,98,97,96,6,7,8,9,10,95,94,93,92,91, etc.

@Adirondackwannabe

You have 1,2,3,4,5,zyxwv,6,7,8,9,10

Your longest subsequence is 50 in length.

@whitenoise If you count all numbers going either up or down as a subsequence even if they are interrupted by other numbers, then you’re always going to have one subsequence of at least 50 numbers.

I think @LostInParadise is going to have to explain his question a bit more, so that we see what the challenge is.

Just check above explanation by @LostInParadise. If we only count subsequences that are not connected, then the longest sequence will be two, regardless of the size of the total set.

Wow…
Getting two great answers for demonstrating not to read the question properly. :-)

Maybe if I show this pictorially it will make more sense.

1,2,3,4,5,100,99,98,97,96,6,7,8,9,10,95,94,93,92,91

The bold numbers are all part of a single ascending subsequence. The other numbers are part of a single decending subsequence. Think of the ascending subsequence as interleaving with the rest of the numbers.

@Adirondackwannabe , Your thinking is in the right direction. The solution is actually simpler than what you are giving. Think about how you can rearrange your groups of 5 so that they don’t combine.

How about this:

1, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11

2, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21

3, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31

…and so on?

That is the correct answer, if you include 10,9,8,7,6,5,4,3,2,1 at the beginning.

Each group of 10 is a descending sequence and going from one sequence to another, you can build an ascending sequence with at most one member from each group.

Can you find a second solution using the same basic idea?

Here is an outline of a relatively short proof that, given any arrangement of the numbers form 1 to 101, there must be ascending or descending sequence of length greater than 10. Unlike some of the longer proofs, it does not tell how to find such a sequence. It only shows that one must exist.

Given an arrangement of the numbers from 1 to 101, associate with each number x the pair of numbers (a,b) where a is the length of the longest ascending sequence starting at x and b is the length of the longest descending sequence starting at x.

1. Consider two numbers x and y where x is to the left of y. Intuitively, it should seem that sequences starting at x should tend to be longer than those starting at y. If (a,b) is the maximum sequence length pair (defined above) associated with x and (c,d) is the pair associated with y, show that it must be the case that either a > c or b > d, depending on the relative sizes of x and y.

2. That means that none of the (a,b) pairs are the same. Put differently, they must all be different. Consider now the numbers whose (a,b) pairs are such that a <= 10 and b <= 10. How many such pairs are there? Do you see how that means that there must be a a number whose (a,b) pair is such that a > 10 or b > 10, meaning that there must be an ascending sequence of length at least 11.

In addition to the solution given by @longgone , there is a similar solution of 91,92,93,94,95,96,97,98,99,100,80,81,82,83,84,85,86,87,88,89,90 and so on

Here is the proof filled in for why an arrangement of 101 numbers must have an ascending or descending sequence of length > 10. Given x to the left of y. If x < y, consider the longest ascending chain starting at y. x can form a larger ascending chain by hooking into y’s chain so we would have a > c. Similarly if x > y, x can hook into the longest descending chain starting at y, and in that case b > d. We conclude that for any two numbers, their (a,b) values will be different, meaning that all the (a,b) values are distinct.

If we consider cases where a <= 10 and b <=10, there are 10×10 = 100 possible pairs of (a,b) values, which can be connected to at most 100 numbers. That leaves at least one of the 101 numbers unaccounted for, which must have either a > 10 or b > 10, and would have to be the start of either an ascending or descending chain of length greater than 10.

Oh, I got it right. Thanks for the proof!