Problem 8 Solution: "Focus Fire!"

Let G(i,j) be the best possible expected damage using j models in groups of no more than i each.

First, we know that G(1,j) = j*F(1) for all j, because with groups of no more than 1, you just have j groups of 1.

We will now show how to calculate the values of G(i,*) from the values of G(i-1,*). (the * means all the numbers from 1 to n). Consider a grouping of j models in groups of no more than i, and let x equal the number of groups of size exactly i that it has. Thus the rest of the grouping is a grouping of (j-xi) models in groups of size no more than i-1. Thus the best you can do with this part of the grouping is G(i-1, j-xi). So the best possible expected damage total with x groups of size i is xF(i)+G(i-1, j-xi). If you already know the latter values, then you can simply compute this for all possible values of x to find out what the optimal value of x to choose is.

In this way you can construct the entire table of G(i,j) values where 1 <= i,j <= n by starting with i=1 and working your way upward. With each value of G(i,j) you also keep track of what grouping achieves that value. Then the grouping associated with G(n,n) is the result.

This technique of building up the solution to a complete problem (in this case the overall optimal grouping) from a series of solutions to subproblems (in this case the optimal groupings of smaller sets of models with limits on the maximum number per group) is known as dynamic programming, and is commonly used in algorithms to solve many different problems.

Another bit of trivia: the "groupings of N models" we've been talking about (like grouping a unit of 8 into groups of 3, 3, and 2) are known in combinatorics as partitions of N. The section we just finished in my combinatorics class had a significant part of it devoted to how to count up the number of partitions of N that satisfy different constraints, like no number repeated, maximum number less than 3, numbers can have "colors" associated with them, etc.

Problem 7 Solution: By Our Powers Combined

Choose an arbitrary hero H. There are 23 other heroes that H can be paired with, and each pairing must have one of the three fusion types. Therefore, there must exist at least one fusion type such that at least 6 of H's pairings have that type. (In fact you only need 16 other heroes, or 17 including H, for this to be true.) Without loss of generality assume this is true of the targeted fusions.

Now consider any 6 heroes that have a targeted fusion when paired with H. Given these six heroes, form a complete graph with the six heroes as vertices. Color each pairing with a guided fusion red, each pairing with a clearing fusion blue, and the targeted fusions can be colored either red or blue. Then by the special case of Ramsey's Theorem that was previously mentioned, there must exist a group of three whose pairings all have the same color. Without loss of generality assume that this color is red. Now those three have only targeted and guided fusions between them. If you form a team consisting of those three and H, they still only have targeted and guided fusions (because adding H just adds targeted fusions) so they have no clearing fusions available. QED.

Note that the Ramsey's Theorem article also includes a "multicolour example" with three colors that, coincidentally, also requires 17 vertices. However this is not the same as our problem. In that problem they are looking for groups of three that have only one edge color, in this problem we are looking for groups of four that have two edge covers. In fact since R(4,4)=18 (as explained in the article) with 18 or more heroes it would be impossible to make sure every team of 4 had one of each fusion type even if there were only two fusion types.

Problem 6 Answer: "Taking Inventory"

Problem 6.1.

To reduce BIGP to IGP, take each object, as well as the entire grid, and increase its length and width by 1 each. For example, if the BIGP problem had an 8x10 grid, and y one 4x6 object, three 3x3 objects, and five 2x1 objects, the corresponding IGP problem has a 9x11 grid, with one 5x7 object, three 4x4 objects, and five 3x2 objects. If there is a solution to the BIGP problem, then the corresponding solution to the IGP problem can be gotten by extending each object one square right and down - this is always possible because of the buffer. To get from the solution to the IGP problem to the solution to the BIGP problem just go the other way. The image gives an example.

To reduce IGP to BIGP, just reverse the process - decrease each object's length and width by 1
each, and also decrease the grid's length and width by 1 each. However this runs into a problem because it's possible that some of the objects have a length or width of 1, and thus can't be decreased farther. If this is the case then first double the dimensions of all the objects in the IGP problem - this won't change the solution.

Problem 6.2.

Given an instance of the bin-packing problem with N bins of capacity V and a set of objects of size S1, S2, S3, etc., create an instance of IGP with an NxV grid and objects of size 1xS1, 1xS2, 1xS3, etc. Then a solution to the IGP instance can be converted into a solution to the bin-packing problem by putting each object into the bin corresponding to the row that the object was put in in the IGP solution, and of course if there is a solution to the bin packing problem it can be converted into a solution to the IGP instance by reversing the process. So the IGP instance has a solution if and only if the bin packing instance has a solution, so the reduction works.