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