18.3.2. Pigeonhole Principle Argument

Try these first

1. 1.

   Define a strictly increasing sequence.

   Hint

   Think about how numbers can be arranged.

2. 2.

   What does the Pigeonhole Principle state?

   Hint

   Consider how this applies to simple grouping.

3. 3.

   What is a strictly increasing sequence?

   • A sequence where all elements are the same
   • A sequence where each element is larger than the previous
   • A sequence in descending order

   Hint

   Think about how numbers grow.

4. 4.

   True or False: The Pigeonhole Principle can always be applied to find a repeated value in sets.

   • True
   • False

   Hint

   Reflect on grouping elements.

5. 5.

   Given the set of integers {1, 2, ..., 10}, prove that in any selection of 6 values, either there will be a strictly increasing or a strictly decreasing subsequence of length 4.

   Hint

   Think about maximum sequences you can get.

6. 6.

   For the sequence (3, 5, 2, 4, 1), identify the increasing and decreasing subsequences of maximum length.

   Hint

   Look for sequences that can skip numbers.