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 ?

Solution 1:

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.

Solution 2:

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

Solution 3:

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!