Pages

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