Let be a positive integer. . There are pairwise different numbers written on a blackboard. Show that we can choose two of those numbers so that no number from the blackboard multiplied by is equal to a multiple of their sum.
Solution
Denote the numbers by . Without loss of generality we may assume that . Let us show we may also assume that not all of these numbers are divisible by . If are all divisible by , then there exists a positive integer such that divides for all , as well as a positive integer such that does not divide . If this is the case, then are pairwise different positive integers, which are not all divisible by . Assume that there exist two among them, such that does not divide any of the numbers . Then does not divide .
Let and assume are not all divisible by . We will prove the claim by contradiction. If the claim is not true, then for every sum there exists an index such that is a multiple of this sum. In particular, this holds for , so divides for some . If is not divisible by , then divides . This is impossible since . So, divides for all . At least one of the numbers is not divisible by which implies none of them are and all give the same remainder when divided by .
This remainder is non-zero, so is not divisible by for . Now, divides , so divides . This is only possible if . Hence, all divide .
We know that for some and some positive integer . Obviously, implies , so or . If , then , which would imply and . We have shown that divides and when we have , so or . This is not possible since all the numbers on the blackboard are different. We conclude that .
We have shown that for some . Since
we have . If then , but this is not possible since . Hence and . As above, since and divides , we have or . This contradicts the assumption that all numbers are different.
We have arrived at a contradiction and we can conclude that it is always possible to choose two of the numbers so that any other number from the board multiplied by is different from their sum.