Split the square roots of 1, 2, 3, ..., 49, 50 into two groups so that the difference between the sums of...

Knuth has discussed this problem (SELECTED PAPERS ON COMPUTER SCIENCE,
chapter 10.)  You can start by throwing out the squares 1, 4, 9, ...,
49, planning to put them back later so as to make the integer parts of
both sides the same; then you only have to worry about the fractional
parts.  After throwing out the squares you are left with 43 numbers.
Split them into a set A of 21 and a set B of 22.  For each subset S of
A, let a_S be the sum of S minus the sum of A-S, and prepare a sorted
list L of the a_S's.  Prepare a similar sorted list M for B.  The
problem is then to find the elements of L and M that are closest to
each other (modulo 1); this can be done by stepping along L and M in
order, as if we were merging them.

If we have N numbers, this splitting trick reduces the work required
from around 2^N to around 2^(N/2), albeit at the cost of using 2^(N/2)
memory.  (I am neglecting non-exponential factors.)  You can use less
memory (around 2^(N/4)) and around the same time if you do not store L
and M in memory but generate them on the fly by merging 2^(N/4)
sublists of 2^(N/4) elements; since these sublists will all be additive
shifts of each other, you really only need to to store one sublist
(using 2^(N/4) storage) and a priority queue of pointers into it to
perform the merge (also using on the order of 2^(N/4) storage.)

According to Knuth (who uses a few more small tricks as well,) the
optimal solution has {2,3,6,10,11,14,17,18,19,21,22,23,24,26,28,29,32,
34,35,36,39,40,42,45,50} on one side, and achieves a difference of
1.4*10^-13.

BTW, these methods can also be used to solve Rubik's Cube, which may
be viewed as a non-commutative version of this problem.

-- David Moews <dmoews@xraysgi.ims.uconn.edu>

----------

In article <34669448.7D40952D@acm.org> Jim Gillogly <jim@acm.org>
writes:

   This is a traditional "knapsack problem", which is known to be hard
   unless there's some clever trick having to do with the selection of
   numbers.  I don't see one here.  I'd ask the interviewer what it was
   going to be used for, which would determine whether I'd offer her
   the exact solution or an approximate one.

   For the exact solution, a straightforward approach would be to
   enumerate all 2^50 partitions and check how close the sums in one
   half are to the target (half the sum of all the sqrts).  ...

   This is very unlikely to be optimal.  If anybody has a real
   algorithm I'd like to see it.  (Prob'ly should have checked the
   literature, but hacking is more fun.)

Well, the relevance to this group is marginal at best, but it turns
out I solved exactly this problem for a CS algorithms class several
years ago.  (The problem was to get as good an answer as possible; I
think it was intended as a problem that was not reasonably solvable
exactly.)  The first thing to notice is that square roots have a fair
degree of regularity.  For instance, many of them are integer.  All
the integers from 1 to 7 appear as square roots of numbers from 1 to
50, so (it's not hard to see that) any integer from 0 to 28 can be
obtained as a sum of sum of these.  Using this, we reduce 2^7 = 128
possibilities to 29, a factor of 4.4.  A similar analysis for
multiples of sqrt(2) reduces 2^5 = 32 possibilities to 16, another
factor of 2.  Multiples of sqrt(3) (etc) help a small amount more.
(Hmm.  That didn't help as much as I remembered.)

But the real power comes from the following observation.  Ignoring the
numbers that come from regularity of the squares as above, we're left
with 31 numbers.  Let's pretend for a moment that we were only doing a
knapsack problem with 30 numbers.  Now, a knapsack problem with 15
numbers has only 2^15 = 32768 solutions, quite a reasonable number for
a computer to tabulate.  So, to do the problem with 30 numbers, list
all the possible subset-sums for two 15 number sub-problems; sort both
lists; and then walk along the two lists (going up in one list, down
in the other) staying as close as possible to your desired total sum.

On a modern computer, we could do the whole problem like this,
dividing it up as evenly as possible.  But I was working on a Sun 3/50,
which (as I recall) didn't even have enough memory to store 2^15
floating point numbers.  (I don't think I thought of it at the time,
but I guess swapping wouldn't be too much of a problem; memory
shouldn't be a limitation here.  Maybe the bottle-neck was sorting?)
For the rest, just repeat the process above for each sub-problem given
by choosing the first few numbers.  Note you only have to do the
sorting once.  (That is, if you took my suggestions above and created
two lists each 32768 long, you'd have to step along them 29*16*10*6*2
= 55680 times to exhaust all possibilities.  Hmm... That seems like
too many to do in a reasonable time.  I must be misremembering some
details with how long the lists were, etc.)

I think the final version took about 30 minutes on the aforesaid Sun
3/50 to find the best packing.  On a modern computer, it should take
much, much less.

(I got a 13 out of 10 on the assignment; the solution was 3 orders of
magnitude better than the second best :-)

(I came up with the algorithm myself (with some refinements from my
dad), but I later learned it was know before.  I don't remember the
names, sorry.)

(No, you can't iterate this to get a divide-and-conquer algorithm.)

(And no, I don't remember the answer...)

-- Dylan Thurston <dpt@kirkuk.berkeley.edu>