RPG Math Answers

Problem 19 Answer: "Rating Trading, Part 2"

2011-10-31T20:22:00.000-07:00

We prove the problem NP-complete by reduction to the subset-sum problem.

Given an instance of the subset-sum problem, where we have a set A1 ... An, and we want to determine if there is a subset that sums to exactly B.

Let X be the sum A1 + ... + An. (Assume that B <= X; otherwise the problem is trivial.) Consider an instance of the Generalized Math Trade Problem with two participants P and Q. Person P has objects which he values at (2*A1) ... (2*An) and person Q values at (A1 ... An) respectively. Person Q has one object which he values at B and P values at 3X. Choose a target value of 5X-B. The only way to achieve the target value under the constraints is for Q to give P his object, and P to give Q objects from his set that Q values at a total of exactly B. Thus if we had a way to determine whether this was possible, we would have solved the subset-sum problem.

Problem 18 Answer: "Rating Trading"

2011-10-31T19:30:00.000-07:00

Problem 18A. Create a graph in which each node represents a player, and there is an edge from A to B if and only if B wants the game A has. Each edge has capacity 1 and cost -1, and each node has node capacity 1. If the edge from A to B has flow, then that means A gives his game to B. The conservation-of-flow constraints ensure that each person ends up with the same number of games he started out with (exactly one), the node capacity constraints ensure that a player isn't trying to give his game to two or more people at the same time, and "minimizing the cost" means to maximize the number of trades.

Problem 18B. Split each node into two nodes: an "in" node and an "out" node. All the incoming edges go into the "in" node, and all the outgoing edges come out of the "out" node. Add a "synthetic edge" going from the "in" node to the "out" node with cost equal to 0 and capacity equal to the node capacity. This guarantees that the amount flowing through that node is not greater than the node capacity.

Problem 18C. Suppose that I am person A and the people B1 ... Bn all have the same game that I want. What I do is create a "fake" person B that wants each of B1 ... Bn's games, and I say that I want B's game. Then the "person B" will win at most one of the games (and then pass it on to me, since I am the only one who wants B's game).

---

The current "gold standard" for software to do the Math Trades is TradeMaximizer, developed in 2008. The algorithm used is described at the bottom of that page, and as far as I can tell, the graph TradeMaximizer generates is exactly the same as the graph described above - the only difference is that TradeMaximizer formulates it as a bipartite graph matching problem while I formulated it as a network flow problem; the main difference between the formulations is that whether or not there is flow on each "synthetic edge" is inverted. I just hadn't noticed that the graph was bipartite so you can use the special "bipartite graph matching" algorithms, but even normal network flow algorithms are polynomial time (in the case where all the costs are 1), which is much better than the exponential time algorithms they were using for years before TradeMaximizer. Oh, well, if only I had found out about the math trades a few years earlier I could have been famous on BoardGameGeek.

Problem 17 Solution: "Seeds of Victory"

2011-03-18T15:30:00.000-07:00

No. The problem is that there are 12 ways of choosing a Final Four with seeds 1,1,2,3, and only one way of choosing a Final Four with seeds 1,1,1,1. If I choose the Final Four with seeds 1,1,1,1, I will have a 1 in 38.02 chance of success. However. if I choose a Final Four with seeds 1,1,2,3, then I will only have the correct Final Four if both (a) the final four has seeds 1,1,2,3 (this has probability 1 in 14.05), and (b) I correctly predicted which of the twelve (1,1,2,3) combinations would happen (this has probability 1 in 12), for a total probability of 1 in 168.6.

To give a simpler analogy, let's say I flip two biased coins that each have probability 0.6 of coming up heads. It's easy to see that the probability of two heads is 0.36 while the probability of one tail and one head is 0.48. But that's because the "one tail and one head" is really two outcomes, (head, tail) and (tail, head). If I was forced to predict the results of each of the two coin tosses separately, a prediction of (heads, heads) would be right with probability 0.36 while a prediction of (heads, tails) would be right with probability 0.24. And in March Madness you predict each conference separately, not the Final Four seed distribution as a whole. The situation above is the same, where "1,1,2,3" is really 12 different outcomes. ((1,1,2,3),(1,1,3,2),(1,2,1,3)

, etc.)

(Yes, I did send this analysis to Jacobson. I just did it a few minutes ago, so I haven't heard back from him yet, though.)

Problem 16 Solution: "Fall Out Pick Up"

2011-02-24T09:42:00.000-08:00

(Note: We will identify an object of weight a and value b by the notation [a,b].)

(a) and (b).

No. Suppose there was an algorithm with competitive ratio K > 0. Then the adversary operates as follows:

- Choose an integer T that is high enough so that 1/T < K.
- Give the algorithm a capacity (T^2).
- At first, provide the item [T^2, T]. If the algorithm doesn't take the item, then stop there; the algorithm got 0 while it could have gotten T, contradicting the fact that it has competitive ratio K. If it does, then keep providing [1,1] items. If the algorithm ever drops the [T^2, T] item to pick up a [1,1], then stop there; the algorithm got 1 when it could have gotten T. Otherwise, stop after you have provided T^2 [1,1] items; by this point the algorithm got T when it could have gotten T^2. So the algorithm has only achieved 1/T of the optimal, contradicting the competitive ratio K.

So by contradiction, there is no algorithm with competitive ratio K > 0.

(c) Each time you see a new item, pick up the item, then drop the items with the lowest value-to-weight ratio until you get within capacity (this may include dropping the new item; in this case you essentially don't pick it up). If this never involves dropping any items, then you will have picked up every item you got so of course it is optimal. If this does involve dropping items, then at the end you will have at least C-M out of your capacity C filled (because each time you drop an item it reduces the total by at most M, and you don't drop until you're over C). Also, since you're storing the items with the highest cost-to-weight ratio, the space that you did fill you are getting as much value out of it as you can. So the competitive ratio is at least (C-M)/C = 1-(M/C).

Problem 15 Solution: "For Science"

2011-02-19T22:16:00.000-08:00

Specify a bijective mapping that associates each possible ordering with an integer in the range [1,24]. It does not matter how you do this; one way is in lexicographic order (say the wormholes are marked A, B, C, D, then you would have 1 = ABCD, 2 = ABDC, 3 = ACBD, 4 = ACDB, etc). Then you can use binary search to find the correct number by asking questions of the form "Is the number corresponding to the correct ordering less than or equal to X?"

Since there are 24 possibilities, this takes ceil(log_2(24)) = 5 questions.

The generalization is obvious - if there are N wormholes then you map each possible ordering to an integer int he range [1,N!], and so the algorithm takes ceil(log_2(N!)) = O(n log n) questions.

The proof of optimality is easy: If there are k questions, then the number of possible ways of answering those questions is at most 2^k, so if 2^k < N! (which happens if k < log_2(N!)) there is no possible way of distinguishing between the N! possibilities using just the k questions.

[The trick to this question is that you get to ask *any* yes-or-no question; you are not limited to questions of the form "Does X come before Y" that most sorting algorithms use. As an aside, the proof of optimality above is also the standard argument use to show that no comparison-based sorting algorithm can run in better than O(n log n) time.]

Problem 14 Solution - "Community Events"

2010-02-24T21:55:00.001-08:00

Suppose there are N attributes - number the attributes from 1 to N. Then define an N-by-N matrix T as follows: The value in the ith row and jth column of T is equal to the intensity of the link going from attribute j to attribute i, or zero if there is no such link.
Now consider the N-dimensional column vector of attribute values. Suppose the initial event adds the vector J to the vector of attribute values (e.g. if only the i'th attribute was affected, J would have zeros in all positions but the i'th position, and the i'th position would ahve how much was added). Then the amount that is added in addition to that due to links is TJ. But these changes also affect other attributes through links, for an additional effect of (T^2)J. And then (T^3)J, and so on.

So the total change is (I + T + (T^2) + (T^3)...)J. We want to see if (I + T + T^2 + T^3 ...) converges. Since this is a power series of matrices, we can use the eigenvalue decomposition of T - see the section titled "functional calculus" in the linked article for information on how to use the eigenvalue decomposition to find power series of matrices. Since we have all the a_i = 1 (using the notation in the article), it just becomes the regular geometric series, so it converges provided all the eigenvalues of T have absolute value less than 1.

Problem 13 Solution: "Characteristic Characters"

2010-02-22T21:17:00.000-08:00

Consider the system with figured characteristics. Suppose there are N total characteristics. We will make the following definitions:
Let T be an N-dimensional row vector representing the cost per point for each characteristic.
Let P be an N-dimensional column vector representing the number of points of each characteristic that is purchased.
Let R be an N-dimensional column vector representing the number of points of each characteristic that the player actually ends up with.
Let X be the total number of points the player spends on characteristics.
We will now find relationships between these variables.
First, observe that X is just the dot product of T and P - or in other words TP.
Now consider the relationship between P and R. R is equal to P plus the vector V representing the number of "free points" of figured characteristics obtained. But since each element of V is a linear combination of elements of P (of course zero in the case of base characteristics), we can represent this as AP where A is a matrix representing the set of linear equations. So we have R = P+V = P+AP = (I+A)P where I is the N-by-N identity matrix.

In other words, the player gets a final characteristic vector of (I+A)P for a cost of TP points.
Now observe that I+A has ones all along its main diagonal, and is upper triangular (if you list the base characteristics before the figured ones), which is sufficient to show that it is nonsingular, and thus has an inverse, which we will designate as Z.

Now consider a system without figured characteristics, and with a cost vector of TZ. Then in order to get the same characteristic vector as before - (I+A)P - the player he simply buys those characteristics directly, for a total cost of TZ(I+A)P. But since Z and I+A are inverses, they cancel each other out, so the total cost is TP, just as before. This shows that the two systems have the same cost, regardless of what characteristics the player wants to buy.

Problem 12 Solution - "Energy Crisis"

2009-12-08T15:42:00.000-08:00

Problem 12.1.

Let f(x) be the probability of success starting from x mana.

If x=0, we have already lost, so f(0)=0.
If x=y, we have already won, so f(y)=1.
If x is between 0 and y, then after this step there is a 1/2 chance that the player will be at x+1 mana and a 1/2 chance he will be at x-1 mana. Therefore, f(x) = (1/2)(f(x+1)) + (1/2)(f(x-1)).

Now suppose f(1) = A. Setting x=1 in the formula and solving for f(2) gives f(2)=2A (since f(0)=0). Similarly, setting x=2 in the formula and using the newly calculated values of f(1) and f(2) gives f(3)=3A, etc., so f(x)=xA. Since f(y)=1 we must have A=1/y, and thus f(x) = x/y. Therefore, the probability of success starting from X mana is X/Y.

Problem 12.2.

The solution is similar to the problem above, except that f(x) = (3/4)f(x+1)) + (1/4)(f(x-1)). If we set f(1)=A, we get f(2) = (1 + 1/3)A, f(3) = (1 + 1/3 + 1/9) A, f(4) = (1 + 1/3 + 1/9 + 1/27) A, and so on. As x approaches infinity, f(x) approaches 3A/2. Since we know f(1,000,000)=1, and by the preceding f(1,000,000) is approximately 3A/2, we have A=2/3. Thus the probability of success is approximately 2/3.

Problem 11 Solution: "You've Been Blocked"

2009-11-30T10:22:00.001-08:00

Problem 11a.

There are 27 possible combinations (3^3) of 3 block cards. There are 6 ways of having three different block cards, so the probability of blocking a mixed combo of that type is 6/27. Given a particular range of attack coming in, there is only 1 way of having three block cards all of that type, so the probability is 1/27.

Problem 11b.

Out of the 27 possible combinations of block cards, only 8 of them (2^3) do not have any medium block cards (there's 2 possible choices for each of the 3 cards). Thus there is a 19/27 probability of a successful block.

Problem 11c.

There are 7 possible combinations of block cards that have two or more medium block cards, and 19 that have at least one. Therefore, given that the attack was blocked, there is a 7/19 chance that there is another medium block card in his hand. If there isn't, there is a 1/3 chance that he will draw a medium block card on his next turn. Therefore the chance of him having a medium block card is 7/19 + (1/3 * 12/19) = 11/19.

Problem 10 Solution: "All Decked Out"

2009-10-11T10:18:00.000-07:00

Let G be the average number of coins on the cards in your deck (both treasure cards and +coins action cards) and let C be the average number of +cards on cards in your deck (i.e. 0 for treasure cards and action cards with only +coins, or X for action cards with +X cards).

Let P be the expected value of a single card. On average, a single card gives you G gold plus C new cards, and the expected value of those C new cards is P each. So we have P = G+CP, or (1-C)P = G, or P = G/(1-C). This means that the expected value of a five card draw is 5G/(1-C).

Note that if C is equal to or greater than 1, this means that on average you will be able to keep drawing cards indefinitely, and our assumption that you will never run out of cards in your deck would be inaccurate.

Problem 9 Solution: The Killing Fields

2009-10-07T20:56:00.000-07:00

Problem 9a.

Suppose that there exists a strategy S that always succeeds with less than N deaths. Suppose that the worst case number of deaths with strategy S is K, and consider an arrangement of kill zones that leads to K deaths. This means that the first K attempts hit a kill zone, and attempt number K+1 gets through. Now move one of the kill zones that didn't get hit (this must exist since K<N) into the path of attempt K+1 (shrinking it as necessary so it doesn't hit paths from other attempts). Then S won't notice anything different until it's too late, because the algorithm didn't hit that kill zone before and won't hit that kill zone this time until attempt K+1, which will hit it. Thus this algorithm will take at least K+1 deaths on this new arrangement, contradicting the assumption that K was the worst case number.

Problem 9b.

Go up in a straight line. If you hit a kill zone, mark a circle of radius 2 around that point - this is the "danger zone" for that kill zone. You know that the kill zone you hit lies entirely within the danger zone, because the center of the kill zone is at most 1 away from where you got hit, and any point in the kill zone is within 1 of the center. Then make another attempt, but this tim maneuver to avoid the danger zone. If you get hit mark another danger zone, and try again avoiding all danger zones marked so far.

This technique will ensure that you never hit the same kill zone more than once. However we still need to show that it will actually get you to the top. Since each danger zone has diameter 4, the sum of the diameters of all the danger zones is equal to 4N which is less than X, so there isn't enough space for the danger zones to completely block the path to the top, so you will be able to get to the top.

Problem 9c.

This is a trick question: there is no limit. If N > X/2, the defender can position his kill zones in a line across the middle, and since the sum of the diameters of the kill zones is 2N which is greater than X, he can completely block the entire path up, so the attacker will never be able to get to the top.

Problem 8 Solution: "Focus Fire!"

2009-09-30T21:55:00.000-07:00

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

2009-09-23T19:16:00.001-07:00

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"

2009-09-13T21:37:00.000-07:00

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.

Problem 5 Answer: "Mathematically Challenged"

2009-01-22T18:05:00.000-08:00

(a) The best strategy is to have everyone except the person with the +8 skill modifier use the aid another action, and have only the person with the +8 skill modifier actually make rolls for success or failure.

(b) No matter how high the aid another DC was, the above strategy would still be optimal. Even if the aid another DC was so high it was impossible to succeed at, aid another is still useful because it effectively removes the character using it from the rotation. So in this case, having everyone but the +8 player using aid another means that all the meaningful skill checks are made at +8, maximizing the chance of winning.

Problem 4 Answer: "Divvying Up The Loot"

2008-12-20T22:01:00.000-08:00

The second example neglects to add in the value of the shield to the total when calculating the individual share of loot. As instructed, the 1250 GP bid should be added to the 5000 GP in gold to get a total treasure value of 6250 GP, which comes out to 1562.5 GP per player. Thus A would get the shield and 312.5 GP, while the others would get 1562.5 GP each.

BONUS QUESTION: What is the actual maximum possible bid for A? In other words, what bid for A would result in him getting the shield and no gold, while everyone else gets the gold divided evenly?

Problem 3 Answer: "Take Cover!"

2008-12-18T15:28:00.000-08:00

In solutions 3.1 and 3.3, the corner of A's square at which the two dotted lines converge does not cross any line connecting it to D's square, as seen in the diagrams. (Note that the endpoint touches a wall, but endpoints touching walls don't count.) Thus A has unobstructed line of sight, despite clearly being on the other side of a wall.

In solutions 3.2 and 3.4, the corner of D's square at which the two dotted lines converge itself touches a wall, so given any corner of A's square, the line from that corner to D's square will touch a wall. Remember that in problems 3.2 and 3.4, the endpoint touching a wall does count for crossing. Thus D has cover, despite having his back to the wall and there clearly being no obstructions between him and A.

This problem demonstrates that the writers of the D+D rulebook did not do a particularly good job clearly explaining the conditions for cover and line of sight.

BONUS PROBLEM: Suppose we attempt to modify the crossing condition to state that the endpoint at A's square counts for crossing, but the endpoint at D's square does not. (This would invalidate all the anomalies described in the solutions at left.) Is it still possible to find a situation in which D has cover, but no line between an interior point of A's square and an interior point of D's square crosses a wall? (Or the other way around, where D has no cover but every line between interior points crosses a wall.)

Problem 2 Answer: "Too Many Men on the Playing Field"

2008-12-07T22:18:00.001-08:00

With the main character's 100 points, he can have 2^16 100 point followers (20 points for one-fifth of the point value plus 80 points for 16 doublings). Each of these followers can have 2^16 duplicates (also 20 points for one-fifth of the point value plus 80 points for 16 doublings.) Thus the main character can field a total of 2^32 + 2^16 + 1, or a little over four billion, units.

Problem 1 Answer : "Ineligible Receiver (of bullets) Downfield"

2008-12-06T15:17:00.000-08:00

Given the two enemy units A and B, and the friendly unit X. Construct the perpendicular bisector of the line segment AB. Whichever side X is on, that is the unit that is closest.