18
$\begingroup$

I asked this question at math.SE a couple of months ago and only got a partial answer, so I thought I would try here.


It is known that, for $n \geq 5$, it is possible to partition the integers $\{1, 2, \ldots, n\}$ into two disjoint subsets such that the product of the elements in one set equals the sum of the elements in the other. One solution is the following:

Let $N = \{1, 2, \ldots, n\}$.

If $n$ is even, take $P = \{1, \frac{n-2}{2}, n\}$ and $N-P$ as the two sets.

If $n$ is odd, take $P = \{1, \frac{n-1}{2}, n-1\}$ and $N-P$ as the two sets.

My question is this:

Is this partition unique for infinitely many $n$?

Background: The problem of proving that the partition is possible was posed several years ago as Problem 2826 in the journal Crux Mathematicorum, with solutions in the April 2004 issue. Every one of the 20 or so solvers (including me, which is why I'm interested in the question) came up with the partition given here. The person who originally posed the problem also asked if the partition is unique for infinitely many $n$. I don't think anyone ever submitted an answer to that latter question to Crux (although I cannot verify that, as I no longer have a subscription). I thought someone here might be able to give an answer.


The partial answers to the math.SE question were

1) Matthew Conroy showed by brute force calculation that, for $5 \leq n \leq 100$, the only values of $n$ that have only this solution are $5,6,7,8,9,13,18,$ and $34$.

2) Derek Jennings showed that for $n=4m$ we can obtain a partition with the required property by taking $P=\{8,m−1,m+1\}$ for $m>1$ and $m \neq 7$ or $9$. Thus the partition in the question is not unique for $n$ a multiple of $4$ and greater than $36$.

$\endgroup$
5
  • 1
    $\begingroup$ Considering P to be a two element set leads to 2(a+1)(b+1) = n^2 +n + 2, which may be solvable with a,b < n, for infinitely many n, although the density of such n may be 0. Gerhard "Ask Me About System Design" Paseman, 2011.02.13 $\endgroup$ Feb 14, 2011 at 7:32
  • 1
    $\begingroup$ @Gerhard, the special case $b=a+1$ leads to a Pell-type equation ($x^2-2y^2=-9$, to be precise), which certainly has infinitely many solutions (although, as you say, density zero). $\endgroup$ Feb 14, 2011 at 11:42
  • 1
    $\begingroup$ That suggests looking at b = a + c where c is not too big (say c < 0.9*a). Do all of those lead to Pell equations, and can something be said about the density of the union of all the solutions, ranging over different values of c? Gerhard "Inquiring Minds Want To Know" Paseman, 2011.02.14 $\endgroup$ Feb 14, 2011 at 17:09
  • 1
    $\begingroup$ The solutions proposed all have a small number of factors in the product, and this is inevitable. But is there anything that can be said about the asymptotics of the largest subset we can pick out to form the product, or is the best we can do to take a constant (3, 4, m say) and say there are infinitely many solutions where the multiplicative part is that size? $\endgroup$ Feb 15, 2011 at 20:27
  • $\begingroup$ @Mark, the product of $m$ distinct positive integers is at least $m!$, so we get $m!\lt n(n+1)/2$. My guess is that for any fixed number of terms in the product there will be infinitely many $n$ with a solution. $\endgroup$ Feb 15, 2011 at 22:05

3 Answers 3

9
$\begingroup$

First (failed) attempt:

For $n \equiv 0 \mod{3}$ or $n\equiv 2 \mod{3}$, there is a second solution: $P=\{ 1, 2, \frac{n(n+1)}{6}-1 \} $.

Edit: As the comments point out, the last term is too large.

Second attempt:

When $n=12m+3$, a second solution is $P=\{ 1, 8m+1, 9m+2 \}$.

When $n=30m+24$, a second solution is $P=\{ 1, 18m+14, 25m+19\}$.

We can generate an infinite family of such solutions as follows. We look for solutions of the form $P=\{1, a, b\}$, which leads to the equation $$ \frac{n(n+1)}{2}= 1ab+a+b+1=(a+1)(b+1) .$$ One solution of this is the original solution given in the question. We can get other solutions by exchanging divisors of (a+1) and (b+1) while keeping both factors $\le n+1$. For example, assuming $n$ is odd and $3|n$ and $2|\frac{n+1}{2}$, we exchange the divisors $2$ and $3$ to get the new solution $a+1=2n/3$ and $b+1=3(n+1)/4$. This leads to the solution for $n=12m+3$ given above. Assuming $n$ is even, and exchanging the factors $3$ and $5$ leads to the other solution given above.

This way we can generate an infinite number of linear congruences for $n$ with corresponding solutions $P$. The question is what proportion of integers is covered by all these congruences. When $n$ and $\frac{n+1}{2}$ are both prime, which is probably true for infinitely many $n$, this method does not generate a second solution.

$\endgroup$
4
  • $\begingroup$ But for most $n$, $n(n+1)/6-1 > n$, so it won't work. $\endgroup$
    – Peter Shor
    Feb 14, 2011 at 17:15
  • 1
    $\begingroup$ Sorry, too big for n > 12. Try again. Gerhard "Have a Happy Valentines Day" Paseman, 2011.02.14 $\endgroup$ Feb 14, 2011 at 17:16
  • $\begingroup$ Nice answer. I'll just comment that it is indeed conjectured that there are infinitely many $n$ such that both $n$ and $\frac{n+1}{2}$ are prime. Google Cunningham chains (of the second kind). $\endgroup$
    – Tony Huynh
    Feb 16, 2011 at 1:27
  • 2
    $\begingroup$ Riffing on the same idea, for $30n + 5$, take the triple $\{1, 18n + 2, 25n + 4\}$. $\endgroup$
    – JBL
    Feb 16, 2011 at 17:58
3
$\begingroup$

I get the impression that sporadic solutions are not too hard to come by. Here is another one in which $n$ happens to be congruent $2 \pmod{4}.$

When $n=2(16m^4-2m^2-1)^2$ we can take

$$P= \lbrace 2,16m^4-2m^2-2m-1,16m^4-2m^2+2m-1,(16m^4-2m^2-1)^2+4m^2 \rbrace .$$

And so, with $m=1,N=\lbrace 1,2,\ldots,338 \rbrace $ and we can take

$$P = \lbrace 2,11,15,173 \rbrace $$

and with $m=2,N=\lbrace 1,2,\ldots,122018 \rbrace $ and we can take

$$P = \lbrace 2,243,251,61025 \rbrace .$$

The problem is, of course, that we have zero density.

$\endgroup$
0
$\begingroup$

I have a feeling that the answer is yes, that the representation is unique for infinitely many $n$, despite the computational evidence. Perhaps others will be similarly compelled by the observations below.

Fixing $n$, the idea is to find a subset $P$ of ${1,...,n}$ so that $\prod_{i \in P} i + \sum_{i \in P} i = n(n+1)/2 = T$. It is clear that $P$ has at least two elements which are not 1 and at most $O(\log(n))$ elements. It takes a little work to show that $\sum_{i \in P} i \lt 3n/2 + O(1)$. Rewriting $\prod_{i \in P} i = p$, and being a little sloppy, $p$ must then be in or near $[n(n-2)/2 , T - \epsilon_1]$ where $\epsilon_1$ is $O(\log(n)^2)$. So a computer search might do well to find all numbers in this interval with factors no larger than $n$. Further, if $p > T - d$, then $p$ must factorize into a product of numbers each smaller than $d$

One can go a little further and show that, if the largest factor has size $n^\alpha$, then the sum has size smaller than $(2/\alpha)n^\alpha$, so if $p$ is far enough away from $T$ then the largest element of $P$ can't be too small.

Other arguments show that if $(n-k) \in P $ for $k$ somewhat smaller than $n/2$, then there are at most one or two choices for $p$; this might be turned into a proof that $k$ cannot be in $[2,.., n/2 - \epsilon_2]$.

UPDATE 2011.02.23

Let's consider how often a partition contains (for fixed $k$) the value $n-k$ in the product. Since $k=0$ and $k=1$ are realized infinitely often, let's try $k \gt 1$.

$(n-k)*p + (n-k) + s = n(n+1)/2$, where $p$ and $s$ are the product, respectively sum, of the members of the set $P - \{n-k\}$, that is all members in the set for product which are not equal to $n-k$ . Now $s$ can range from some number greater than $\log_2(p)$ up to $p+1$, as $s$ is the sum of distinct positive integers whose product is the integer $p$. Further, $n(n+1)/2 \le (n- k+1) (p+1)$, so $p \ge (n+k-2)/2$. So when $k$ is small ($k \lt \sqrt(n+1)-1$) there aren't too many choices for $p$:

$(n+k-2)/2 \le p \lt (n+k-1)/2 + (k^2 +k)/2(n-k)$ .

So when $(k^2 + 2k) \lt n$, if $n+k$ is even, then $p$ could be $(n+k-2)/2$, otherwise $n+k$ is odd and then $p$ could be $(n+k-1)/2$.

Now we can solve for $s$: if $n+k$ is odd, $s = ( k^2 +k )/2$, otherwise $s = (k^2 + 2k -n)/2 \lt 0$ because $k$ is small. So when $k$ is small, $s$ is one of only finitely many possibilities, which means $p$ and therefore $n$ is one of only finitely many possibilities. Thus, when $k$ is fixed and not $0$ or $1$, $n-k$ can occur in a partition for only finitely many $n$. However, one can fix $k$, determine $s$, find an additive partition of $s$, multiply that partition to find $p$ and then find $n$, so there are many more $n$ for which there is more than one partition.

I still suspect that there are infinitely many $n$ for which there is not more than one partition. I also think that one can extend the above analysis for $k$ up to $n/4$ to find out exactly when $n-k$ is in a partition, but I'll let someone else run with that for now.

END UPDATE 2011.02.23

Once one finds a candidate $p$ that meets the conditions above, one still has to find a factorization of $p$ such that $p$ plus the sum of these factors adds up to $T$. I think there are enough primes and other obstacles to support the answer yes. Further, I suspect the number of such representations is bounded or if not bounded, grows slower than $\log(\log(n))$.

Gerhard "Ask Me About System Design" Paseman, 2011.02.16

$\endgroup$
2
  • $\begingroup$ I had forgotten Andreas Weingartner's construction in writing the above. Still, there is hope for the notion that for most n, k cannot be in the interval [2,..., n/2 - some fudge factor]. Gerhard "Ask Me About System Design" Paseman, 2011.02.16 $\endgroup$ Feb 16, 2011 at 9:19
  • $\begingroup$ Using the updated results, one has partitions like {1,2,...,k-1,k, (2(k!) - 2k +1)} for the product, with n = 2(k!) - k + 1 , for k > 2. Gerhard "Ask Me About System Design" Paseman, 2011.02.23 $\endgroup$ Feb 23, 2011 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.