3
$\begingroup$

This challenge is about permutations of the integers 1 to 30 with longest increasing subsequence length 3. An important part of the definition is that a subsequence is not necessarily contiguous or unique.

Create a permutation of the sort described above with shortest possible longest decreasing subsequence.

The permutation 30 29 28 ... 4 1 2 3 has longest increasing subsequence length 3, as required, but its longest decreasing subsequence has length 28, which is not the shortest possible.

$\endgroup$

1 Answer 1

5
$\begingroup$

A best possible sequence is

28 29 30 25 26 27 22 23 24 19 20 21 16 17 18 13 14 15 10 11 12 7 8 9 4 5 6 1 2 3

which has a longest increasing subsequence of length 3 and a longest decreasing of length...

10. Indeed there are $3^{10}=59049$ such subsequences which are generated by picking one element from the first triple, one from the second triple and so forth.

Another example is

28 25 22 19 16 13 10 7 4 1 29 26 23 20 17 14 11 8 5 2 30 27 24 21 18 15 12 9 6 3

which has

$11\times 12/2=66$ different decreasing subsequences of length 10 and $10\times 11\times 12/6=220$ increasing subsequences of length 3.

These are best possible because

Consider three subsets of our integers $S_1$ the set of elements for which there is no greater element to its right; $S_2$ the set of elements for which there is no lesser element to its left and $S_3$ the set of elements for which any greater element to the right belongs to $S_1$ and for which any lesser element to the left belongs to $S_2. These sets are clearly disjoint and, because there are no increasing subsequences of length greater than 3, every element of our complete set lies in one of these subsets. It follows that one of these subsets has at least ten members. We also note that each of these subsets is a decreasing subsequence. QED

$\endgroup$
2
  • $\begingroup$ It might be hard to count all the possible optimal solutions. $\endgroup$
    – Simd
    Nov 25, 2023 at 10:19
  • 3
    $\begingroup$ You can streamline your proof by one simple modification (everything else works just as it does now): Define S_j as the set of numbers such that j is the maximum length an increasing subsequence ending at that number can have. That is shorter, easier to follow, I think, and readily generalises to increasing subsequences of maximum length other than 3. $\endgroup$ Nov 26, 2023 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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