Problem 16 Solution: "Fall Out Pick Up"

(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"

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"

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"

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"

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"

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"

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.