Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
18.2.2. Achieving Disjoint Groups
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we're diving into subsequences. A subsequence can be derived from another sequence while maintaining the original order, even if they are not consecutive. For instance, in the sequence 1, 3, 0, -5, 2, 8, we can form a subsequence like 1, -5, 2.
So, does that mean any selection from a sequence, maintaining the original order, is a subsequence?
Exactly! And remember, subsequences can be strictly increasing or decreasing. Can anyone provide an example of each type?
For a strictly increasing example, we could use 1, 3, 5. And for decreasing, maybe something like 5, 3, 1?
Great examples! Remember that ordering matters. We'll explore more about these subsequences and how we use them in broader mathematical proofs.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let’s discuss the pigeonhole principle. This principle tells us that if we have more items than containers, at least one container must contain more than one item.
Can you give an example of that, maybe in everyday life?
Sure! Imagine you have 10 pairs of shoes but only 9 slots in your closet. At least one slot will have two pairs of shoes. In our case, we will apply it to our subsequences to prove their existence.
How does that relate to our earlier discussion on subsequences?
It’s instrumental because it helps demonstrate that within our sequence of distinct real numbers, there must exist subsequences of sufficient length that are either increasing or decreasing.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let’s apply this to a practical example. Consider 9 people whose ages range from 18 to 58. Using the theories we've discussed, can we claim there are disjoint groups with the same sum of ages?
I think using the pigeonhole principle again might help! We can form various subsets of those 9 individuals.
Correct! And since there are 511 non-empty subsets and the sum can only range from 18 to 522, we ensure that at least two of those groups must yield the same total.
What if there are overlaps in the groups? Doesn’t that affect the result?
Good question! Even if the groups overlap, if they share common individuals, we can remove those to create completely disjoint groups while preserving the sum equalities.
Overview
Short Summary
This section discusses the establishment of disjoint groups of distinct real numbers ensuring subsequences that are either strictly increasing or decreasing.
Medium Summary
The section explains the concept of subsequences within an arbitrary set of distinct real numbers and uses the pigeonhole principle to demonstrate the existence of either a strictly increasing or strictly decreasing subsequence. It practically applies these concepts to illustrate how to organize distinct ages into groups with the same sum.
Detailed Summary
Achieving Disjoint Groups
This section focuses on demonstrating that within any sequence of n + 1 distinct real numbers, we can always find a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.
Key Concepts Detailed:
-
Subsequences: A subsequence is defined as a sequence derived from another sequence where elements may not be consecutive but retain the original order. An example is taking a subset from a sequence like 1, 3, 0, -5, 2, 8, and forming a subsequence such as 3, 2, 8. The same principle applies to increasing and decreasing sequences.
-
Long Increasing/Decreasing Subsequences: We refer to a sequence of numbers that successively increases or decreases. The lengths of such subsequences can be denoted as L(i) for increasing and D(i) for decreasing, representing the length starting at index i.
-
Pigeonhole Principle: This concept is crucial in proving the existence of either subsequence lengths greater than or equal to n + 1. By considering pairs of indices from the arbitrary sequence, we use the pigeonhole principle to demonstrate that at least one subsequence must exist that is either strictly increasing or strictly decreasing.
The section concludes with an application of these principles to a tangible problem, where we can always form two disjoint groups of people from a set of nine individuals whose ages are distinct and within a given range, proving that their sum can be the same.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountIn this question we want to show the following: you are arbitrarily picking 9 people in the age group of 18 to 58. That means the minimum age it is allowed is 18; the maximum age is allowed 58.
Detailed Explanation
This section introduces the problem of selecting 9 individuals within a specific age range (18 to 58 years). We will find two distinct groups among these people such that the sum of their ages is the same.
Examples & Analogies
Imagine a group of 9 friends who range in age from young adults to middle-aged. Regardless of their specific ages, the aim is to divide them into two groups that have the same total age, showcasing an interesting threshold of the relationships among numbers.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountNow we want to prove that irrespective of what exactly are their ages, as long as they are in the range 18 to 58, it is always possible to choose 2 disjoint groups of people out of these 9 people whose sum of ages is the same.
Detailed Explanation
To approach this proof, we will apply the pigeonhole principle, which states that if more items are put into fewer containers than there are items, then at least one container must hold more than one item. Here, we set non-empty groups of people as our 'pigeons' and the possible sums of ages as our 'holes'.
Examples & Analogies
Think of a box with limited slots to hold the different weight combinations of toys. If you have more toys than slots, some weights will inevitably be repeated in certain slots, reflecting the potential for matching sums of age among groups.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThe minimum sum of ages possible in a group could be 18, and the maximum possible sum can occur when all the 9 people have the maximum age of 58.
Detailed Explanation
The smallest age sum of 18 is achieved by just one person aged 18. In contrast, if all 9 individuals are 58 years old, the maximum age sum would be 522 (9 multiplied by 58). Hence, the range of possible sums of ages spans from 18 to 522.
Examples & Analogies
Imagine a party where the youngest guest is 18 years, and the oldest is 58. If you sum their ages, the variety of combinations could range from just having the youngest guest to everyone attending being 58, showing how different combinations can lead to different outcomes.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountIf I consider 511 possible non-empty subsets of these 9 people and the range of sum of ages is from 18 to 522, the pigeonhole principle implies that there must exist at least one pair of groups with the same age sum.
Detailed Explanation
With 511 unique combinations, and only 505 possible outcomes for the sums of ages (from 18 to 522), at least one age sum must repeat between different groupings. This guarantees that two disjoint groups will share the same total age sum.
Examples & Analogies
Think about having 511 different gift baskets with different possible weights, while only being able to balance them against a limited number of weights. If you have more baskets than weights, at least two baskets must end up with the same weight, creating a parity that guarantees balance.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThe question wants me to show that the groups should be disjoint. If the sets A and B are not the same, I can remove the common people from both sets.
Detailed Explanation
To ensure that the two groups we form are disjoint, we can take any overlapping individuals from Group A and Group B and exclude them. Since these individuals contribute equally to both sums, their removal does not affect the equality of the sums but ensures that the groups do not share any members.
Examples & Analogies
If there are two teams of players that include some of the same players, removing the overlapping players will help form two distinct teams. If both teams had equal score contributions from the removed players, their new totals will remain equal while becoming entirely separate.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Subsequences:
A subsequence is defined as a sequence derived from another sequence where elements may not be consecutive but retain the original order. An example is taking a subset from a sequence like 1, 3, 0, -5, 2, 8, and forming a subsequence such as 3, 2, 8. The same principle applies to increasing and decreasing sequences.
- Long Increasing/Decreasing Subsequences:
We refer to a sequence of numbers that successively increases or decreases. The lengths of such subsequences can be denoted as L(i) for increasing and D(i) for decreasing, representing the length starting at index i.
- Pigeonhole Principle:
This concept is crucial in proving the existence of either subsequence lengths greater than or equal to n + 1. By considering pairs of indices from the arbitrary sequence, we use the pigeonhole principle to demonstrate that at least one subsequence must exist that is either strictly increasing or strictly decreasing.
The section concludes with an application of these principles to a tangible problem, where we can always form two disjoint groups of people from a set of nine individuals whose ages are distinct and within a given range, proving that their sum can be the same.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
From the sequence 1, 3, 0, 2, we can find subsequences like 1 and 2 that are strictly increasing.
A practical example involves 9 distinct ages where we can form substrings that match the sum, hence demonstrating the pigeonhole principle effectively.
Memory aids
In an order you'll hide, a subsequence will ride, some numbers will abide, while others set aside.
Imagine a group of friends at a party each holding distinct ages between 18 and 58, and how they can pair up based on shared interests but also ensuring no two can be from the same age.
To remember the steps for finding subsequences: S-Select, M-Maintain order, and J-Judge elements.
Flash Cards
Glossary
Subsequence
A sequence derived from another sequence by retaining the original order but allowing for non-consecutive elements.
Strictly Increasing Sequence
A sequence where each element is greater than the previous, maintaining order without repeats.
Pigeonhole Principle
A principle that states if more items are put into fewer containers, then at least one container must contain more than one item.
Disjoint Groups
Groups that do not overlap, meaning no elements are shared between the two groups.