5
$\begingroup$

Arrange the integers 1-100 in such a way that no eleven of the numbers selected from left to right (adjacent or otherwise) form a strictly increasing or decreasing sequence. (This means if 11 numbers are selected from anywhere in the pattern they cannot be in an increasing or decreasing pattern).


I think I have to divide the 100 integers into 10 groups, all with 10 integers. But that's all I've thought about.

$\endgroup$
  • 2
    $\begingroup$ Sounds like a good first step....and you ARE allowed a ten-number increasing or decreasing sequence... $\endgroup$ – Joffan Mar 1 '17 at 22:10
  • 1
    $\begingroup$ Start with a smaller example if it helps you to think. Can you arrange the first nine numbers in such a way that no four numbers selected are in increasing or decreasing order? 789 456 123 seems to do the trick, yea? Can you generalize this to your specific scenario? Can you prove that it does in fact work? $\endgroup$ – JMoravitz Mar 1 '17 at 22:14
1
$\begingroup$

To reiterate my comment from above and remove this from the unanswered queue:

Think about the smaller question of arranging the numbers $1$-$9$ in such a way that there is no monotonic subsequence of length $4$ or more.

$789~456~123$ satisfies this condition. If you were to create an increasing subsequence all of the numbers must be from the same block. If you were to create a decreasing subsequence all of the numbers must be from different blocks. As such, the largest length increasing subsequence is the size of a block and the largest length decreasing subsequence is the number of blocks, both of which in this case are three.

Generalize this to your specific problem.

$91,92,93,\dots,100,~~81,82,83,\dots,90,~~71,72,73,\dots,80,~~\dots~~1,2,\dots,10$

$\endgroup$
1
$\begingroup$

What about

$$10\ 9\ 8\ 7\ 6\ 5\ 4\ 3\ 2\ 1\ 20\ 19\ 18\ 17\ 16\ 15\ 14\ 13\ 12\ 11\cdots $$

?

$\endgroup$
  • $\begingroup$ Same answer as mine in reverse. Of course an increasing subsequence from left to right corresponds to a decreasing subsequence from right to left, so it stands to reason any correct solution could be written in the opposite order and remain correct. $\endgroup$ – JMoravitz Mar 1 '17 at 22:39
  • $\begingroup$ @JMoravitz I did not notice your solution ... $\endgroup$ – Peter Mar 1 '17 at 22:41
0
$\begingroup$

I'd like to point out another construction: $$91,81,71,\ldots,92,82,72,\ldots,93,83,73,\ldots $$ If you want an increasing sequence, no matter which number you choose you must pass at each step to the next block of ten numbers $\implies$ at most ten choices.

If you want a decreasing sequence you must lower at each step the ten's figure $\implies$ at most ten choices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.