18. Subsequence Existence

Try these first

1. 1.

   Define a subsequence.

   Hint

   Think about maintaining the original order.

2. 2.

   True or False: A subsequence must include all elements of the original sequence.

   Hint

   Consider what it means to 'skip' elements.

3. 3.

   What is a subsequence?

   Hint

   Think of it like picking items from a list.

4. 4.

   True or False: Every sequence has multiple possible subsequences.

   • True
   • False

   Hint

   Remember that we can skip elements to form new sequences.

5. 5.

   In a given sequence of 10 distinct heights of people, demonstrate the existence of either an increasing or decreasing subsequence of at least 5 heights.

   Hint

   Utilize combinatorial reasoning to pair heights effectively.

6. 6.

   Prove that if you add an element to a sequence already with a defined increasing subsequence, it can either enlarge that subsequence or create a new one.

   Hint

   Consider where the new element would naturally fit within the existing sequence.