2016 IMO Problems/Problem 4
Problem
A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let . What is the least possible positive integer value of such that there exists a non-negative integer for which the set is fragrant?
Solution
Consider and . We note that in order to and we must have and . It is obvious that since or .
If then implies . WLOG, we can let and see that . So there doesn't exists so that .
If , we find and we let . Hence, from we get . So there is one prime such that .
If , it is obvious that satisfy and is the only answer.
If , we do the similar thing and get and so . ___________________________ Now, back to the problem, since there doesn't exists any prime for so . The only prime for is so if we choose then there will be a number remains. This means since we need a prime and but since .
If , we consider two cases, where there are two numbers that are divisible by (which means ), the middle-three numbers we can't find a way make each two of them have common prime factor. If no two are divisible by then they can only be divisible by , but it can't cover all "consecutive" numbers.
If then we can pick .
So the final answer is .
See Also
2016 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |