Mariolys's Monotonic Subsequences

I claim the answer is $(13-1) \cdot (17-1) + 1 = 193$ elements. To rigorously prove this, I will prove a general statement: Given a sequence of length $(r-1) \cdot (s-1) + 1$ , there exists an increasing subsequence of length $r$ or a decreasing one of length $s$ .

Given a sequence of length $(r-1) \cdot (s-1) + 1$ , label each number $n_i$ ' in the sequence with the pair $a_i, b_i$ , where $a_i$ is the length of the longest monotonically increasing subsequence ending with $n_i$ and $b_i$ is the length of the longest monotonically decreasing subsequence ending with $n_i$ . Each two numbers in the sequence are labeled with a different pair: if $i < j$ and $n_i < n_j$ then $a_i < a_j$ , and on the other hand if $i > j$ then $b_i < b_j$ . But there are only $(r-1) \cdot (s-1)$ possible labels in which $a_i$ is at most $r_i -1$ and $b_i$ is at most $s_i-1$ , so by the pigeonhole principle there must exist two elements with the same labelling if the increasing/decreasing sequences don't exist, which is absurd. Thus it is proven they exist so we are done.

To show $193$ is minimum, it suffices to find a sequence of $192$ elements with no increasing chains of length $13$ or more and no decreasing ones of length $17$ or more.To do this just construct $16$ sets of $12$ increasing elements. Make it so that the greatest element in the a set is less than the minimum element in the previous one. It is clear this has no increasing subsequences of length $13$ and no decreasing ones of length $17$ either, so we are done.

Let us prove the more general result that the minimum length of a list of distinct integers with either an increasing subsequence of length $m$ or a decreasing subsequence of length $n$ (where $m, n \geq 2$ ) is $(m-1)(n-1)+1$ .

We first note that a sequence of $(m-1)(n-1)$ numbers can contain neither an increasing subsequence of length $m$ nor a decreasing subsequence of length $n$ . One such sequence is $(n-1, n-2, ... , 1, 2n-1, 2n-2, ... , n+1, ... , (m-1)n-1, (m-1)n-2, ... , (m-2)n+1)$ . This sequence can be divided into $m-1$ consecutive blocks of $n-1$ numbers each, where each block contains a decreasing sequence of $n-1$ terms and two consecutive blocks have the property that all the numbers in the right block are greater than all the numbers in the left block. It is easy to see that such a sequence of $(m-1)(n-1)$ numbers contains neither an increasing subsequence of length $m$ nor a decreasing subsequence of length $n$ .

Now we want to prove that a sequence of $(m-1)(n-1)+1$ numbers must contain either an increasing subsequence of length $m$ nor a decreasing subsequence of length $n$ . Assume on the contrary that this is false. Then for each number $n_i$ in the sequence, we label it with the ordered pair $(a_i, b_i)$ , where $a_i$ and $b_i$ are the lengths of the longest increasing subsequence beginning with $n_i$ and the longest decreasing subsequence ending with $n_i$ respectively. Since we have assumed the result to be false, then $1 \leq a_i \leq m-1$ and $1 \leq b_i \leq n-1$ for all $1 \leq i \leq (m-1)(n-1)+1$ . We thus have $(m-1)(n-1)+1$ ordered pairs, but at most $(m-1)(n-1)$ are distinct. So at least two numbers in the sequence, say $n_x$ and $n_y$ , must have the same label $(r, s)$ . Without loss of generality, we let $x \leq y$ . If $n_x < n_y$ , then $n_x$ , together with the longest increasing subsequence beginning with $n_y$ , would be an increasing subsequence of length $r+1$ , contradicting the fact that $r$ is the length of the longest increasing subsequence beginning with $n_x$ . If $n_x > n_y$ , then $n_y$ , together with the longest decreasing subsequence ending with $n_x$ , would form a decreasing subsequence of length $s+1$ , contradicting the fact that $s$ is the length of the longest decreasing subsequence ending with $n_y$ . Since $n_x$ and $n_y$ are distinct, then $n_x \neq n_y$ , so we arrive at a contradiction. This means our original assumption was incorrect, so a sequence of $(m-1)(n-1)+1$ numbers must contain either an increasing subsequence of length $m$ nor a decreasing subsequence of length $n$ .

Thus, we have proved that the minimum length of a list of distinct integers with either an increasing subsequence of length $m$ or a decreasing subsequence of length $n$ is $(m-1)(n-1)+1$ . In the question, $m=13$ and $n=17$ , so our answer is $(13-1)(17-1)+1=193$ .

First, it is easy to see that if there are $192$ numbers $(a_1, a_2,..., a_{192})$ in the list, he might not be able to find an increasing subsequence of length $13$ nor a decreasing subsequence of length $17$ . To do this, we can form $12$ subsequences of $16$ numbers each, where each sequence is decreasing, and its terms are either all larger or all smaller than that of another subsequence. We can then arrange these subsquences in increasing order to form our desired sequence of length $192$ . A simple example would be $(16,15,...2,1,32,...17,48,....,192,...177)$ .

Next, we consider a sequence of length $193$ . For each $a_i, 1 \leq i \leq 193$ in the sequence, we consider the longest increasing and decreasing subsequence (let's name it $(x,y)$ , $x$ for increasing, $y$ for decreasing) from $a_1$ to $a_i$ . For any two distinct $a_i,a_j$ where $i < j$ , if $a_i > a_j$ then $a_j$ would have a larger $y$ value, and if $a_i < a_j$ then $a_j$ would have a larger $x$ value. Therefore, no two numbers in the sequence will share the same $(x,y)$ . For Luigis not to spot such subsequences, $1 \leq x \leq 12$ and $1 \leq y \leq 16$ for all $a_i$ in the sequence. There are only 192 possible $(x,y)$ , so if there are 193 numbers in the list, (by pigeonhole principle) at least one of $a_i$ would have $x>12$ or $y>16$ and Luigis's claim would be true.

First, if N is (at most) 192, consider the sequence:

(16,15,...,1, 116,115,...,101, 216,.......... 1116,1115,...,1101).

This has 192 terms as there are 12 blocks of 16, and a decreasing sequence must all be in one block (length at most 16) and an increasing sequence is in separate blocks (length at most 12). (Take the first N terms if N < 192).

Otherwise, suppose N is 193. Say the sequence is $x_1$ , ..., $x_{193}$ . To each term, assign the pair $a_i, b_i$ denoting the lengths of the longest possible increasing subsequence ending at $x_i$ and the longest possible decreasing subsequence starting at $x_i$ . Supposing that $a_i < 13$ and $b_i < 17$ , we obtain that as a and b are positive, then there are 12 possibilities for a and 16 for b, so by pigeonhole there are $x_i, x_j$ with the same a, b.

But if $x_i < x_j$ , then $a_i < a_j$ , and if $x_i > x_j$ , then $b_i < b_j$ trivially, contradiction. Hence, we must be able to find our subsequence.

Claim: If $N \geq mn+1$ , then every sequence of $N$ distinct integers contain either a subsequence of length $m+1$ with increasing terms, or a subsequence of length $n+1$ with decreasing terms.
Proof:
Let $A_k$ is the maximum length of increasing subsequence with the last element $k$ and $B_k$ is the maximum length of decreasing subsequence with the first element $k$ for any number $k$ in the sequence.
For 2 different numbers $k$ and $l$ in the sequence, we can easily see that either $A_k \neq A_l$ or $B_k \neq B_l$ must be satisfied.
Therefore, we have $N$ distinct pairs of $(A_k, B_k)$ with $k$ varies from $1,2,3,\dots , N$ .
Assume that all increasing subsequences have length less than $m+1$ and all decreasing subsequences have length less than $n+1$ .
The value of $A_k$ varies from $1,2,3,\dots , m$ and the value of $B_k$ varies from $1,2,3,\dots ,n$ .
Then the maximum number of distinct pairs $(A_k, B_k)$ is $mn$ .
If $N\leq mn$ , we are still able to find a subsequence of length less than $m+1$ with increasing terms and a subsequence of length less than $n+1$ with decreasing terms.
However, we have $N \geq mn+1$ distinct pairs $(A_k, B_k)$ .
And the pigeonhole principle leads to a contradiction.
So, every sequence of $N$ distinct integers contain either a subsequence of length $m+1$ with increasing terms, or a subsequence of length $n+1$ with decreasing terms.
The claim has been proven.
Luigis claims that he can find either a subsequence of length 13 with increasing terms or a subsequence of length 17 with decreasing terms.
So, the minimum number $N$ is $12 \times 16 +1 = 193$ .
And we are done.

We associate to each number $x$ in the list a value $i_x$ such that taking the longest (or one of the longest, if there are more) decreasing subsequence containing $x$ , $x$ will be in the $i_x$ -th position.

Supposing that there is no $n$ in the list is such that $i_n \geq 17$ , we have to find what is the smallest $N$ such that there will have to be subsequence of length $13$ where all the terms are increasing.

By the pigeonhole principle, we will have $13$ numbers with the same $i_x$ associated if there are $(17-1)\cdot (13-1)+1=193$ numbers. And we might not have $13$ numbers with the same $i_x$ if there are less than $193$ numbers.

( $(17-1)$ is the number of different values for the $i_n$ )

The $13$ numbers with the same $i_x$ will form an increasing subsequence, because supposing that this is not true (and two of these numbers let's say $a$ and $b$ will be decreasing $a>b$ ) we will have that $i_b$ is at least $i_a+1$ , that is a contradiction. Therefore the solution is: $\fbox{193}$

The following claim is proved first. Every sequence $a_1, a_2, ..., a_k$ [where $k= mn+1$ ] of $mn+1$ distinct real numbers contains either an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$ .

Proof:- Let $x_i$ denote the length of the longest increasing subsequence starting with $a_i$ , and let $y_i$ denote the length of the longest deceasing subsequence starting with $a_i$ . Then we prove that all of the $mn+1$ ordered pairs $(x_i, y_i ), 1 \leq i \leq mn+1$ are distinct. Consider two distinct integers $i, j$ such that $1 \leq i < j \leq mn+1$ . We observe that $a_ i< a_j$ implies $x_i > x_j$ , since for every increasing subsequence starting with $a_j$ , we can add $a_i$ at the beginning of it and obtain another increasing subsequence which starts with $a_i$ , and it will still be increasing because of the fact that $a_i < a_j$ . Similarly, $y_i < y_j$ , since for every decreasing subsequence starting with $y_i$ we can add $y_j$ at the beginning of it and it will still be decreasing because of the fact that $a_j > a_i$ . Hence all of the $mn+1$ ordered pairs $(x_i, y_i), 1 \leq i \leq mn+1$ are distinct. Now on the contrary assume that the claim to be proven is not true. Note that for each $i$ we have $1 \leq x_i \leq m$ and $1 \leq y_i \leq n$ . Thus there are $m$ possible distinct values for $x_i$ , and $n$ possible distinct values of $y_i$ . By the rule of product we can conclude that only $mn$ of the $mn+1$ ordered pairs $x_i, y_i$ can be distinct. By the pigeonhole principle atleast 2 of the ordered $mn+1$ pairs $x_i, y_i$ must be equal, a contradiction to the statement proved previously which states that all the pairs $x_i, y_i$ must be distinct. Also note that the numbers chosen are not provided, and the smallest number on which pigeon hole principle works for is $mn+1$ . For any number smaller than this, our argument won't work and we can find a set with that number of elements not satisfying the given conditions. In the question $m+1= 13 \implies m= 12$ and $n+1= 17 \implies n= 16$ . Hence answer= $mn+1 = 12*16+1= 193$ .

1. Use $n_k$ to represent the $k$ th number in the sequence.

2. Label each number of the sequence as $(a_1,b_1), (a_2,b_2), (a_3,b_3), \ldots, (a_N,b_N)$ in which $a_k$ represents the length of the longest monotonically increasing sequence ending at $n_k$ and $b_k$ represents the length of the longest monotonically decreasing sequence ending at $n_k$ .

3. Because all numbers are distinct, therefore two number cannot have identical label $(a,b)$ . If $i>h$ and $n_i>n_h$ , then $a_i>a_h$ . If $n_i<n_h$ , then $b_i<b_h$ .

4. If there is neither a subsequence of length 13 with increasing terms nor a subsequence of length 17 with decreasing terms present in the sequence, we must have $a_{max}=13-1=12, b_{max}=17-1=16$ . Hence, the total number of numbers permitted in the list if there is no subsequence length 13 with increasing terms nor a subsequence of length 17 with decreasing terms is $12\times16=192$ .

5. Therefore, the minimum N required for Luigis's claim to be true is $12\times16+1=193$ .

Note that the exact integer values don't matter, only their relative values. Hence, we may replace the integers with an ordering from $1$ to $n$ . If $n = (12)(16) = 192$ , then Mariolys can order the numbers $16, 15, \ldots, 1, 32, \ldots 17, 48, \ldots 33, \ldots, 192, \ldots 177$ . Any decreasing subsequence must be consecutive and has length at most 16, while any increasing subsequence must use one from each consecutive decreasing subsequence, so has length at most 12. If $n \geq 193$ , then for each $1 \leq k \leq n$ , we let $i(k)$ be the length of the longest increasing subsequence that starts with $k$ , and $d(k)$ be the length of the longest decreasing subsequence that starts with $k$ . Given any two numbers $j, k$ with $j \neq k$ , we have $( i(j), d(j) ) \neq ( i(k), d(k) )$ . If $i(k) < 13$ and $d(k) < 17$ , then there are at most $12 \times 16 = 192$ possibilities, which contradicts the fact that there are 193 numbers. Hence, the minimum size of the list is 193.

Note: This is a specific instance of Dilworth's Theorem.

Two words: Erdős-Szekeres :P

(One also needs to show tightness of the bound, but this is fairly straighforward if you know why Dilworth's theorem is true: just paste together 12 copies of a decreasing sequence of length 16.)

The answer is 193. The sequence is built from left to right. Draw a line between any two integers that are a subset of an ascending subsequence. In other words, connect each number to every larger number on its right.

Now, we have transformed the problem into an identical one:

(The interconnecting lines between numbers are taken as friendship-denoting lines, and the numbers which are not connected to each other are taken to be strangers.)

There are N people in a random Facebook group. What is the minimum value of N such that there must either be 13 people who are all friends, or 17 people who are all strangers?

Solution: We show that the case does not hold for N =192. We may divide 192 people to construct 16 groups of 12 people each, with members of each group all being friends with other members of the same group. No friendship is formed between different groups. Evidently, there are no 13 people who are all friends. Also, by the pigeonhole principle, by choosing any 17 people from the 16 groups, one group must contain two of them. Hence, the two are friends, and no 17 people can be strangers in this setup.

Now we look at N =193. We add in a new person P and attempt to draw friendship-denoting lines connecting P with the earlier 192 people until there are enough lines such that no 17 people are strangers, yet there are no 13 people who are all friends. We will see that this is impossible, that is, there is at least one group containing members who are all friends with P.

As long as there is no such group, we can find one member from each group who is detached from P, making a total of 17 strangers, forcing a line to be drawn from P to one of the 16 chosen members (since there can be no friendships between different groups). Repeating this iteration strictly decreases the number of people detached from P, until eventually one group must have all its members connected to P. This group, together with P, makes 13 interconnected friends!

This completes the proof by contradiction.

When the question asks for the minimum value so that a condition can be ensured, it is often that we have to assume the worst-case scenario. In this case, we find the longest sequence of distinct integers such that any of the desired subsequences cannot be found.

From the question, a desired subsequence would be one of length 17 with decreasing terms. Thus, we assume the first 16 integers to be descending like in the sequence $16,15,14,13 \ldots 3,2,1$ . This does not fulfill either of the two desired subsequences.

Other numbers could be chosen and they don't necessarily have to be consecutive like the example, but the above sequence will be used for simplicity's sake.

We then continue to add strings of 16 consecutive descending integers, being wary so that they do not repeat. The sequence becomes:

$\overline{16},15,14\ldots 3,2,1,\overline{32},31,30 \dots 19,18,17,\overline{48},47,46 \ldots 35,34,33 \ldots$

The overlined integers indicate the starting of a new length 16. Also, the overlined integers also give an example of the longest subsequence of increasing integers of length 3, assuming the entire list was 48 terms long.

Hence, continuing this process of adding strings of 16, we reach a point when the ascending subsequences are of length 12, where there is a total of $16 \times 12=192$ terms. At this point, if we add another larger unused integer as the next term (193, in this case), this will cause a subsequence of 13 increasing terms to be formed; if we add another integer that is smaller than all the terms on the list (eg. 0), this will cause a subsequence of 17 decreasing terms to be formed. Since this sequence will form a desired subsequence no matter what is added next, it is the shortest list of integers such that Luigis' claim is true.

Thus, $N=16 \times 12 + 1=193$ .