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}$
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.
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$.
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
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:
With that in mind, let's look into the most basic version
Basic Version
First some assumptions:
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:
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.
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.
Subscribe to:
Posts (Atom)