42
$\begingroup$

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.


  • 0
    @GottfriedHelms: Yep, typo. (Derek and Matthew have 36.) I'll fix it. Thanks!2011-10-12

4 Answers 4

10

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.

  • 0
    I'm stating the obvious here but $n(n+1)/2=\sum_{m\leq n}m$2017-02-18
7

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

  • 0
    Oops, I don't know how I missed 36 (doable with $\{1,17,36\}$ and $\{22,28\}$).2010-12-16
2

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
    @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.2011-10-12
2

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$

  • 0
    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\}$.2011-10-13