Wednesday, December 5, 2012

Sum of products of 3

Let $p>3$ be a prime number, and let $S={2,3,\dots,p-1}$ Let $X = \sum_{ i < j < k \in S} ijk$, prove that $X + 1$ is divisible by $p$.

Solution

Because $p$ is odd, let $p = 2m+1$. First we calculate $1^2 + \dots + (p-1)^2 \mod p$. We do this by realizing that $1^2 = (p-1)^2 \mod p, 2^2 = (p-2)^2 \mod p$ and so on. Every term will have a "pair", so the sum is: $$1^2 + \dots + m^2 + (m+1)^2 + \dots + (p-1)^2$$ $$\equiv 2 (1 + \dots + m^2) \mod p$$ $$\equiv m(m+1)(2m+1) \equiv 0 \mod p$$ because $2m+1 = p$. This means that $2^2 + \dots + (p-1)^2 \equiv -1 \mod p$

Next we calculate $1^3 + \dots + (p-1)^3 \mod p$. We do this by realizing that $p = 1 + (p-1) | 1^3 + (p-1)^3, p=2+(p-2) | 2^3+(p-2)^3$ and so on. Like above, each term will have a pair that it cancels out with. Thus $1^3 + \dots + (p-1)^3 \equiv 0 \mod p$, so $2^3 + \dots + (p-1)^3 \equiv -1 \mod p$.

Now we also have that $1+\dots + (p-1) \equiv 0 \mod p$, so $2 + \dots + (p-1) \equiv -1 \mod p$. From this, we have: $$2\sum_{i < j \in S} ij \equiv (-1)^2-(-1) \equiv 2 \mod p$$ $$\sum_{i < j \in S} ij \equiv 1 \mod p$$ because $p$ is odd.

Now, for any real numbers $a_1, \dots, a_n$, let us define the following variables: $$A = a_1 + \dots + a_n$$ $$B = \sum_{i < j} a_i a_j$$ $$C = \sum_{i \neq j } a_i^2 a_j$$ $$D = \sum_{i < j < k} a_i a_j a_k$$ $$E = a_1^2 + \dots + a_n^2$$ $$F = a_1^3 + \dots + a_n^3$$ Then we have: $$AB = (a_1+\dots+a_n)(a_1a_2 + a_1a_3 + \dots + a_{n-1}a_n) = C + 3D$$ The identity from middle to right is because for each $a_i$ in $A$, it's either paired with $a_ia_j$ or $a_j a_k$ in B. If it's paired with $a_i a_j$ then it would contribute towards $C$, otherwise it would contribute towards $3D$. Likewise, each term in $C$ and $3D$ can be traced back to $AB$. Each term $a_i^2 a_j$ in $C$ comes from $a_i$ in $A$ and $a_i a_j$ in $B$. Each term $3a_i a_j a_k$ in $3D$ comes from three sources: $a_i$ in $A$ and $a_j a_k$ in $B$ and its permutations. To further convince ourselves, $A$ has $n$ terms, and $B$ has $n(n-1)/2$ terms, so $AB$ has $n^2(n-1)/2$ terms. $3D$ has $n(n-1)(n-2)/2$ terms and $C$ has $n(n-1)$ terms, so altogether they have $n^2(n-1)/2$ terms.

Furthermore: $$C = a_1^2(A-a_1) + a_2^2(A-a_2) + \dots + a_n^2(A-a_n) = AE - F$$ So: $$3D = AB-C = F + AB-AE$$ This identity holds for any real numbers $a_i$, and it's based on pure algebraic manipulation. We can apply this identity to our set $S$. We already know that $F \equiv -1, A \equiv -1, B \equiv 1, E \equiv -1 \mod p$. From there, we have $3D \equiv -3 \mod p$, which means $(3D+3)$ is divisible by $p$. Because $p > 3$ then $D+1$ is divisible by $p$.

Wednesday, June 13, 2012

An equilateral with side $n$ is divided into smaller equilaterals with size 1 so that they form a triangular lattice. Each segment of length 1 is colored either red, blue, or green. A coloring is called "good" if every equilateral has sides of three different colors. How many good colorings are there? Two colorings are called distinct if at least one segment is colored differently. For example, with $n=1$, there are 6 good colorings. With $n=2$, there are 48 colorings.

Thursday, May 3, 2012

Sum of randomly selected numbers

In a class with 10 students, each student is allowed to choose a number from the following list: 100,101,102,300,301,302. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be 2012? Two "ways" are considered distinct if there is at least one student who chooses different numbers.

Variant: In a class with $2n+1$ students, each student is allowed to choose a number from the following list: $n, n+1, -n, -n-1$. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be zero?

Solution Suppose the number of students who chose 100,101,102,300,301,302 are $a,b,c,d,e,f$ respectively, so we have: $$a+b+c+d+e+f = 10$$ and $$100.a + 101.b + 102.c + 300.d + 301.e+ 302.f = 2012$$

Note that we can write 100=201-100-1, 101 as 201-100, 102 as 201-100+1, 300 as 201+100-1, 301 as 201+100, 302 as 201+100+1, so the second equation becomes: $$201(a+b+c+d+e+f) + 100(d+e+f-a-b-c) + (c+f-a-d) = 2012$$ Since $a+b+c+d+e+f = 10$ then: $$100(d+e+f-a-b-c) + (c+f-a-d) = 2$$

Now, since $|c+f-a-d| \leq 10$ then it must be the case that: $$d+e+f-a-b-c = 0$$ and $$c+f-a-d = 2$$

We also note that when the students choose one of the numbers, they're essentially making two choices: first, they choose if they want to choose small or big numbers (be included in $a+b+c$ or $d+e+f$), and second, they choose if they want their number to end with 0,1, or 2 (be included in $a+d, b+e$ or $c+f$).

Thus, the number of ways to satisfy the first constraint $a+b+c = d+e+f = 5$ is 10C5, which means 5 students choose the small numbers and the rest choose the big numbers.

In order to satisfy $c+f - a - d = 2$, we make the following substitutions: $x = a+d, y = b+e, z = c+f$. Then $x+y+z = 20, z-x = 2$. We divide the cases by the values of $z$. Note that once a student chooses to be included in $x$ or $y$ or $z$, he only needs to choose if he wants to choose a big or small number, since each of $x,y,z$ contains exactly one big and one small number.

If $z > 6$ then $x > 4$, impossible.

If $z = 6$, then $x = 4, y = 0$. There are 10C6 = 210 ways to choose this.
If $z = 5$, then $x = 3, y = 2$, there are 10! / 2! 5! 3! = 2520 ways.
If $z = 4$, then $x = 2, y = 4$, there are 10! / 4! 4! 2! = 3150 ways.
If $z = 3$, then $x = 1, y = 6$, there are 10! / 3! 6! 1! = 840 ways.
If $z = 2$, then $x = 0, y = 8$, there are 10C8 = 45 ways.

If $z < 2$ then $x < 0$, impossible.

So the total number of ways is $$_{10}C_{5} (210+2520+3150+840+45) = _{10}C_{5} 6765 = 1 704 780$$

Solution to variant

Suppose the number of students who chose $-n-1, n+1, -n, n$ are $a,b,c,d$ respectively, so we have: $$a+b+c+d = 2n+1$$ $$(n+1)(b-a) + n(d-c) = 0$$

Note that because $n$ and $n+1$ are relatively prime, so we must have $n+1 | d-c$. But $|d-c|$ can take any values from $0$ to $2n+1$, so $d-c = 0, n+1, -(n+1)$.

If $d-c=0$, then $b-a=0$, which means $a+b+c+d$ would be even, impossible.

If $d-c=n+1$, then $b-a = -n$. Combined with $a+b+c+d = 2n+1$ we have $(a,b,c,d) = (n,0,0,n+1)$. (Remember that $a,b,c,d$ have to be non-negative).

This means that $n$ of the students choose $-n-1$ and the other $n+1$ choose $n$. There are $_{2n+1}C_{n}$ ways to do that.

The case of $d-c = -n-1$ is similar, where $(a,b,c,d) = (0,n,n+1,0)$, and there are $_{2n+1}C_{n}$ ways. Note that all these ways are disjoint, so the total number of ways is $2_{2n+1}C_{n}$

Thursday, April 5, 2012

Teacher distributing coupons

Let $n$ be a positive integer, and $N = n(n+1)(2n+1)$. In a class with $N$ students, each student has an ID number from $1$ to $N$. The teacher then gives each student red, green, and blue coupons as follows:

A student with id $k$ will receive $x$ red coupons, $y$ green groupons, $z$ blue coupons where
$1 \leq x \leq n, n | k-x$
$1 \leq y \leq n+1, (n+1) | k-y$
$1 \leq z \leq 2n+1, (2n+1) | k-z$.

For each student then the teacher gives him a penny based on the median number of coupons he receives. For example, if a student receives 2 red, 4 green, and 5 blue coupons, he gets 4 cents. If another student receives 2 red, 5 green, and 4 blue, he also gets 4 cents. If yet another student get 3 red, 5 green, 5 blue, he gets 5 cents.

Find the total number of money that the teacher has to pay to the entire class.

Solution

Note that $n, n+1, 2n+1$ are all pairwise prime, and $N$ is their LCM. By Chinese Remainder Theorem, we find that for each triplet $(x,y,z)$ such that $1 \leq x \leq n, 1 \leq y \leq n+1, 1 \leq z \leq 2n+1$, there is exactly one $k$ such that $1 \leq k \leq N, k \equiv x \mod N, k \equiv y \mod N, k \equiv z \mod N$. In other words, for each triplet of $(x,y,z)$ within the allowable coupon range, there is exactly one student who receives $x$ red, $y$ green, and $z$ blue coupons.

Solution 1

We divide the cases based on the amount of money a particular student receives. Suppose a student receives $k$ cents.

Case 1: $1 \leq k \leq n$.

Let $x,y,z$ be the number of red, green, and blue coupons he receives.

Case 1a: $x,y,z$ are all distinct.

If $x < y < z$, then $k = y$. For a student to be paid $k$ cents in this manner, $x$ must be from 1 to $k-1$, and $z$ must be from $k$ to $2n+1$, inclusive. Conversely, as long as $x$ is any value from $1$ to $k-1$, and $z$ is any value from $k+1$ to $2n+1$, then $(x,y,z)$ form a triple where the median is $k$. For each of these triples, there is exactly one student who gets paid $k$ cents. So the number of students who gets paid $k$ cents in this manner is $(k-1)(2n+1-k)$, so the total money spent on them is $k(k-1)(2n+1-k)$

Since $k$ is allowed to take range from $1$ to $n$, then the number of students who gets paid via $x < y < z$ configuration is
$$\sum_{k=1}^{n} k(k-1)(2n+1-k)$$

Now, that's just for $x < y < z$. There are 6 permutations of order, and we can repeat the same analysis for each. The total number or $x,y,z$ all distinct is:

$$2 \sum_{k=1}^{n} k(k-1)(n-k) + 2 \sum_{k=1}^{n} k(k-1)(n+1-k) + 2 \sum_{k=1}^{n} k(k-1)(2n+1-k)$$
$$= 2 \sum_{k=1}^{n} k(k-1)(4n+2-3k)$$

Case 1b: two of them are the same, the third higher.

Suppose $x=y < z$, then $k = x = y$. Similar analysis as above, the number of students who gets paid this way is $(2n+1-k)$, and the total money spent on them is $k(2n+1-k)$. Summing from $k=1$ to $n$, and also taking into account cases of $x=z < y, y=z < x$, we have:

$$\sum_{k=1}^{n} k (4n+2-3k)$$

Case 1c: two of them are the same, the third lower.

Suppose $x < y= z$, then $k = y = z$. Again, the number of students is $k-1$, so total amount of money, including cases of $y < x= z, z < x=y$ is:
$$3 \sum_{k=1}^{n} k(k-1)$$

Case 1d: $x=y=z$

$$\sum_{k=1}^{n} k$$

Case 2: $k = n+1$.

Since $x \leq n$, then $x$ cannot be the median nor the top, and $y$ cannot be on top, so the only configuration left is $x < y \leq z$. There are $n$ values for $x$ and $n+1$ values for $z$ (from $n+1$ to $2n+1$). So the number of students is $n(n+1)$ and total amount paid is $n(n+1)^2$

These are all the cases, since the median cannot be greater than $n+1$. Summing over all the sums, we have:

(do the algebra here)

Solution 2:

We divide cases based on the range of $x,y,z$.

Case 1: $1 \leq x,y,z \leq n$

Recall that each triplet $(x,y,z)$ corresponds to exactly one student. We form student pairs as follows: student who receives $(x,y,z)$ is paired with the student who receives $(n+1-x, n+1-y, n+1-z)$. Note that if $n$ is even, then each student gets a pair, but if $n$ is odd, there is a student $((n+1)/2, (n+1)/2, (n+1)/2$ who is paired with himself.

Suppose student $A$ and student $B$ is a pair. Note that if $x < y < z$, then $n+1-x > n+1-y > n+1-z$, so if $A$ gets paid $y$, then $B$ gets paid $n+1-y$. The sum of payment from this pair is $n+1$. It's easy to check that this rule holds for all order configurations ($x = y < z, x < y = z$, etc). In other words, the average income of this pair is $(n+1)/2$. This holds for all pairs, even in the case where a student is paired to himself. The total amount of income for all students in this group is then $n^3 (n+1)/2$.

Case 2: $1 \leq x,y \leq n, z = n+1$.

In this case, since $z$ is the largest of all three, then the median is $\max(x,y)$, summed over all $1 \leq x,y \leq n$.

Case 2a: $x > y$.

Then $\max (x,y) = x$. For each $x$, there are $x-1$ possible values of $y$, meaning there are $x-1$ students, each of which are getting paid $x$ cents. So the total income here is:

$$\sum_{k=1}^{n} k(k-1)$$

Case 2b: $x < y$

By symmetry, it's identical to 2a.

Case 2c: $x = y$.

The total income here is $\sum_{k=1}^{n} k$

Case 3: $1 \leq x,z \leq n, y = n+1$.

By symmetry, it's identical to case 2

Case 4: $1 \leq x \leq n, y = z = n+1$.

The median here is $n+1$, and there are $n$ students, so total income here is $n(n+1)$.

Case 5: $1 \leq x \leq n, y = n+1, z > n+1$

The median here is $n+1$, and there are $n^2$ students, so total income is $n^2(n+1)$.

Case 6: $1 \leq x,y \leq n, z > n+1$

This case is similar to case 2. In fact, EACH value of $z$ is identical to case 2 in that we're summing $\max (x,y)$ over all $1 \leq x,y \leq n$. Case 6 is thus like $n$ instances of case 2.

Spaceship speed

A spaceship has two tanks for two different kinds of fuel. Tank A will be exhausted after one hour, where tank B will be exhausted after $\sqrt{p}$ hours, where $p$ is a prime number. Each tank is being depleted at a constant rate, and when empty, immediately refilled to full from an unlimited reserve. Assume that the refilling time is negligible.

Suppose $V$ represents the spaceship speed at time zero, and $r$ represents the lesser of the ratio between fuels in tank A or B versus their respective capacity. The spaceship speed at any given time is $rV$.

If the tanks are both full at time zero, and the ship travels a really long distance, what is the average speed of the ship? Express in terms of $V$ and $p$.

Wednesday, April 4, 2012

Waiting for the bus

You come to a bus stop served by 3 bus lines: A, B, C. Line A comes every 2 minutes, B every 3 minutes, C every 5 minutes. Each bus line is independent to each other (i.e. they don't have to be in-phase or synced). You board the SECOND bus you see. What's the expected time of waiting?

Solution

First consider line A, regardless of the other lines. Probability that we have to wait $t$ minutes or less is $t/2 (0 \leq t \leq 2)$. Likewise, probability that the first bus from line A doesn't come in $t$ minutes is $1 - t/2$. For line B and C, a similar formula applies.

Now, we consider nine cases of the first two buses we see: AA, AB, AC, ..., CC.

Case 1: AA
This means that bus A comes at time $t$, then at time $t+2$, and in the mean time, bus B and C never come. Obviously $0 \leq t \leq 1$ for otherwise B would have come already. The probability that B doesn't come in $t+2$ minutes is $1 - (t+2)/3$, and probablity that C doesn't come in $t+2$ minutes is $1 - (t+2)/5$. Also, keep in mind that your waiting time is not $t$ but $t+2$. The expected waiting time is thus:
$$\int_0^1 (t+2) (1-\frac{t+2}{3})(1-\frac{t+2}{5})dt = \frac{37}{180}$$

Case 2: AB
This means that bus B comes at time $t$, bus A comes before $t$ and bus C comes after $t$. Note that for $0 \leq t \leq 2$ that means bus A comes in the time between $(0,t)$, but if $2 \leq t \leq 3$, that means bus A comes in the time between $(t-2, 2)$.

$$\int_0^2 (t) (t/2)\frac{2}{3}(1-\frac{t}{5})dt + \int_2^3 (t) \frac{1}{3} (\frac{2-t}{2})(1-\frac{t}{5})dt = \frac{28}{45} + \frac{37}{120}$$

Case 3: AC
$$\int_0^2 (t) (t/2) \frac{2}{5}(1-\frac{t}{3})dt + \int_2^3 (t) \frac{1}{5}(\frac{2-t}{2})(1-\frac{t}{3})dt= \frac{4}{15} + \frac{23}{360}$$

Case 4: BA
$$\int_0^2 (t) (t/3)(1-\frac{t}{5})dt = \frac{28}{45}$$

Case 5: BB
Impossible, because bus A must come at least once in the period between two Bs.

Case 6: BC
$$\int_0^2 (t) (t/3)(1-\frac{t}{2})dt = \frac{2}{9}$$

Case 7: CA
$$\int_0^2 (t) (t/5)(1-\frac{t}{3})dt = \frac{2}{15}$$

Case 8: CB
$$\int_0^2 (t) (t/5)(1-\frac{t}{2})dt = \frac{1}{15}$$

Case 9: CC
Impossible, because bus A must come at least once in the period between two Cs.

The sum of those values is $\frac{83}{36} = 2.3055$ minutes

Wednesday, February 29, 2012

non-injective power mapping

Suppose $p$ is a prime and $f(a) = a^m$ is defined for $a$ that are relatively prime to $p$, then prove that $f$ is injective if and only if $m$ does not divide $p-1$.

Tuesday, February 28, 2012

Musings: rpg combat tuning part 1

After discussions with a few friends about the necessity of holy trinity in RPG (tank, dps / damage per second, healer), I began to wonder if it's possible to design a combat system such that the group doesn't need a tank, dps, or healer. Don't get me wrong, the concept of holy trinity will always be there, but would it be possible to design a system such that the need of a dedicated tank, dedicated healer, or dedicated dps is not needed, or can be variable?

The motivating use case is that in WoW, the standard group composition is 1 tank 3 dps 1 healer (1-3-1). What about 1-2-2? It certainly can work, as long as there's no enrage timer, hard or soft. But what about 1-4-0? It almost certainly won't work. 0-5-0 is even worse. This alone puts some constraints on the nature of group composition, is that you need a dedicated tank, a dedicated healer, and the rest can be dps or healers. The second tank probably won't help that much. Furthermore, each player much squarely choose to be a tank, a dps, or a healer. No double-classing, no double dipping skill points (talents). Thus, you can't have a group that's comprised of, say, 1.5 tank, 2.5 dps, and 1 healer. My goal of this musings is to allow a more creative group composition and that they'd be seriously viable to complete the dungeon. Within reason. (0-0-5 will never work no matter how you put it). To add into your curiosity, there are youtube videos of 10 blood death knight killing a heroic raid boss in Firelands when the content was current (seriously, search it).

To formalize the goal of this article, here are the basic principles:

• To clarify, we are not trying to improve upon WoW or any other RPG combat systems out there. Rather, we are trying to come up with a new system from scratch. A few games such as Guild Wars 2 claimed that it IS possible to alleviate the need of a dedicated tank, but they still need a healer (if I'm reading the beta reviews correctly).
• We are not concerned with what's fun to play or not. Ok maybe we are, but that's a secondary issue that might be revisited in future articles. Part of what makes current RPG so fun is that sense and element of danger that RNG can screw you off or reward you handsomely. As you shall see, in the system that I designed, the effect of RNG is greatly minimized. Any element of fun should come from the encounter design and not the combat system design itself.

• In part 1 (this article), we shall concern ourselves with a pure tank-and-spank style game (Patchwerk style). Anything that deals with movement, environmental damage, adds, etc, would unnecessarily complicate the calculation.

• Furthermore, we're assuming that players are reasonably intelligent. That is, they won't put all their skill points into tanking perks and play as a healer, while wearing dps gear. We're assuming that all players will wear roughly equivalent gear and play equivalently well.

With that in mind, let's look into the most basic version

Basic Version
First some assumptions:

• Each group is comprised of $n$ people.

• DPS: tank and healer does zero (negligible) dps, and all dps does $d$ dps. This would mean that the tank would have some other mechanisms to keep the boss aggroed. One possible solution is that a taunt is permanent until further overwritten (or until tank is dead). The boss does $b$ dps.

• HPS (heal per second): tank and dps does zero self-hps. Health does not regenerate in combat. Healer does $h$ hps. The boss does zero hps.

• Health: The tank has $T$ effective health, and the boss has $H$ effective health. The rest of the players' health should be irrelevant for this version.

• No built in enrage timer, soft or hard.

Now, in the world of perfect tuning, if the gear and skill level of the group is "just right", the boss would die right when the tank dies (or is left with 1 hp). Now, assuming that the configuration is $1-(n-2)-1$, this would translate to:
$$\frac{H}{(n-2)d} = \frac{T}{b-h}$$

The LHS represents the time it takes for dps to burn the boss down, and the RHS represents the time it takes for the boss to kill the tank. $b-h$ represents the incoming damage by the boss after being mitigated by the healer.

Now, suppose that this boss is also killable with $1-(n-3)-2$ configuration, we have additional constraint:
$$\frac{H}{(n-3)d} = \frac{T}{b-2h}$$

Solving both equations, we have $b = (n-1)h$ and $H / d = T / h$. Furthermore, as long as those two relations are satisfied, for any real number $0 \leq k \leq n-1$ we have:
$$\frac{H}{(n-k-1)d} = \frac{T}{b-kh}$$

This means that as long as you have one tank, the number of healers can be any number from zero to $n-1$, and the rest is dps. Note that $k$ doesn't have to be an integer, which gives credence to our assumption as having "1-2.5-1.5" composition or whatnot. Here, $k$ represents the number of healers.

The required relations are then:

1. $b = (n-1)h$. This means that hps of a healer is not a match to the hps of the boss. The tank HP WILL go down steadily throughout the fight, which means that the fight must be sufficiently long otherwise RNG will be too prominent in the fight. Moreover, a short fight won't be fun for everyone.

The length of the time is $H/d(n-k-1) = T/h(n-k-1)$. In order for this fight to be long, then $H/d = T/h$ must be a large quantity. In other words, boss hp is large compared to player dps and consequently, boss dps is small compared to tank hp.

This is the first radical departure from the Wow model: slow early fight assumption. If we want the fight to last 50 seconds with $1-(n-2)-1$ configuration, then the tank health is roughly 50 times $b$. There is no danger of tank dying randomly in the middle of the fight, and damage cannot by spiky. The danger of wipe only comes towards the end when the tank seems to be low on health versus dps trying to burn the last of the boss.

2. $H/d = T/h$, or equivalently $H = Td/h$. The quantity $Td/h$ cannot be arbitary. It is a function of player gear and skill that's intended for that fight. The boss needs to be tuned such that his hp $H$ satisfies that relation. The boss damage $b$ is tuned to be $b = (n-1)h$. The values of $T,d,h$ themselves are not pegged one way or another. Their relative values are only important in PVP (eg, to determine the burstiness and length of average 1v1 game).

Corner case: if the configuration is $1-0-(n-1)$, the boss dps matches healer's hps exactly, so the tank won't die. But since none of them does any dps, the boss won't die either. While this is not a kill, it's not a wipe either, and it's consistent with our definition of well-tuning.

Now, if there are no tanks, we could argue that the players themselves becomes the tank. The collective health pool of healers and dps can be combined to become the "tank." The challenges here is that players must be good enough to taunt off each other just at the right time. Also, the effectiveness of the dps or healer that's currently being hit by the boss is reduced (e.g., spell pushback, hit/expertise requirement from the front, etc). As long as the average health pool of a player is well above $T / n$, the fight is still reasonably-tuned. Note that we're talking about effective health. So even if an average player has, say, 60% the hp of a tank, they won't have the same amount of armor mitigation, magical resistance, damage reduction cooldowns, avoidance, etc. Assumption of $T/n$ isn't that far-fetched assuming $n$ is not too large.

Now, if we have $2-(n-3)-1$, the equation becomes:
$$\frac{H}{(n-3)d} ? \frac{2T}{b-h}$$

which simplifies to $4 ? n$. In other words, if $n = 4$ then the fight is still equally tight-tuned, but if $n > 4$, then the fight is under-tuned (the boss dies well before tank dies). This is where the model breaks down. In fact, the more tanks there are, the more the fight is under-tuned. This is because the presence of the second tank greatly increases the tanks' collective health pool, but the loss of dps doesn't compensate enough.

More radically, if we have $(n-1)-1-0$, the fight is greatly under-tuned, albeit extremely boring, while $2-0-(n-2)$ is severely under-tuned (because no matter how small incoming damage is reduced to, there is still zero group dps but a finite number of collective health pool).

In essence, the model's main weakness is this: In the presence of multiple tanks, a healer is a liability compared to a dps.

There are several ways we can correct this situation, which we shall visit in future articles:

• We can give tanks and healers some nontrivial dps, so that a group without any dps still has chance to kill the boss. Consequently, the healer dps must be nerfed a little bit so that a group of $0-0-n$ or $1-0-(n-1)$ can still wipe.

• We can make multiple tanks composition a little bit less effective. For example, the boss could gain an increased dps buff if he kills someone or is taunted.

• An alternative to nerf multi-tanks: only the FIRST tank gets an hp of $T$, but subsequent tanks' hp won't be as high. This could be achieved via an npc that the MAIN tank talks to before the fight, that increases the main tank's hp from normal to $T$, and only usable once. This is less elegant, but is viable, and somehow similar to Thrall's buff in Ultraxion encounter.

Another thing to note is that we didn't address how difference in mitigation from tank to tank would factor into healing. For example, if tank A has 10k hp with 50% damage mitigation, and tank B has has 5k hp with 75% damage mitigation, they both have 20k effective health. But tank B is far preferable to healers. We can easily rectify this situation by imposing that all tanks will have similar amount of health and mitigation. Wow somehow achieves this via harsh diminishing return curves for parry, dodge, and armor. The rest of our equation is still valid with this restriction.

Tuesday, February 21, 2012

Maximal non-intersecting boat tours

In a country, there are $n$ islands, and each island has exactly one port. A travel agency is planning a series of boat tours where it would employ a number of boats that start and end on these ports. They must obey these rules:

1. Each tour starts and ends at the same port and does not stop at any other port. That is, each tour is a loop that passes through exactly one port.

2. No two tours may intersect each other, except at ports.

3. For two distinct tours A and B, either A must circle an island that B doesn't, or B circles an island that A doesn't. By "circling" an island we mean: the region created by the tour contains the island.

Assuming that all islands have non-zero area and all boats are treated as points, what is the largest number of tours that can be run at the same time?

Solution

Answer: $2n$

First we will show an arrangement of $2n$ tours that satisfy the given constraints, and then we shall show that it is the largest attainable number.

For each island, have a tour that starts at that island and circle it closely to the shore so that we don't greatly alter the shape of the island. Altogether, there are $n$ of such tours.

Then, label the island $I_1, \dots, I_n$. For each $i = 2, \dots, n$, have a tour that starts at $I_1$, circles $I_1, \dots, I_i$ and comes back to $I_1$. There are $n-1$ such tour. Finally we can have a tour that doesn't circle any island. In total, there are $2n$ tours.

The proof for maximality is similar to our construction. There can be at most one tour that doesn't circle any island, and there can be at most $n$ tours that circle exactly one island. Now we show that there are at most $n-1$ tours that circle multiple islands. Let's call a tour that circles multiple islands a "complex" tour.

Suppose $T_1$ and $T_2$ are both complex tours and both circle an island in common $I_1$. Furthermore, WLOG, we can assume that $T_1$ circle an island $I_2$ that $T_2$ doesn't. We assert that $T_2$ must be inside $T_1$. Otherwise, the possibilities are either $T_1$ is inside $T_2$, which is impossible since $T_2$ doesn't contain $I_2$, or that they are disjointed, which is impossible because they both contain $I_1$, or that they intersect. There must be at least two points of intersection, but they can only intersect in ports and they each can stop in oneport only, also impossible. Thus, we have just proved the following statement:

Given two complex tours, either they are disjoint or one is inside the other.

From here, it's matter of induction to show that there can be at most $n-1$ complex tours given $n$ islands. Take the smallest complex tour $T$ that does not contain another complex tour. $T$ circles at least two islands, and any other complex tour either contains $T$ or is disjoint from $T$. So as far as other complex tours are concerned, we can regard $T$ as an island on its own, thereby reducing the number islands by at least 1. Since there are now at most $n-1$ "islands", then there are at most $n-2$ complex tours. Altogether with $T$, we have at most $n-1$ tours.

Wednesday, February 8, 2012

A Divided Kingdom

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:
1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.

Monday, January 30, 2012

Successive reflection

Given 2012 points on the plane: $A_1, \dots, A_{2012}$, and a point $P$. Suppose $B_1, \dots, B_{2012}$ is a permutation of the $A_i$s, we determine the shadow of $P$ as follows:

Reflect $P$ with respect to $B_1$ to obtain $P_1$. Reflect $P_1$ with respect to $B_2$ to obtain $P_2$, and so on, to arrive with $P_{2012}$. We call this last point the shadow of $P$.

Obviously, depending on the permutation of $B_i$s, one may arrive at different shadows of $P$. Find the maximal numbers of shadows of $P$ over all possible permutations.

Saturday, January 28, 2012

Graph with degree 3

A graph where each vertex has degree 3 has all of its edges colored with red, green, or blue. How many colorings are there such that every 3 edges that meet in a vertex are either of the same color or have 3 different colors?

Replacing number on the board

In a blackboard, the number 2012 is initially written. On each turn, the student can choose on of the three numbers: 6, 1006, 1509, and multiply it with the existing number on the board. The existing number is then erased and replaced with the new product.

The teacher has a specific integer $k > 1$ in mind, and the goal for the student is to get the number of the board to have form $n^k$ where $n$ is an integer.

Determine all values of $k$ such that, after a finite number of turns, the number of the board will have the desired form.