Father, two sons, 999 paintings

Question

This is a question for a job application: "A father has two sons and 999 paintings. Each painting has a different value: first is worth 1, second is worth 2 and so on, until the final painting is worth 999. He would like to divide all of his paintings to his two sons, so that each son gets equal value. How many ways are there to do that with 999 paintings? Example: if father had 7 paintings, he could divide them fairly by giving the first son paintings 1,6 and 7. Second son would get 2,3,4 and 5. Both would have equal value in sum, 14. In case when there are 7 paintings, father can fairly divide them in 4 ways (other 3 not listed here), so the solution is 4. HINT: the number might be large, so send us the last 10 digits and sketch of your solution."

What I did was try to use a brute force approach, adding up all the possible combinations by writing a c# program which writes it's own c# program with loops within loops, like this:

StringBuilder sb = new StringBuilder();
for (short i = 2; i <= 999; i++) //starts from 2 because 1 is always added to the total for one side
{
    sb.AppendLine("for (byte i" + i.ToString() + " = 0; i" + i.ToString() + " < 2; i" + i.ToString() + "++)");
    sb.AppendLine("{");
}

for (int i = 2; i <= 999; i++)
{
    sb.Append("if (i" + i.ToString() + " == 1) { total += " + i.ToString() + "; }\n");
}

for (short i = 2; i <= 999; i++)
{
    sb.AppendLine("}");
}

And then adding this after the if blocks in the result:

if (total == 249750)
{
    count++; //count is a BigInteger
}
total = 1;

This approach should technically work (as tested on a smaller number of paintings), but the problem is it is a HUUUGE number and it would take like a million years or so to calculate the result on my computer this way... Is there some mathematical trick to do this in a reasonable amount of time?

Answer 1

It's easier to approach the more general problem of determining how many ways the first son can get value k, where k is a parameter. There's an art to figuring out the appropriate generalization; it's taught in algorithms courses under the name dynamic programming.

Let x be a variable. The mathematical insight needed is that, for n paintings, the coefficient of x^k in the product of polynomials

x (1 + x^2) (1 + x^3) ... (1 + x^n)

in x is the number of ways that the first son can get value k (including the painting of value 1). This is because this product distributes to

(sum for i_2 = 0 to 1) (sum for i_3 = 0 to 1) ... (sum for i_n = 0 to 1)
    x^(1 + 2 i_2 + 3 i_3 + ... + n i_n),

which effectively is how your brute force solution evaluates this product. The dynamic program here is equivalent to distributing the factors one by one instead of all at once, e.g.,

x (1 + x^2) = x + x^3
x (1 + x^2) (1 + x^3) = (x + x^3) (1 + x^3)
                      = x + x^3 + x^4 + x^6.
x (1 + x^2) (1 + x^3) (1 + x^4) = (x + x^3 + x^4 + x^6) (1 + x^3)
                                = x + x^3 + x^4 + x^6 + x^4 + x^6 + x^7 + x^9
                                = x + x^3 + 2 x^4 + 2 x^6 + x^7 + x^9.

The time savings comes from duplicate terms. Already we have only six terms to contend with instead of eight (two to the third power).

Keeping only the last ten digits means that we can evaluate this product in the ring of integers modulo 10^10. As a result, we can reduce the intermediate coefficients modulo that number to avoid resorting to bignums. This trick, well known to the competitive programming community, is covered formally in courses on abstract algebra or number theory.

In Mathematica:

In[1]:= Coefficient[x Product[1+x^i,{i,2,7}],x^(Sum[i,{i,1,7}]/2)]

Out[1]= 4

In[2]:= Coefficient[x Product[1+x^i,{i,2,8}],x^(Sum[i,{i,1,8}]/2)]

Out[2]= 7

In Java:

public class PartitionPaintings {
    public static void main(String[] args) {
        long[] p = new long[] {0, 1};
        for (int i = 2; i <= Integer.parseInt(args[0]); i++) {
            long[] q = new long[p.length + i];
            for (int k = 0; k <= p.length - 1; k++) {
                for (int j = 0; j <= 1; j++) {
                    q[k + i * j] = (q[k + i * j] + p[k]) % 10000000000L;
                }
            }
            p = q;
        }
        System.out.println(p[(p.length - 1) / 2]);
    }
}

Answer 2

This is a job for mathematics.

You are basically looking for a number partition, one with distinct parts.

The total value of all paintings is the sum of integers 1…999. (n * (n+1)) / 2 according to Gauss, so we get: (999 * 1000) / 2 = 499500. So each son is supposed to get paintings with a total value of 249750.

Now, we just need to find the number partitions of that value with distinct parts that do not exceed 999. We assign each partition we find as the set of paintings for one son, and the second son will get the remaining paintings (which have the same total value).

So the only tricky part is figuring out the partition function for distinct and bounded parts. But I guess you could also do this programmatically.

Mohammadreza Bidar, from the Sharif University of Technology in Tehran, actually wrote a paper with the promising title “Partition of an Integer into Distinct Bounded Parts, Identities and Bounds”. You can read it in INTEGERS, volume 12 (it’s the 8th article there).