Products of Partitions
True or False?
It is possible to partition the set of the first 2026 positive integers { 1 , 2 , 3 , … , 2 0 2 6 } into exactly two subsets such that the product of all the elements in each subset is the same.
Note: 2027 is a prime number.
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.
19 solutions
Moderator note:
As Kyle Coughlin points out in the comments, this argument relies on Bertrand's postulate , that
For every positive integer n > 1 there exists at least one prime p such that n < p < 2 n .
A very slight tweak results in an unsolved problem; in fact, one of the most famous of all unsolved number theory problems.
Legendre's conjecture :
For every positive integer n > 1 there exists at least one prime p such that n 2 < p < ( n + 1 ) 2 .
Also note that, by Bertrand's postulate, there exists at least one prime such that 1 0 1 3 < p < 2 0 1 6 , so there is guaranteed to be a prime that follows the above argument.
Call a to the product ∏ i ∈ A i and b to ∏ i ∈ B i . In the prime decomposition of a and b , for any prime p , the sum of the multiplicities must be even. So, if 1 3 ∈ A , then 2 1 9 7 = 1 3 3 ∈ B , but this is false, hence there is no partition as the required.
Although 1013 is prime, equality is obtained by 2, 1013 in one subset and 2016 in the other.However, 1019 is prime. It can only be in one subset, the other cannot have 1019 as a factor because 2038 > 2016. So equal products not possible
In short, as long as it holds a multiplier factor of a prime number on one subset (subset A), it is certain that there will be no divisor on another subset (subset B) of equal value to that prime number even by utilizing the multiplication of several numbers on another subset (Subset B), because the nature of prime numbers can only be divided by itself.
Thus, it is certain that the multiplication of the numbered members of each subset (subset A and subset B) will never be the same.
Note: Members of subset A or subset B can be random, not necessarily 1 ≤ S u b s e t A ≤ 1 0 1 3 and 1 0 1 4 ≤ S u b s e t B ≤ 2 0 2 6 , which needs is guaranteed only that in a subset must be found at least one prime number
Let 1 0 1 4 ≤ p ≤ 2 0 2 6 be a prime number, and X ∋ p and Y ∋ p the two subsets.
Clearly, p ∣ ∏ X . However, since no higher multiple of p is contained in the original set, p ∣ ∏ Y .
Thus ∏ X = ∏ Y .
Alternative solution 1
Choose a prime number just above 2 0 2 6 ≈ 4 5 : an easy choice is p = 4 7 . Now 4 3 × 4 7 = 4 5 2 − 2 2 = 2 0 2 1 ; it is clear that there are precisely 4 3 multiples of 4 7 in our set, and no multiples of 4 7 2 . Thus there are an odd number (43) of prime factor 47 to distribute equally over two sets, an impossibility.
Alternative solution 2
We can also start with the smaller primes.
Lemma : In the prime factor decomposition of N ! , N ! = 2 e 2 ⋅ 3 e 3 ⋅ 5 e 5 ⋯ , the exponents are equal to e p = p − 1 N − σ p ( N ) , where σ p ( N ) is the sum of the digits of the base- p representation of N .
If any of the e p is odd for N = 2 0 2 6 , i.e. if any of the σ p ( 2 0 2 6 ) is odd, these prime factors cannot be evenly distributed over two sets.
Now 2 0 2 6 1 0 = 1 1 1 1 1 1 0 1 0 1 0 2 , making σ 2 ( 2 0 2 6 ) = 8 and e 2 = 2 0 1 8 , even.
And 2 0 2 6 1 0 = 2 2 1 0 0 0 1 3 , so that σ 3 ( 2 0 2 6 ) = 6 and e 3 = 1 0 1 0 , even.
But 2 0 2 6 5 = 3 1 1 0 1 5 , making σ 5 ( 2 0 2 6 ) = 6 and e 5 = 5 0 5 , odd. Therefore we conclude that the partition cannot be made.
Log in to reply
Hi, Arjen The highest power of 5 to divide 2026! Is 5^505 You have missed a 1 from the units column of base 5 number, so digit sum is 6 2026-6 = 2020, Then you must divide by 4 (=5-1) Try it with 10! to see the need to divide by base-1
It's based on an assumption that this prime exists.
Log in to reply
It does, doesn't it? An example is 1 0 3 3 . It is an odd number of the form 4 k + 1 , can be written as the sum of two squares ( 3 2 2 + 3 2 ), and in a unique way (we only need to check 2 3 2 = 5 2 9 to 3 1 2 = 9 6 1 , and save work by realizing that squares can only end in 1 , 4 , 5 , 6 , 9 , 0 , and the only ways to have final digit 3 are 4 + 9 or 5 + 6 ). This proves that it is prime.
Log in to reply
I think what he was going for here (why he picked 1014) is that he is using the weak version of Bertrand's Postulate, namely, that there exists a prime between n and 2n+1 for all n. This allows his argument to be easily extended to larger numbers. https://en.wikipedia.org/wiki/Bertrand%27s_postulate
Suppose that it is possible to partition the integers in such a way. Let X , Y be sets such that X ∪ Y = { 1 , 2 , 3 , … , 2 0 2 6 } and X ∩ Y = ∅ . Let P ( X ) , P ( Y ) denote the products of the numbers in X , Y , respectively.
X , Y contain only integers, so P ( X ) , P ( Y ) are integers. Also note that P ( X ) P ( Y ) = 2 0 2 6 ! , since all the integers from 1 to 2026 inclusive are contained within X , Y .
We assume, for the sake of contradiction, that P ( X ) = P ( Y ) . Hence, by Wilson's Theorem, we have
P ( X ) 2 ≡ P ( X ) P ( Y ) ≡ 2 0 2 6 ! ≡ ( 2 0 2 7 − 1 ) ! ≡ − 1 ( m o d 2 0 2 7 ) .
This means 2 0 2 7 ∣ P ( X ) 2 + 1 . However, we know that if an odd prime number p divides x 2 + 1 for some positive integer x , then p must be of the form 4 k + 1 . The prime number 2 0 2 7 is of the form 4 k + 3 , so it can't possibly divide P ( X ) 2 + 1 .
Therefore, we have reached a contradiction, so we conclude that the statement is false : there is no way to partition the first 2026 positive integers into two sets such that the products of the elements of both sets are equal. ■
Generalization: Let p be a prime of the form 4 k + 3 . Then, it is impossible to divide a set of p − 1 consecutive positive integers into two subsets such that the product of the integers in both sets are equal.
A much quicker way is to consider the primes. Since 1997 is prime and we do not have 3994, hence we cannot split the product.
For the generalization, It's easier to use bertrand's postulate directly, to show that there is a prime between n and 2 n , hence we cannot split the products.
"However, we know that if a prime number p divides x 2 + 1 for some positive integer then must be of the form 4 k + 1 ."
This is not true: take x = 1 and p = 2 .
Log in to reply
Thanks for pointing that out. Any odd prime factor of x 2 + 1 must be of the form 4 k + 1 . . I have updated my solution.
There is a total of 1013 odd numbers at the start. No matter how partitioned, there would be one subset with an odd number of odd numbers and one with an even number of odd numbers, so one has to be even and the other odd. Not equal!
Log in to reply
That argument would work when working with the sum , but this problem is about a product .
For instance, 8 × 3 × 5 = 2 × 4 × 1 5 , even though the first product has two odd factors and the second product has only one.
All this is pretty deep for me, but if you just takproducts 1-4 and try to split them into equal subsets ,you can't do it
Seems to be asking if a factorial can be a square number - or can we prove a factorial cant be a square number
Log in to reply
It is not the same.
If a partition like this exists for { 1 , … , N } , then N ! is a square.
However, if N ! is a square, then this kind of partition does not necessarily exist.
Example: the product of { 6 , 1 0 , 1 5 } is a square, yet one cannot partition this set into two subsets of equal product.
Note that 2017 is a prime and 2017 only appears once in the prime factorization of 2 0 2 6 ! . Hence, 2017 will appear in exactly one of the two subsets. Therefore, such partition is impossible.
Hi Qi,
That is really neat! I think you could improve your answer by including the fact that you are using the unique prime factorisation theorem (aka fundamental theorem of arithmetic).
This is exactly what I thought of, seemed to simple but was correct
Let the set be split at some number n. So, the product of one subset is n! And the product of the other is (2026! / n!).
For these to be equal n! = 2026!/n! => n!.n! = 2026!
But n!.n! = (n2)!
Thus n would have to be equal to sqt (2026)
Since sqt (2026) is not an integer it cannot be a member of the original set. Do the statement is false.
It is false. Note that 1 9 9 7 is prime and 1 9 9 7 ∣ 2 0 2 6 ! , but 1 9 9 7 2 ∤ 2 0 2 6 ! . So, only one of the subsets would have a factor 1 9 9 7 , then the products cannot be equal.
2 0 2 7 < 46, dividing 2027 by the primes less than 46, reveals that p = 2027 is not divisible by any of them. So, by the Sieve of Eratosthenes, p is a prime. By Wilson's Theorem which says p is a prime if and only if (p - 1)! is congruent to -1 (mod p). So 2026! is congruent to -1(mod 2027). If 2026! = x 2 , then x 2 is congruent to -1(mod p). Then by Quadratic Residue Properties the Legendre symbol (-1/p) = 1. But we know from Number Theory (-1/p) = ( − 1 ) ( p − 1 ) / 2 . So letting p = 2027, then (-1/p) = ( − 1 ) 1 0 1 3 = -1, which is a contradiction, so (p - 1)! can not be a complete square.
Set p = 2 0 2 7 . If such a partition exists with their common product being A , then we have A 2 ≡ ( p − 1 ) ! ≡ − 1 m o d p , contradicting the fact that − 1 is a quadratic nonresidue since p ≡ 3 m o d 4 .
can you explain this residue thing in detail.
Log in to reply
See Quadratic residues .
A quadratic residue a is a value such that for some x , we have x 2 ≡ a m o d p . By the first supplement of Quadratic Reciprocity, − 1 is a quadratic residue modulo p if and only if p ≡ 1 m o d 4 . Our p ≡ 3 m o d 4 , so − 1 is not a quadratic residue (i.e. it's a quadratic nonresidue). Yet, if a common product A existed, we get A 2 ≡ − 1 m o d p , which is a contradiction.
Every number has a unique prime factorization. The products of the two partitions therefore must have a 1-1 correspondence between their prime factors.. There are primes between 1014 and 2026. These primes can appear as a factor only once, on their initial occurrence, since their smallest composite number containing such a prime, the multiple by 2, will be larger than 2026. Once one of these primes is assigned to a partition, there can be no corresponding prime in the other partition, thus that products of the two partitions cannot have the same prime factorization, and thus cannot be equal.
If all the numbers in the original set of 2016 were expressed as products of primes the idea is to have the same number of each prime represented in the prime product chain of each of the two sectioned sets. However, the prime 47 would appear 43 times and, 43 being an odd number, this means there cannot be a sectioning off to include the same number of 47s in each set.
Let's take the sun off the numbers up to 2026. One good mathematician have is that the sun off numbers up to n is (n+1)*n/2. For the sun up to 2026, this is 2053351. You might notice this is an odd number, which means it cannot be broken into two equal subsets. Therefore this doesn't work.
No, you read the question wrongly. The questions asked whether we can partition these integers into 2 sets such that the product (NOT SUM) of elements of each sets are equal.
Not sure if this is right so would appreciate input:
In the set [1,2,3,4,5...k...2026]
Is there somewhere a k such that k! =? 2026! / k! k! * k! =? 2026!
Well there is a prime number "2026" in 2026! which certainly won't be a factor of k! * k! .Both k are smaller than 2026 and that 2026 can only be made by multiplying it and 1. Therefore the two sides of the expression are unequal. Therefore our original statement that there is such a k that can split this set such that both subsets have the same product is false.
Is it generally possible to split sets ending with prime numbers into smaller sets with the same products? (I think this proof suggests otherwise)
Not sure, but would appreciate feedback!
2017 is a prime number. (Perhaps that was intended to be the hint.) Let A and B be the products of the two subsets. Then A or B is divisible by 2017, but not both.
Wonderful! Cleanest solution here.
If the sets had the same product, they could multiply to 2026!, and this value would need to be a square number. If there is one prime number greater than 2026/2, then there is a prime factor that appears an odd number of times. 2017 is prime, so 2026! is not a square number.
The highest prime less than 2026 has to go in one group or the other
2017 is not only the current year, but also a prime that makes the statement false. If it belongs to the set A, it will not divide the product of the set B as none of its element is divisible by 2017.
Call the product in the question P .
Then P 2 = 2 0 2 6 ! , but there are no factorials n ! with n > 1 that are perfect squares, a simple statement with more complex proof: see the problem on https://brilliant.org/wiki/distribution-of-primes/#bertrands-postulate.
Therefore there exists no P , and therefore the answer is False.
The answer is false.
Let's say you want to segregate the integers into two groups.
Both should contain the same number of 7.
But you have an only odd number of 7, which we can't put into two group.
Number of 7 - { 7 2 0 2 6 + 7 2 2 0 2 6 + 7 3 2 0 2 6 + 7 4 2 0 2 6 }=289+41+5=335
You can also check for 5. But it will be a little longer. And check for 11, you can make it short.
It is False.
Suppose to have 2 partition A and C of the set E, if the sum of A is equals to the sum of C then the sum of every element of the set E must be disabled by 2.
E = {1.. 2026}
So the sum of E is
SE = 2027*2026/2
Which is not divisible by 2 because 2027 is prime and 1013 is not divisible by 2.
The problem was asking about the product of the numbers in each set, not the sum.
The answer is False.
Let's call these 2 subsets A and B.
For any prime number x such that x > 1013: If x is in subset A, then we have no way to form subset B so that product of B is divisible by x, because no number in range [1, 2026] is divisible by x except x itself (recall x is prime and x > 1013).
So we have product of A is divisible by x when product of B is not.