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


  • 5
    +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.$2010-12-14
  • 0
    @Derek Jennings: Thanks for the examples! Do you have a formula that will produce these $P$ sets for certain values of $n$?2010-12-14
  • 7
    @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 .$2010-12-14
  • 1
    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.2010-12-14
  • 2
    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$).2010-12-14
  • 2
    No additional unique partitions up to $n\le61$.2010-12-15
  • 1
    No addition unique partitions to $n\le 81$ (this is keeping my cpu warm).2010-12-16
  • 1
    No additional unique partitions to $n\le 100$.2010-12-17
  • 0
    The number 38 in your post is not divisible by 4. Typo?2011-10-12
  • 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
    That is an interesting observation!2011-10-06
  • 0
    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.2011-10-06
  • 0
    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.2011-10-06
  • 3
    I think you mean $n(n+1)/2$...2011-10-07
  • 0
    Yup, or you can say that it is a partition of $\{ 1, 2, 3, ... ,n-1 \}$, lol.. Will fix it :)2011-10-12
  • 0
    This was the best partial answer that goes beyond the results of Derek Jennings and Matthew Conroy, so the bounty goes to user9176! Thanks!2011-10-13
  • 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.$)

  • 3
    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.2010-12-15
  • 0
    @Matthew: Well spotted! And we must include $n=36$ also, where $m-1=8.$ These are the only exceptions though.2010-12-15
  • 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
    Nice idea, Angela. I get $bc+ad+a+c=\frac{1}{2}$, though, in your first paragraph. Am I missing something?2011-10-12
  • 0
    I made a mistake. I have now edited it.2011-10-13
  • 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