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.

Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

Passengers Boarding Airplane, Part Deux

2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

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

Combinatorial Sum Identity

For $m,n > 0$ prove that

$\displaystyle 1 + \sum_{k=1}^{m} \binom{k+n}{k} = \binom{m+n+1}{m}$

Harder version:

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{m+n+1}{n+1} - \binom{n+l}{n+1}$

Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.

Circles and Coloring

Several circles are drawn on a piece of paper to form several regions on the paper. We wish to color these regions such that no two regions that share a common boundary would have the same color.

(It is okay if two regions that share a common point to have the same color, but not boundary)

How many colors minimum are needed?

Show and Change

Credit for this problem goes to a friend of Boon Leong Ng.

A ticket to a show costs 10 dollars. There are $(m+n)$ (where $m > n$) people waiting on a line. $m$ of them pays with 10 dollar bills and $n$ of them pays with 20 dollar bills. Assuming that the cashier starts out with no money, what is the probability that the cashier never runs out of change? Assuming the probability is uniform among all possible ordering of people.

Passengers Boarding Airplane

2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.

For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.

What is the probability that the last passenger would sit on his assigned seat?

Solution: http://dharmath.blogspot.com/2010/05/solution-passengers-boarding-airplane.html

Room and Lights Game

This problem is identical to this one but reworded for better clarity.

Alice is playing a game against Bob and Charlie. In a room, there are 27 lights with individual switches, some of them could be turned on or off. Bob enters the room while Charlie waits outside. Alice will tell Bob a number from 1 to 27. Bob then is allowed to flip at most 3 switches if he wishes. Then Bob exits and Charlie enters the room. He has to, upon examining the lights, guess the number that Alice told Bob. Neither Bob nor Charlie knows the configuration of the lights before Bob entered the room.

How can Bob and Charlie agree on a strategy to win this game?

Harder version: 15 lights, but Alice tells Bob a number from 1 to 16, and Bob can only flip at most one switch.

Spy And Radio

A spy is being commissioned by the government to infiltrate a mafia rank in order to find out who the head honcho is. There are sixteen potential candidates and the government needs to know which one of them is the leader. However, the spy only has one chance to pass the information back to the government before she gets murdered.

On an previously-agreed date, the local radio station will announce the winning lottery number. This number will be from 0 to $2^{15}-1$ inclusive, and will be saved as a 15 binary digit data in that radio station's computer. The spy only has one chance to infiltrate the radio station's computer mainframe, change one bit (or none) in that number, and leave. The broadcaster will announce the number without knowing that the spy has changed it, and the government agents will listen to that changed number. The government and the spy don't know the winning number in advance and they have no further power to rig the lottery.

To make things more complicated, the spy does not have that much time in the radio station's computer room. Therefore, she would not be able to perform lengthy and complex calculations. Of course, lengthy and complex is a relative term, but she is a sufficiently accomplished mathematician and she needs to perform this task in less than one minute.

What strategy can be done by the spy and the government so that she can pass the mafia leader's identity accurately with that one chance?

Remark: The following weaker versions of the problem are due to David Rager:

1. Prove that if there are 3 mafia members and 3 bit number lottery winner, you can pass the information with only 1 flip.

2. Prove that if there are 27 mafia members and 27 bit number lottery winner, you can pass the information with only 3 flips.

Prisoners and hats

2047 prisoners are kept in a dungeon. One day, the King decided to do an experiment. They will each be given either a blue hat or a red hat and then collected in a room. Each prisoner can see the color of everyone else's hats but not his own. No form of communication is allowed. After a few minutes, the warden will come and ask each of them individually what he thinks the color of his hat is. They can answer "red" or "blue." Each prisoner must answer by whispering to the warden's ear, so that the other prisoners can't hear his answer. Those who can answer correctly will be freed, but those who answer incorrectly will be executed on the spot. The prisoners found out about this experiment the night before, so they had some time to devise a scheme to ensure they can save as many people as possible.

Question 1: What is the scheme that allows everyone to live in this case?

Suppose now the King decided to alter the experiment a little bit. The warden will come to the room immediately after everyone get their hats. Each prisoner is allowed to answer "red", "blue", or "I don't know." If everyone answers "I don't know", they will all be executed. If someone answers "red" or "blue" and he is wrong, they will all be executed. Otherwise, everyone is freed at the same time. In other words, in order for them to live, at least one person must answer "red" or "blue" and he must be right. As before, the prisoners can't hear everyone's answers, and the release or execution is delayed until everyone had given their answers.

Question 2: What is the scheme that allows everyone to live with the highest probability? What is that probability?