18.1.4. Pigeonhole Principle Application

Try these first

1. 1.

   What does the Pigeonhole Principle state?

   Hint

   Think about how items can be grouped.

2. 2.

   Give an example of a strictly increasing sequence.

   Hint

   Each term should be larger than the previous term.

3. 3.

   What does the Pigeonhole Principle guarantee?

   • It guarantees a unique solution.
   • It guarantees duplicates in containers.
   • It guarantees an increasing subsequence.

   Hint

   Think about how items can be distributed.

4. 4.

   True or False: Every sequence of 4 distinct numbers must have an increasing subsequence of length 3.

   • True
   • False

   Hint

   Try arranging 4 numbers differently.

5. 5.

   Given a set of numbers {6, 2, 4, 8, 7}, find all increasing subsequences of at least length 3.

   Hint

   Use combination of mappings to construct new subsequences.

6. 6.

   Show that for any set of 10 distinct integers, there must exist an increasing subsequence of length 4.

   Hint

   Consider the distribution of integers in ranges.