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}$

Solution 1: Critical Height

Original problem: http://dharmath.blogspot.com/2010/04/critical-height.html

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1

First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.

Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.

From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.

Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
So:
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$

For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.

Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$

Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
...
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.

We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.

Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.

We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.

$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$

So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.

This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.

For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
...
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.

For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$

Simplifying Series

Let $a_n = \binom{2n}{n}$ and $b_n = \binom{3n}{n}$. Find a more compact expression for:

$A(x) = a_0 + a_1x + a_2x^2 +\cdots + a_nx^n + \cdots$

$B(x) = b_0 + b_1x + b_2x^2 +\cdots + b_nx^n + \cdots$

ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

Divide Colored Balls

There are $2n$ balls of each color: red, green, and blue. How many ways are there to divide them into two groups such that each group has $3n$ balls?

First Solution

It is the same as the coefficient of $3n$ in the expansion $(1+x+x^2+x^3+\cdots+x^{2n})^3$. The proof is left to the readers as an exercise.


Note that $(1+x+\cdots+x^{2n})^3 = \frac{(1-x^{2n+1})^3}{(1-x)^3} = (1 - 3x^{2n+1} + 3x^{4n+2} - x^{6n+3})(1-x)^{-3}$

But $(1-x)^{-3} = (1+3x + 6x^2 + 10x^3 + \cdots + \frac{(k+2)(k+1)}{2}x^k + cdots)$

So the coefficient of $3n$ in that expansion is:

$\frac{(3n+2)(3n+1)}{2} - 3\frac{n(n+1)}{2} = 3n^2 + 3n + 1$

Second Solution

We shall prove that there are $3n^2+3n+1 = (n+1)^3 - n^3$ ways, which has striking geometrical interpretations.

Create an equilateral triangle with altitude $3n$, and mark all the points that has integer distance to all the sides. These points will form a triangular lattice

It is a well-known fact that for any point in an equilateral triangle, the sum of distances to the sides is constant. Since the altitude of the triangle is $3n$, then for any point in that triangular lattice, the sum of distance to the sides is $3n$. Furthermore, the distances are integers. Thus, these points represent the number of ways to choose $3n$ balls from 3 colors.

However, the constraint that we only have $2n$ supply of each color is not yet enforced. We examine the points in the lattice whose distance to any of the sides is greater than $2n$, and we eliminate them. So we are left with a hexagonal lattice of side $n+1$. This is the projection of a half-shell of an $n+1$-cube that has $n$-cube carved out of it.

2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$