Partitioning the integers $1$ through $n$ so that the product of the elements in one set is equal to the sum of the elements in the other

Question

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$.

Answer 1

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.

Answer 2

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.

Answer 3

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