Split into Groups
Lesson · Intermediate
Combinatorics
When we want to prove that some selected objects must have a certain relationship, it can be useful to split all possible objects into carefully chosen groups.
Key Idea
1. Determine the relationship you want to force.
2. Split the objects into groups based on that relationship.
Fourteen distinct integers are selected from
Prove that two of the selected integers differ by 7.
Split the numbers into the following 13 groups:
There are 13 groups.
Since 14 numbers are selected, by the Pigeonhole Principle, at least two selected numbers must belong to the same group, and their difference is 7.
Eleven distinct integers are selected from
Prove that one of the selected integers divides another.
Write every positive integer uniquely as
where m is odd.
Group the numbers according to their odd part:
and similarly for the remaining odd parts.
There are 10 groups, corresponding to the 10 odd numbers from 1 to 20.
If 11 numbers are selected, two must belong to the same group.
They have the form
so the smaller divides the larger.
What is the largest possible subset of
such that no two selected numbers have sum 51?
Split the numbers into pairs:
There are 25 groups.
From each pair, we can select at most one number.
Therefore, at most 25 numbers can be selected.
This is attainable by selecting
Therefore, the maximum is 25.
Twenty-one distinct positive integers are selected from
Prove that two of them have a product that is a perfect square.
Every positive integer can be written uniquely as
where s is squarefree.
Group the numbers according to their squarefree part s.
There are 20 groups, so two numbers are selected from the same group and their product is a perfect square.