Partitioning

So, I have a few new puzzles in the bank now, so I need to get to blogging again to spend them. I guess I need to start with my solution to the number puzzle from last time.

So, we have a list of numbers L, with n elements, whose sum is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smallest S possible. We are looking for two lists I will call L₁ and L₂.

Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L₁ and L₂ have any numbers in common, we may as well delete the common numbers from both lists, as they will still have equal total sums and products after common numbers are deleted.

At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.

Anyway, thats all I got here.