Father, two sons, 999 paintings

Question

This is a question for the application for work: “The father has two sons and 999 paintings. Each painting has a different meaning: the first costs 1, the second costs 2, etc., while the final picture does not cost 999. He would like to divide all his paintings into his two sons, so that each son gets equal value.How many ways to do this with 999 paintings? Example: if the father had 7 paintings, he could divide them fairly, giving the first pictures of his son 1,6 and 7. The second son will receive 2,3,4 and 5. Both will have an equal amount of 14. In case there are 7 paintings, the father can quite often divide them along 4 paths (the other 3 are not listed here), so the solution is 4. TIP: the number may be large, so send us the last 10 digits and a sketch of your solution.

I tried to use brute force by compiling all possible combinations by writing a C # program that writes its own C # program with loops inside loops, for example:

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 as a result:

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

This approach should technically work (as tested on fewer pictures), but the problem is that it is the HUUUGE number, and it will take about a million years to calculate the result on my computer ... Is there any mathematical trick to do this in a reasonable amount of time?

Answer 1

It is easier to approach the more general problem of determining how many ways the first son can get the value of k , where k is a parameter. There is art to clarify the corresponding generalization; he taught in courses in algorithms called dynamic programming.

Let x be a variable. Mathematical insight is needed, since for paintings n coefficient at x^k in the product of polynomials

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

in x is the number of ways in which the first son can get the value of k (including coloring the value 1 ). This is due to the fact that this product applies 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 is effective, as your brute force solution evaluates this product. A dynamic program here is equivalent to a distribution of coefficients one after another, and not immediately, for example,

 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. 

Time savings come from repetitive terms. We already have only six terms, instead of eight (two to three).

Saving 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 this number so as not to resort to bonuses. This trick, well known to the competitive community of programmers, is officially distributed 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 math.

You are basically looking for a section number , one with separate parts .

The total cost of all the paintings is the sum of the integers 1 ... 999. (n * (n+1)) / 2 according to Gaus , so we get: (999 * 1000) / 2 = 499500 . Therefore, each son should receive paintings with a total value of 249750.

Now we just need to find the numerical sections of this value with different parts that do not exceed 999. We assign each section that we find as a set of paintings for one son, and the second son will receive the remaining pictures (which have the same common value).

Thus, the only difficult part is the definition of the function of splitting into separate and limited parts. But I think you could also do this programmatically.

Mohammadreza Bidar of the Sharif University of Technology in Tehran actually wrote an article with the promising title "Dividing the Whole into Clear Limited Parts, Identities, and Borders." You can read it in INTEGERS, Volume 12 (his eighth article is there).