Dave Richeson tweeted about a puzzle from Futility Closet (original source a Russian mathematical olympiad): can you split the integers 1, 2, …, 15 into two groups A and B, with 13 elements in A and 2 elements in B, so that the sum of the elements of A is the product of the elements of B?

Think about it for a moment. There’s of course the temptation to brute-force it, which is doable, but there’s a more elegant solution.

This got me thinking – when can you split the integers 1, 2, …, n into two groups A and B, where B has two elements, so that the sum of the elements of A is the product of the elements of B?

Say B contains x and y. Then their product is of course xy. The sum of the elements of A is . Setting these equal and rearranging gives

where we’ve added 1 to make the factorization work out – this becomes

.

So the problem is reduced to finding factorizations of n(n+1)/2 + 1, which satisfy two conditions:

- x and y can’t be equal (for specificity we’ll say x < y), and
- x and y are both at most n.

Since we have y ≤ n, we’re going to have x ≥ (n+1)/2 + 1/n. *n* must be at least 2, so we can just write x ≥ (n/2) + 1. So we’re looking for factors of n(n+1)/2 + 1 in the interval [n/2+1, n]. Here’s some brute-force Python code to find all such solutions:

import math def solutions(n): out = [] total = n*(n+1)/2+1 xmin = int(math.ceil(n/2.0) + 1) xmax = n for x in range(xmin, xmax+1): if total % (x+1) == 0: y = total/(x+1)-1 if x < y: out.append([x,y]) return out def all_solutions(n): out = [] for i in range(2, n+1): sols = solutions(i) for sol in sols: sol.insert(0, i) out.append(sol) return out

`solutions` takes an integer `n` as input and returns pairs `[x, y]` which are solutions to the problem. For example `solutions(17)` returns `[[10, 13]]`.

And `all_solutions` takes an integer `N` and returns all triples `[n, x, y]` with which are solutions to the problem — that is, where *xy* equals the sum of all the integers up to *n* except for *x* and *y*. The first few solutions are:

n | x | y |

10 | 6 | 7 |

17 | 10 | 13 |

26 | 15 | 21 |

36 | 22 | 28 |

37 | 21 | 31 |

45 | 27 | 36 |

50 | 28 | 43 |

61 | 42 | 43 |

65 | 36 | 57 |

67 | 42 | 52 |

78 | 45 | 66 |

82 | 45 | 73 |

91 | 52 | 78 |

94 | 57 | 76 |

101 | 55 | 91 |

102 | 70 | 73 |

110 | 70 | 85 |

122 | 66 | 111 |

136 | 76 | 120 |

138 | 87 | 108 |

So it appears that there’s nothing particularly special about the number 15 in the initial puzzle. There are plenty of values *n* for which you can’t do this, and plenty for which you can. Also, there are values of *n* for which there are multiple solution pairs (*x*, *y*), although not surprisingly they are rare. The smallest such *n* is 325, for which and are both solutions. In this case $latex n(n+1)/2 + 1 = 52976 = 2^{4} \times 7 \times 11 \times 43$, from which 52976 has (5)(2)(2)(2) = 40 factors. A typical number of this size has about factors. This abundance of factors makes it more likely that 52976 would have two factorizations of the sort we’re looking for. And in fact .

Solutions to this problem appear to have some interesting statistical properties… more on that in a future post.

Elegant. You’re reducing the search to factorize 121, which is trivial. Before reading your answer I tried it using constraints: x<y, and it's easy to see that 8<=x<=10, and 11<=y<=15. So, the search is reduced to 15 pairs, I made an exhaustive search using a spreadsheet and I thought something was wrong when nothing came up. 😉

Reblogged this on lava kafle kathmandu nepal <a href="https://plus.google.com/102726194262702292606" rel="publisher">Google+</a>.

[…] another brute-force number theory puzzle, in the spirit of the Russian puzzle I looked at a couple weeks ago. From what would Martin Gardner tweet: “Two triangles share one angle but have six different […]

A very insightful investigation of a fun puzzle. I’m a math undergraduate and have been simply browsing. You’re solution was very easy to follow, but I had a little trouble understanding your boundaries for x. I really like how this puzzle led you to find other values for n. Very interesting read!