2011 IMO Problems/Problem 1
Problem
Given any set of four distinct positive integers, we denote the sum by . Let denote the number of pairs with for which divides . Find all sets of four distinct positive integers which achieve the largest possible value of .
Author: Fernando Campos, Mexico
Solution 1
Firstly, if we order , we see , so isn't a couple that satisfies the conditions of the problem. Also, , so again isn't a good couple. We have in total 6 couples. So .
We now find all sets with . If and are both good couples, and , we have . So WLOG with and . It's easy to see and since are bad, all couples containing must be good. Obviously and are good (). So we have and .
Using the second equation, we see that if , , for some a positive integer.
So now we use the first equation to get , for a natural .
Finally, we obtain 1, 2 or 4. We divide in cases:
CASE I: . So and . But 3, 4,5 or 6. implies , impossible. when . We easily see and , impossible since . When , , and we get .Uf , and we get .
CASE II and III:2, 4. Left to the reader.
ANSWER: ,, for any positive integer .
(Note: The above solution looks generally correct, but the actual answer should be ,. You can check that doesn't actually work. -Someone who didn't write up the above solution but solved the problem in a similar way)
Solution 2 (Avoids the error of the first)
Similarly to the first solution, let us order the terms in set by since it is given that these four integers must be distinct and positive. Obviously, from this. We know that pair cannot work because Additionally, pair cannot work for the same reason:
Hence, since there were only pairs in total, and two pairs are guaranteed not to work, we are to find sets satisfying Due to our making the largest term of set , the only way to have a pair that exists such that is to make equal to 1 and find an such that When this happens, we know that , as well. It clearly follows that we need pairs and that exist such that both and divide
To satisfy conditions and , choose a set with four distinct positive integer elements with Obviously, for our set to consist solely of positive integers. The problem becomes to find and such that and
We realize that can be any positive even integer. This allows and to have a common factor of 2, simplifying our problem a bit. Hence, must divide Now, we can look at the other condition, , to solve this problem. To find satisfying , it suffices to define a positive integer that makes Note that must be less than If , would have solutions and that will make , since due to This is a contradiction with the condition that each element in set has to be positive. Despite this, We move on to some cases.
- cannot work because this makes at least one of the solutions to zero or negative, another contradiction.
- For , we have that We need to find possible values for such that that satisfy both and Note that because , the sum of our set is Hence, it suffices to call our terms and The only values for and that work are those such that and at the same time, and and at the same time. Hence, we get that or Moreover, it follows that or On a side note, because we are constrained to , or . Note that this completely satisfies because the and that we chose exists such that for , , and . At the same time, for , , and . In turn, we have the two sets and Since must be a multiple of 5 or 11, we can scale these two sets by multiplying by 5 and 11, respectively, to get sets and with being any or that results in positive integers for the first and second set, respectively. Remember that cannot be zero because our set must contain positive integers.
- cannot work because we have established that cannot be greater than or equal to Solving the inequality , cancels, resulting in This shows that any greater than or equal to 4 will not work for .
Thus, the only possible sets we have for satisfying the maximum , which is 4, are and , with being any positive integer since it is obvious that any that is a positive multiple of 5 or 11 makes and positive integers, respectively.
See Also
2011 IMO (Problems) • Resources) | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |