1991 IMO Problems/Problem 3
Contents
Problem
Let . Find the smallest integer such that each -element subset of contains five numbers which are pairwise relatively prime.
Solution 1
Let's look at this another way. We aim to find the least number of integers we can remove from S to leave a set which does not contain 5 pairwise coprime integers.
Let And more generally And finally It is clear that these sets taken over all collections of primes and 1 forms a partition of S.
If there are representatives from five sets , there are five mutually coprime integers, so all but four of the sets must be completely removed. It is clear that (with the exception of 1, which can clearly be removed first) if so it is worth removing before removing (if we are striving for a minimum). Furthermore, if we remove two sets , we must also (to stop there from being 5 mutually coprime integers) remove and so on, and these have similar ordering relations. So once we have removed everything we need to keeping sizes of sets removed to a minimum, we are left with and the multi-index sets not coprime to all of these. In other words, we have the set of multiples of 2,3,5 and 7, which can be calculated (by lots of inclusion-exclusion) to have cardinality . Therefore, a subset of of size must contain 5 coprime integers.
This solution was posted and copyrighted by Ilthigore. The original thread for this problem can be found here: [1] Firstly note that . Therefore, we only need to check primes to check if a number from to is prime.
Solution 2
I claim the answer is . First, let's look at a subset of that consists only of multiples of . It is easy to calculate by PIE that the total number of elements in this set isNow, note that no matter what element subset we consider of this subset we just made, consisting of multiples of , we will always have at least of those elements that exist in the subset that share a factor greater than by the Pigeonhole Principle since . Thus, we know from this. We also know that there are composite numbers and prime numbers (obviously just ) in this subset of . Now we do casework on the numbers (we don't have to check higher numbers because remember !) to find the other composite numbers. We find that all of numbers, fills in the rest of the composite numbers from to . This gives a total of numbers when counted. So we can now count up the total as composite numbers and the remaining must be prime so prime numbers ( not included as prime or composite). Now suppose is a subset of our set such that ( represents its cardinality or the number of elements in the subset ). Also suppose that there is no element subset of such that all elements are relatively prime to each other. This means we would have to have at most prime numbers and at least composite numbers to make this subset . This means the set (everything that is in but not in ) has at most composite numbers. Now consider the following sets and notice that at least one of these must be a subset of !:And obviously each of these sets has elements that are all relatively prime numbers, as desired.
This solution was posted and copyrighted by Wave-Particle. The original thread for this problem can be found here: [2]
See Also
1991 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |