# 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

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

One might be able to prove an even stronger result, as I don't know of any other solutions.

Update on progress: Derek Jennings has found another family of solutions for the case where $n$ is a multiple of 4, except for $n=8$, $28$, or $36$; see his answer below. And Matthew Conroy has verified that, for $n \leq 100$, the partition given above is unique only for $n = 5,6,7,8,9,13,18,$ and $34$.

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.

-
+1: Nice question. $P$ is clearly not unique for many (actually an infinity of) $n.$ In the case $n=10$ we could take $P=\lbrace 6,7 \rbrace,$ for $n=61$ take $P=\lbrace 42,43 \rbrace$ and for $n=358$ take $P=\lbrace 252,253 \rbrace.$ – Derek Jennings Dec 14 '10 at 19:27
@Mike: I just set $m(m+1)/2 - a - b = ab$ and put $b=a+1$ which gives solutions when $\sqrt{2m^2+2m+5}$ is a square (when $9=2x^2 - y^2$ for $y=2m+1$). The next solution occurs when $m=-2090,$ which gives $n=2089$ and $P=\lbrace 1476,1477 \rbrace .$ – Derek Jennings Dec 14 '10 at 21:58
For any fixed size of the product subset (and one can stipulate that it is at least, say, 4 or 6 to give some freedom) there should be nonuniqueness for large enough $n$, with a number of solutions like O((log n)^k) for some k > 0. So I would certainly not expect to have infinitely many n for which uniqueness holds. – T.. Dec 14 '10 at 22:19
A brute force calculation I did indicates unique partitions only for $n= 5, 6, 7, 8, 9, 13, 18,$ and 34 ( for $n \le 42$). – Matthew Conroy Dec 14 '10 at 22:21
No additional unique partitions up to $n\le61$. – Matthew Conroy Dec 15 '10 at 7:54

Here is an interesting observation:

If $\frac{n(n+1)}{2}+1$ is not a prime, nor a square of a prime, then the partition is not unique.

Proof

Look at the partition $P=\{a,b \}$ and $N-P$.

This works if and only if

$$ab=\frac{n(n+1)}{2}-a-b \,,$$

if and only if

$$ab+a+b+1=\frac{n(n+1)}{2}+1 \,.$$

if and only if

$$(a+1)(b+1)=\frac{n(n+1)}{2}+1 \,.$$

As long as the right side can be written as the product of two distinct proper divisors, we can find $a,b$.

Edit I pointed below I made an(other) elementary mistake, the actual claim should be if $\ \dfrac{n(n+1)}{2}+1$ is the product of two distinct proper divisors not exceeding $n$, then the solution is not unique.

Sorry, this is weaker than I thought.

-
That is an interesting observation! – Mike Spivey Oct 6 '11 at 21:32
It is necessary that the factorization have max(a,b) < n+1. Not every proper factorization has this property. But the same method could be used for triples (a,b,c) and might take care of all large enough n. – zyx Oct 6 '11 at 21:42
The problem that @zyx points out occurs, for example, with $n = 34$. You have $562$ on the right-hand side, which factors into $2$ and $281$, the latter of which is prime. – Mike Spivey Oct 6 '11 at 21:51
I think you mean $n(n+1)/2$... – Craig Oct 7 '11 at 23:12
Yup, or you can say that it is a partition of $\{ 1, 2, 3, ... ,n-1 \}$, lol.. Will fix it :) – N. S. Oct 12 '11 at 16:23

This does not answer the question but it is progress towards.

For $n=4m$ we can obtain a partition with the required property by taking $P=\lbrace 8,m-1,m+1 \rbrace$ for $m>1 \textrm{ and } m \ne 7 \textrm{ or } 9.$

This partition is distinct from the one given in the question for all $m>2$ and hence the partition in the question is not unique for $n$ a multiple of $4$ and greater than $8.$ (Other solutions exist for $n=28$ and $n=36.$)

-
This does not work for $n=28$, though, where $m+1$ would equal 8. For $n=28$, $P=\{1,13,28\}$ and $P=\{3,7,18\}$ are the only workable partitions. – Matthew Conroy Dec 15 '10 at 20:53
@Matthew: Well spotted! And we must include $n=36$ also, where $m-1=8.$ These are the only exceptions though. – Derek Jennings Dec 15 '10 at 21:53
Oops, I don't know how I missed 36 (doable with $\{1,17,36\}$ and $\{22,28\}$). – Matthew Conroy Dec 16 '10 at 4:44

I just wanted to comment that you can rephrase the question as

Find all $S\subset \{1,2,\dots , n\}$ such that $$\sum_{i\in S} i+\prod_{i\in S} i=\frac{n(n+1)}{2}.$$

Alternatively

Given $n$, how many different boxes with dimension less then $n$, and distinct integer sides exist such that the sum of the side lengths plus the volume is the $n^{th}$ triangle number?

It is very interesting to note, that in this form it looks at least similar to this famous problem.

-
+1 for the reformulation. – Mike Spivey Oct 10 '11 at 20:47
@MikeSpivey: I don't think this is useful, but I added a link to where there is a similar problem in Number theory with the sum and product formulation. Unfortunately everything there is reciprocals, but it is worth at least glancing at. – Eric Naslund Oct 12 '11 at 16:07

There are no families of 2 elements of the form $\{an+b,cn+d\}$. Otherwise we would have $(an+b)(cn+d)+an+b+cn+d=\frac{n^{2}+n}{2}$ hence $bd+b+d=0$, $d(b+1)=-b$, $d=\frac{-b}{b+1}$, $ac=\frac{1}{2}$ and $bc+ad+a+b=\frac{1}{2}$, and substitutions will give a quadratic in b for which no solutions will give an infinite solution set.

Supposing a family of solutions of 3 elements were given by $\{an+b,cn+d,fn+e\}$ where $a,b,c,d,e,f$ are rational, and would apply for all $n$ such that $an+b,cn+d,fn+e$ are distinct integers $>0$ and $\leq{n}$.
Their product + their sum is to be $\frac{n^2+n}{2}$ therefore the parametric equations of the solution families would be:

$acf=0$ (generalising, families of $n$ elements would have 2 elements with a non-zero $n$ coefficient, and the rest of the elements would be constant - so we can assume $f = 0$)

$ebd+e+b+d=0$

$eac=\frac{1}{2}$

$ebc+eda+a+c=\frac{1}{2}$

With 4 elements any family of solutions $\{an+b,cn+d,e,f\}$ would require:

$ac(f+g)=\frac{1}{2}$

$a+c+adgf+gcbf=\frac{1}{2}$

$bdfg+b+d+f+g=0$

-
Nice idea, Angela. I get $bc+ad+a+c=\frac{1}{2}$, though, in your first paragraph. Am I missing something? – Mike Spivey Oct 12 '11 at 16:04
I made a mistake. I have now edited it. – Angela Richardson Oct 13 '11 at 8:51
I added some formatting and fixed one mistake I saw. What is $g$ in the 4-element case, though? And +1, especially for showing that we can rule out sets of the form $\{an+b, cn+d\}$. – Mike Spivey Oct 13 '11 at 15:39