Equal products? Surely not

What is the sum of all positive integers n n , such that we can find two disjoint, non-empty subsets of the set S = { n , n + 1 , n + 2 , n + 3 , n + 4 , n + 5 } S = \{n,n+1,n+2,n+3,n+4,n+5\} such that the product of the elements in both sets is the same?


The answer is 6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Calvin Lin Staff
May 13, 2014

Let A , B A,B be the two subsets of S S and let A A be the one with the least number of elements. Let N N be the set of values of n n for which the desired subsets exist. Suppose A A has one element. The largest value for the product of the elements in A A is n + 5 n + 5 . The smallest value for the product in B B is n ( n + 1 ) n(n+1) (We take the least possible number of elements and the smallest elements). When n 3 n \geq 3 we have n ( n + 1 ) > ( n + 5 ) n(n+1) > (n+5) , so we need only consider n = 1 , 2 n = 1, 2 . When n n is 1 or 2, A = { 6 } , B = { 2 , 3 } A = \{6\}, B = \{2,3\} works, so 1 , 2 N 1,2 \in N .

Suppose A A has two elements. If B B has three or more elements, the smallest possible value for the product of B B is n ( n + 1 ) ( n + 2 ) n(n+1)(n+2) and the largest possible value for the product of A A is ( n + 4 ) ( n + 5 ) (n+4)(n+5) . When n 3 n \geq 3 we have n ( n + 1 ) ( n + 2 ) > ( n + 4 ) ( n + 5 ) n(n+1)(n+2) > (n+4)(n+5) so we are done (Since we know 1 , 2 N 1,2 \in N ).

If A A and B B each have two elements, with the same product, then of the 4 elements between the sets, one set must have the largest and smallest elements (let's assume this is A A ) and the other set B B must have the middle two elements. The sum of the elements in A A cannot be the same as the sum of the elements in B B since ( x k ) ( y + k ) < x y (x-k)(y+k) < xy for x < y x < y and k k positive. As such, the difference between the elements in A A have to be at least 4. If the difference between the elements in A A is 4, (say they are x x and x + 4 x+4 ) , by the previous discussion, the elements of B B cannot be x + 1 x+1 and x + 3 x+3 . If the elements of B B are x + 1 x+1 and x + 2 x+2 , then x ( x + 4 ) = ( x + 1 ) ( x + 2 ) x = 2 x(x+4) = (x+1)(x+2) \Rightarrow x=2 . So the numbers would have to be 2 , 3 , 4 , 6 2,3,4,6 , which only occur in S S when n = 1 , 2 n = 1,2 , both of which we already know are in N N . If the elements in B B are x + 2 x+2 and x + 3 x+3 , then x ( x + 4 ) = ( x + 2 ) ( x + 3 ) 0 = x + 6 x(x+4)=(x+2)(x+3) \Rightarrow 0 = x + 6 , so the numbers would have to be 6 , 4 , 3 , 2 -6, -4, -3, -2 , which is not applicable.

If the difference between the elements in A A is 5 (say they are x x and x + 5 x+5 ), then the elements of B B can only be { x + 1 , x + 2 } \{x+1,x+2\} or { x + 1 , x + 3 } \{x+1,x+3\} For these possibilities, we get x = 1 x =1 and x = 3 x = 3 , so the sets A , B A,B can only exist for values of n 3 n \leq 3 , which we know are in N N . When x = 3 x = 3 , we have A = { 3 , 8 } , B = { 4 , 6 } A = \{3,8\}, B = \{4,6\} so 3 N 3 \in N .

If A A has three elements, then B B also has three elements. [See Laurent Shorts' solution for a quick reason why this is not possible. My original reasoning is painful to wade through] Since we have six consecutive numbers, we either have the first and last are multiples of 5 or only one is a multiple of 5. For the elements of A A and B B to have the same product, they must each contain a multiple of 5, since at least one of them will. Thus, we may assume that n A n \in A and n + 5 B n + 5 \in B . If n + 4 B n + 4 \in B , since ( n + 5 ) ( n + 4 ) ( n + 1 ) > ( n + 3 ) ( n + 2 ) ( n ) (n+5)(n+4)(n+1) > (n+3)(n+2)(n) , the elements of B B would always have a larger product than the elements in A A so n + 4 A n + 4 \in A . Similarly, if n + 1 A n+1 \in A , since ( n + 5 ) ( n + 3 ) ( n + 2 ) > ( n + 4 ) ( n + 1 ) ( n ) (n+5)(n+3)(n+2) > (n+4)(n+1)(n) , the elements of B B would always have a larger product than the elements in A A , so n + 1 B n+1 \in B . Since ( n + 1 ) ( n + 5 ) > ( n ) ( n + 4 ) (n+1)(n+5) > (n)(n+4) we must have n + 3 A n + 3 \in A and n + 2 B n+2 \in B . So we have A = { n , n + 3 , n + 4 } , B = { n + 1 , n + 2 , n + 5 } A = \{n,n+3,n+4\}, B = \{n+1,n+2,n+5\} . However, n + 5 > n + 4 n + 5 > n+4 and ( n + 1 ) ( n + 2 ) > ( n ) ( n + 3 ) (n+1)(n+2) > (n)(n+3) so the elements of B B will always have a larger product than the elements of A A .

Hence, the sum is 6.

黎 李
May 20, 2014

Check that for N 30 N \leq 30 , we only have N = 1 , 2 , 3 N=1,2,3 which yield solutions.

When N > 30 N>30 , the subsets must have equal size since n ( a + 1 ) > ( n + 5 ) a n^(a+1)>(n+5)^a for a 3 , n 30 a \leq 3, n \geq 30 . Clearly, the size can not be 1. For any x , y x,y in S, gcd ( x , y ) 5 \gcd(x,y) \leq 5 . If the size is 2, x y = z w xy=zw , then x z w x|zw , but gcd ( x , z ) 5 \gcd(x,z) \leq 5 , gcd ( x , w ) 5 \gcd(x,w)\leq5 , and hence x 5 5 = 25 x\leq 5*5=25 , contradiction. If the size is 3, x y z = w p q xyz=wpq , there must be an adjacent pair the two of which on different side, say x w = 1 |x-w|=1 , then use the same argument and we have x gcd ( x , w ) × gcd ( x , p ) × gcd ( x , q ) 1 × 5 × 5 = 25 x \leq \gcd(x, w) \times \gcd (x, p) \times \gcd(x, q) \leq 1 \times 5 \times 5 = 25 .

Laurent Shorts
Feb 5, 2017

Here's a proof that it is impossible for the two sets to have all 6 elements together.

Suppose we use all 6 elements. If one of the elements is divisible by 7, it's the only one. But then, the set containing makes a multiple of 7, but not the other; they can't be equal. So no element is divisible by 7.

Modulo 7, our set is now {1,2,3,4,5,6}.

Let X be a subset with some of the numbers, and Y with the others. The product x of numbers in X equals the product y of numbers in Y, so that x·y=x·x, a square, and thus x·y can only be 1, 2 or 4, as those are the only squares modulo 7.

But x·y is 1·2·3·4·5·6, which equals 6 modulo 7. That's a contradiction.

Ah, that's a nice argument that we cannot use up all 6 elements. Much better than my last paragraph. Let me redirect people to your solution :)

Calvin Lin Staff - 4 years, 4 months ago

Clearly 1,2 & 3 support the condition...4,5 & onwards the set S would either contain 2 or more primes,which means they can't be included in the subsets,as they would reduce the chances of products being equal...or the set would include numbers larger than those possible for sufficing the given conditions...1.2 & 3 possess specific subsets' equated sums....larger numbers can't allow such a set having such properties,as the numbers would be coprime,& differing than quite a big factor....

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...