# The set $\{1,2,3,\ldots,n\}$, where $n \geq 5$, can be divided into two subsets so that the sum of the first is equal to the product of the second

A peer of mine showed me earlier today this problem, taken from a 7th grade math contest :

Let $A=\{1,2,3,\ldots,n\}$; (where $n \geq 5$) prove that $A$ can be divided into two disjoint subsets such that the sum of the elements in the first subset is equal to the product of the elements in the second subset.

This has been puzzling me for 15 minutes already, but I'm sure there's a simple, straight-forward way to do it since it's a 7th grade problem, albeit I can't see it.

Can anyone shed some wisdom here ?

• $3=1+2$; $4\cdot2\cdot1=5+3$; $6\cdot3\cdot1=7+5+4+2$ – alex.jordan Feb 8 '15 at 1:24
• $n = 5$ works; you get $3+5=1\cdot2\cdot4$; $n=6$ gives $3+4+5=1\cdot2\cdot6$ – Dan Uznanski Feb 8 '15 at 1:26
• The problem actually does ask for a proof . Math is taken quite seriously in my country, those contests are more than tough – Victor Feb 8 '15 at 1:55

Going by the assumption that for an odd $n$ the product of $1, (n-1), (n-a)$ is equal to the sum of the rest of the numbers, we have $$1(n-1)(n-a) = \frac{n(n+1)}{2} - 1 -(n-1) - (n-a)$$

solving this gives $a=\frac{n+1}{2}$

Now for odd $n \ge 5$, we have
$$n-a = \frac{n-1}{2} \ge 2$$ Therefore the numbers $1, n-1, n-a$ are distinct.

A similar assumption for even $n$ with $1, n, (n-a)$ gives $$1*n(n-a) = \frac{n(n+1)}{2} - 1 -n - (n-a)$$ and the solution is $a=\frac{n+2}{2}$

And for even $n \ge 6$ we have $$n-a = \frac{n-2}{2} \ge 2$$ And therefore the numbers $1, n, n-a$ are distinct.

• We need to know why? (1) How many items to move? (2) Which to move. I disagree to assume there must be 3 items, and 1 and (n-1) must be within the choices. Plus we do not know if there are multiple solutions. Need to proof. – PdotWang Feb 8 '15 at 2:49
• @PdotWang: we were just asked to show that there is one solution, not to show how many there are. benji has exhibited a solution. (ed df) – Ross Millikan Feb 8 '15 at 3:28
• @Asker Basically, he just means "Let's try something simple." My answer was the same - I first tried looking for a pair, and then a triple. Since $ab+a+b+1=(a+1)(b+1)$, I realized the easiest triple might be of the form $\{a,b,1\}$. – Thomas Andrews Feb 9 '15 at 7:10
• You are misreading what the answer is. The product of the elements of $\{1,a,b\}$ is $ab$. The sum of the other ones is $n(n+1)/2 - (1+a+b)$. So you need $(a+1)(b+1)=ab+(1+a+b)=n(n+1)/2$. But we have obvious factorization of $n(n+1)/2$ depending on whether $n$ is even or odd. – Thomas Andrews Feb 9 '15 at 8:33
• @Asker I meant I just tried to solve for $n=5,6,7,8$. So for example for $n=5, 1 \cdot 2 \cdot 4 = 3+5$. I noticed that for $n=5,7$ the product is made with $1,n-1$ and another number and for $n=6,8$ the product is $1,n$ and some other number. The rest is in the answer.. – benji Feb 10 '15 at 0:26

You can always do it with the product being three elements, one of them $1$.

$$1+2+3+4+\cdots +n = n(n+1)/2$$

Find $a,b$ so that $n(n+1)/2-(1+a+b) = ab$. This is easy to do since $1+a+b+ab=(1+a)(1+b)$.

So, when $n$ odd, choose $a=n-1,b=\frac{n-1}{2}$. E.g., for $n=7$, that gives $1\cdot 3\cdot 6=2+4+5+7$.

For $n$ even, $a=n,b=\frac{n-2}{2}$. For example, $n=6$ yields $a=6,b=2$ and $1\cdot 2\cdot 6=3+4+5$.

When $n<5$, $\{a,b,1\}$ are not distinct.

It's harder to do it in two elements in the product. Then you'd need $ab=n(n+1)/2-(a+b)$ or $(1+a)(1+b)=\frac{n^2+n+2}{2}$. So you'd need to factor $\frac{n^2+n+2}{2}$ into two distinct numbers $\leq n+1$.

You can do this for $n=17$, for example, then $\frac{n^2+n+2}{2}=154=11\cdot 14$. so $a=10,b=13$. Then $$10\cdot 13 =1+2+3+4+5+6+7+8+9+11+12+14+15+16+17$$

The question came up about products of $4$ numbers. Let's still try to seek simple answers, so a product of the form $1\cdot 2\cdot a\cdot b = \frac{n(n+1)}{2}-(a+b+1+2)$, or:

$$2ab +a+b+3=\frac{n(n+1)}{2}$$ Multiply both sides by $2$ and you get:

$$(2a+1)(2b+1)+5 = n(n+1)$$

So we need to factor $n(n+1)-5$ into two distinct odd numbers $\leq 2n+1$. For example, $n=10$ then $n(n+1)-5=105=15\cdot 7$. So $a=3,b=7$. Then:

$$1\cdot2\cdot3\cdot 7 = 4+5+6+8+9+10$$

An example with the product containing $5$ elements, $n=20$ then:

$$1\cdot 2\cdot 3\cdot 4\cdot 8 = 5+6+7+9+10+\cdots + 20$$

An example with a product of $4$ numbers, none equal to $1$ (with $n=26$):

$$2\cdot 3\cdot 5\cdot 11 = 1+4+6+7+8+9+10+12+\cdots +26$$

Another with $4$ in the product:

$$3\cdot 5\cdot 7\cdot 16 = \frac{58\cdot 59}{2} - (3+5+7+16)$$

We can get arbitrarily long product solutions. You can show that for $n=k!-k$, let $A=\frac{k!}{2}-k$, then:

$$1\cdot 2\cdot3\cdots k\cdot A = \frac{(k!-k)(k!-k+1)}{2}-(1+2+\cdots + k + A)$$

For example:

\begin{align}4!\cdot 8 &= \frac{20\cdot21}{2}-(1+2+3+4+8)\\ 5!\cdot 55 &= \frac{115\cdot116}{2}-(1+2+3+4+5+55)\\ 6!\cdot 354 &= \frac{714\cdot715}{2}-(1+2+3+4+5+6+354)\\ 7!\cdot 2513 &= \frac{5033\cdot 5034}{2}-(1+2+3+4+5+6+7+2513) \end{align}

More generally, if $\{x_i\}_{i=1,\cdot,m}$ are distinct positive integers with at least one even, let $S=\sum x_i$ and $P=\prod x_i$. Then if $S=\frac{k(k+1)}2$ for some $k$, then let $A=\frac{P}{2}-k$ and $n=P-k$. Then:

$$A\cdot \prod x_i = \frac{n(n+1)}{2} - (x_1+\cdots + x_m + A)$$

For small collections of small values $x_i$ this doesn't always give a good $A$, but in most cases, it does.

For example $5+10=\frac{5(5+1)}2$. So $n=45$ and $A=20$, and you get $$5\cdot 10\cdot 20 = \frac{45\cdot 46}{2}-(5 + 10+20)$$

This means that we can always extend any $x_1,\cdots,x_m$ with a larger $x_{m+1}$ so that $\sum_{i=1}^{m+1} x_i$ is a triangular number, and then find the $A$ above. Indeed, we can write an explicit formula. If $S=\sum_{i=1}^m x_i$ and $P=\prod_{i=1}^m x_i$ then you can define \begin{align}x_{m+1}&=2S(S-1)\\x_{m+2}&=PS(S-1)-2S+1\\n&=2PS(S-1)-2S+1.\end{align}

This can't be done for $n=4$.

One element of the product side won't do. Two elements on the product side won't do. ($1*2=2\neq 7, 1*3=3\neq 8, 1*4\neq6, 2*3=6\neq 4, 2*4, nope$) Surely it doesn't work for three elements on the product side.

It doesn't work. For $n\geq 5$, certainly seems to be true. What I've found so far:

1*2*4 = 3+5
1*2*6 = 3+4+5
1*3*6 = 2+4+5+7
1*3*8 = 2+4+5+6+7
1*4*8 = 2+3+5+6+7+9
6*7 = 1+2+3+4+5+8+9+10
1*5*10 = 2+3+4+6+7+8+9+11
1*5*12 = 2+3+4+6+7+8+9+10+11
1*6*12 = 2+3+4+5+7+8+9+10+11+13
1*6*14 = 2+3+4+5+7+8+9+10+11+12+13
1*7*14 = 2+3+4+5+6+8+9+10+11+12+13+15
1*7*16 = 2+3+4+5+6+8+9+10+11+12+13+14+15
10*13 = 1+2+3+4+5+6+7+8+9+11+12+14+15+16+17
1*8*18 = 2+3+4+5+6+7+9+10+11+12+13+14+15+16+17
1*9*18 = 2+3+4+5+6+7+8+10+11+12+13+14+15+16+17+19
1*9*20 = 2+3+4+5+6+7+8+10+11+12+13+14+15+16+17+18+19
1*10*20 = 2+3+4+5+6+7+8+9+11+12+13+14+15+16+17+18+19+21
1*10*22 = 2+3+4+5+6+7+8+9+11+12+13+14+15+16+17+18+19+20+21
1*11*22 = 2+3+4+5+6+7+8+9+10+12+13+14+15+16+17+18+19+20+21+23
1*11*24 = 2+3+4+5+6+7+8+9+10+12+13+14+15+16+17+18+19+20+21+22+23
1*12*24 = 2+3+4+5+6+7+8+9+10+11+13+14+15+16+17+18+19+20+21+22+23+25
15*21 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+16+17+18+19+20+22+23+24+25+26
1*13*26 = 2+3+4+5+6+7+8+9+10+11+12+14+15+16+17+18+19+20+21+22+23+24+25+27
1*13*28 = 2+3+4+5+6+7+8+9+10+11+12+14+15+16+17+18+19+20+21+22+23+24+25+26+27
1*14*28 = 2+3+4+5+6+7+8+9+10+11+12+13+15+16+17+18+19+20+21+22+23+24+25+26+27+29
1*14*30 = 2+3+4+5+6+7+8+9+10+11+12+13+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29
1*15*30 = 2+3+4+5+6+7+8+9+10+11+12+13+14+16+17+18+19+20+21+22+23+24+25+26+27+28+29+31
1*15*32 = 2+3+4+5+6+7+8+9+10+11+12+13+14+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31
1*16*32 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+33
1*16*34 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33
1*17*34 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+35
22*28 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+23+24+25+26+27+29+30+31+32+33+34+35+36
21*31 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+22+23+24+25+26+27+28+29+30+32+33+34+35+36+37
1*18*38 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37
1*19*38 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+39
1*19*40 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39
1*20*40 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+41
1*20*42 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41
1*21*42 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+43
1*21*44 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43
27*36 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+28+29+30+31+32+33+34+35+37+38+39+40+41+42+43+44+45
1*22*46 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45
1*23*46 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+47
1*23*48 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47


For $n=39$, I found these $7$ partitions:

1*19*38 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+39
1*25*29 = 2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+26+27+28+30+31+32+33+34+35+36+37+38+39
3*7*35 = 1+2+4+5+6+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+36+37+38+39
4*11*17 = 1+2+3+5+6+7+8+9+10+12+13+14+15+16+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39
5*10*15 = 1+2+3+4+6+7+8+9+11+12+13+14+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39
2*6*7*9 = 1+3+4+5+8+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39
1*3*4*7*9 = 2+5+6+8+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39


Amazingly good question!

• $n\geq 5$, now that's a whole new question. – ploosu2 Feb 8 '15 at 1:42
• I believe you have made a program. Can you test that there is only one solution for each case? – PdotWang Feb 8 '15 at 3:08
• There isn't only one solution in each case. There is always a solution of the form $\{1,a,b\}$ for the product, but there might be a solution with two elements in the product. @PdotWang – Thomas Andrews Feb 8 '15 at 3:10
• For example, when $n=17,$ $$1\cdot 8\cdot 16 = 2+3+4+5+6+7+9+10+11+12+13+14+15+17$$ which is different from the answer above. @PdotWang – Thomas Andrews Feb 8 '15 at 3:15
• Question 1, would {a,b,c,d} be possible? Question 2, would {1,a,b} and {1,c,d} be possible"? – PdotWang Feb 8 '15 at 3:16

The sum of all the numbers is $$\sum_{k=1}^nk=\frac{n(n+1)}2\tag{1}$$ We will find $a$ and $b$ so that $$\overbrace{\left(\sum_{k=1}^nk\right)-a-b-1}^{\text{sum of all but a, b, and 1}}=\overbrace{\vphantom{\left(\sum_1^n\right)}1ab}^{\text{product}}\tag{2}$$ That is, we need to find $a$ and $b$ so that \begin{align} \frac{n(n+1)}2 &=\overbrace{ab}^{\text{product}}+\overbrace{a+b+1}^{\text{sum}}\\ &=(a+1)(b+1)\tag{3} \end{align} and $(3)$ can be solved using $$(a,b)=\left\{\begin{array}{} \left(\frac{n-1}2,n-1\right)&\text{if n is odd}\\ \left(n,\frac{n-2}2\right)&\text{if n is even}\\ \end{array}\right.\tag{4}$$ Thus, the product of $1$, $a$, and $b$ is the sum of the rest of the numbers from $1$ to $n$.

If $n\ge5$, then $a,b\ge2$ so that they don't interfere with $1$.

Examples

With $n=5$, $a=\frac{5-1}2=2$ and $b=5-1=4$ so $1\cdot2\cdot4=3+5$

With $n=6$, $a=6$ and $b=\frac{6-2}2=2$ so $1\cdot2\cdot6=3+4+5$

With $n=7$, $a=\frac{7-1}2=3$ and $b=7-1=6$ so $1\cdot3\cdot6=2+4+5+7$

With $n=8$, $a=8$ and $b=\frac{8-2}2=3$ so $1\cdot3\cdot8=2+4+5+6+7$

For any odd $n$ and $n\geq5$ we can always find the item before the last one, and the item before the center item, and the first item. Then move those 3 items to the product set.

For example: $n=5$, move $1,2,4$. If: $n=7$, move $1,3,6$.

For any even $n$ and $n\geq6$ we can always find the last item, and the item just before the 2 center items, and the first item. Then move those 3 items to the product set. That is the solution.

For example: $n=6$, move $1,2,6$. If: $n=8$, move $1,3,8$.

for $n=3$, move 3. It seems that this is a special case.

To proof, we have the following relationships:

For: $n=odd$

Left: $${1\over2}n(n+1)-(n-1)-{(n-1)\over2}-1={1\over2}(n-1)^2$$ Right: $$(n-1){(n-1)\over2}={1\over2}(n-1)^2$$

For: $n=even$

Left: $${1\over2}n(n+1)-n-({n\over2}-1)-1={1\over2}n(n-2)$$ Right: $$n({n\over2}-1)={1\over2}n(n-2)$$

Note: If we want to just give an answer to the question, then the above is OK. But in general, we need to know (1) How many items to move? (2) Which ones to move. We cannot assume there must be 3 items, and 1 and (n-1) must be within the choices. Further we do not know if it is the only solution. We may need to proof.

• for n=3, move 3. That is special, I think. – PdotWang Feb 8 '15 at 1:57
• for n=7, move 1,3,6. – PdotWang Feb 8 '15 at 2:00
• It is easy to prove. Left is the sum which is (n+1)n/2-(n-1)-(n-1)/2-1. Right is (n-1)(n-1)/2 – PdotWang Feb 8 '15 at 2:03