========================================================================
CSC 363H                 Tutorial Exercises #10              Summer 2007
========================================================================

The PARTITION problem asks whether a set of weights B = {b1, b2, b3...} 
can be partitioned into two sets of equal total weight.  "Partitioning" B 
means producing two sets, X and Y such that X \intersect Y is empty and X 
\union Y is B.  That is, every element of B must be placed in either X or 
Y, but not both.

Show that SUBSET-SUM reduces to partition.

Given an instance of SUBSET SUM (A = {a1, a2, a3, ..., an}, t), let w 
denote \Sum_i ai.  That is, w denotes the total weight of A.

Then let the set B equal A \union {p = w - t + 1, q = t + 1}.  That is, we 
add two elements to A, with weights w - t + 1 and t + 1.

Then SUBSET-SUM(A,t) iff PARTITION(B)

=>
Suppose there is indeed a subset T of A, with total weight t.  Then the 
total weight of the remaining objects (A - T) is w - t.  Now consider B:  
If we add p to T, and q to (A-T), both sets have total weight w + 1.  So B 
can be partitioned.

<=
Suppose that B can indeed be partitioned, into sets X and Y.  Note that p 
and q cannot both be in the same partition, because already p + q = w + 2 
> w; while the other partition could contain total weight of at most w.

Since the total weight of B is 2w + 2, the total weights of X and Y must 
both be w + 1.  WLOG, let p be an element of X.  Then X - {p} is a subset 
of A that sums to (w + 1) - (w - t + 1) = t.  A does have a subset of 
total weight t.