Problem: (1970 IMO - #1) Find all positive integers $n$ such that the set $\{n,n+1,n+2,n+3,n+4,n+5\}$ can be partitioned into two subsets so that the product of the numbers in each subset is equal.
Solution: We claim that no such $n$ exists.
First, suppose one of the elements has a prime factor $ > 5 $. Then clearly none of the other elements has the same prime factor; therefore, any partition will create one set with that prime factor and one without it. Hence none of the elements has a prime factor $ > 5 $.
Now take the set modulo $ 5 $. By the same argument above, there must be two elements divisible by $ 5 $. But the first and last are the only two elements that differ by $ 5 $, so $ n \equiv n+5 \equiv 0 \pmod{5} $.
Consider the elements $n+1, n+2, n+3, n+4$. Two of them can be divisible by $ 2 $. Of the remaining two, however, only one can be divisible by $ 3 $ (since they differ by $ 2 $). Hence there exists an element that is divisible by neither $2, 3, $ nor $5$. Then it must have a prime factor $ > 5 $, which gives us a contradiction.
So no such $ n $ exist, as desired. QED.
--------------------
Practice Problem: Find an $ n $ such that the above condition holds for the set $ \{n,n+1,\ldots,n+7\} $ or prove that none exist.
Assme that such a set exists - clearly, no element has a prime factor greater than 7, and thus must have prime factors of 2, 3, 5, and/or 7.
ReplyDeleteBy mod 7, the only two numbers which are equivalent are n and n+7, thus these two must be multiples of 7 --> 7k and 7k+7, and all other numbers in the set cannot have a 7 as a prime factor.
In the remaining 6 numbers, it is clear that 2 of these are multiples of 3, and that the rest (four) numbers are not multiples of 3.
Of the two numbers that were accounted for directly above, one must have been odd and one must have been even, as these elements would have the form m and m+3.
Within the remaining 4 numbers, then, we have 2 odd and 2 even numbers. These two odd numbers cannot both be multiples of 5, since the have the same parity but the absolute value of the difference is less than 10.
Thus, there exists an odd number, not divisible by 3, 5, or 7 - this implies that it has a prime factor greater than 7, but this gives us a contradiction, so no such set exists.