Question

Construct a sequence of 16 integers that has no increasing or decreasing subsequence of five elements.

Short answer

The sequence [1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16] has no subsequence of five increasing or decreasing elements.

Step-by-step solution

Understand the Problem

We need to construct a sequence of 16 integers that does not have an increasing or decreasing subsequence with more than four elements.

Learn About Erdős–Szekeres Theorem

According to the Erdős–Szekeres theorem, any sequence of more than \((k-1)(l-1)\) integers has either an increasing subsequence of length \(k\) or a decreasing subsequence of length \(l\). Here, \(k = 5\) and \(l = 5\), so any sequence of more than \((5-1)(5-1) = 16\) integers will have an increasing or decreasing subsequence of five elements.

Set the Boundaries of the Sequence

Since the maximum number of elements we can have without having a subsequence of length 5 is 16, we need to carefully construct a sequence of exactly 16 numbers.

Construct a Zigzag Sequence

Design a sequence that oscillates to avoid long increases or decreases. Example: \([1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16]\). This ensures no consecutive increases or decreases extend to length 5.

Verify the Sequence

Check the sequence for subsequences. In the constructed sequence, the longest continuous increasing or decreasing subsequences are of length 4, which satisfies the problem condition.

Key concepts

Increasing Subsequence

An increasing subsequence within a sequence of numbers is a subset where each number is larger than the preceding one. Imagine you are climbing a staircase; each step must be higher than the last for it to be considered an increase. For example, given the sequence \[ [1, 3, 2, 4, 5, 7] \] here are some possible increasing subsequences:

• \([1, 3, 4, 5] \)
• \([2, 4, 5, 7] \)

Notice not all elements have to be included, just enough to maintain the increasing trend. In the context of the Erdős–Szekeres theorem and the exercise, having a sequence without an increasing subsequence of 5 elements means carefully choosing numbers so that no set of 5 numbers will ever continuously rise.

Decreasing Subsequence

A decreasing subsequence is quite the opposite of an increasing one, where each subsequent number is less than the one before it. If you think of descending a staircase, each step must be lower to count as a decrease.Consider the sequence \([10, 8, 9, 5, 4, 6, 2] \). Potential decreasing subsequences could be:

• \([10, 9, 5, 4] \)
• \([8, 6, 2] \)

The challenge is to construct sequences where no 5 elements form a continuous downward trend. Again, linked to the Erdős–Szekeres theorem, the task involves ensuring that no subsequence of 5 elements diminishes in value.

Zigzag Sequence

A zigzag sequence alternates between increasing and decreasing, preventing lengthy subsequences of increases or decreases. Think of it like driving on a winding road, constantly turning left then right to avoid a long straight path.In practical terms, the sequence alternates patterns like so:\([1, 3, 2, 4, 6, 5] \)In this example, it goes from 1 to 3, then dips to 2, climbs to 4, again up to 6, and then drops to 5, ensuring no path from 1 to another number has more than 4 consecutive increases or decreases.Designing a zigzag sequence helps comply with restrictions given by the Erdős–Szekeres theorem in the exercise, safeguarding against reaching the forbidden subsequence length of 5, whether it be increasing or decreasing. Such a pattern is repeated smartly to construct a sequence like the given example, \([1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16] \), to fulfill all constraints needed.