Sum over hypercube

Let $n$ be a positive integer, and suppose $a = a_1, \dots, a_{2019}$ is a sequence of integers each ranging from $1,\dots,n$. Determine the sum of $$\sum_a \frac{a_1 - a_2 + a_3 + \dots -a_{2018} + a_{2019}}{a_1 + \dots + a_{2019}}$$ Where the sum is taken over all possible sequences in that range.

Tournament, number of dominated players

In a tournament with $n$ people, each player plays against each other player exactly once, with each game results in a win or a loss (no draw).

If we choose $A$ a set of 5 players at random, let $X_3$ denote the number of players not in $A$ that lose to exactly 3 players in $A$. What's $E[X_3]$? What about $E[X_4]$?

Remark: by choosing $n$ carefully, we can write problems such as: Show that we can choose $A$ and $B$ disjoint groups containing 5 players each so that each player in $B$ loses to exactly 3 players in $A$. The number 5 can be replaced by other numbers too.

Solution

There are $N = {n \choose 5}$ ways to choose set $A$. Of all those choices, we sum up the total number each player loses to exactly 3 players in $A$.

That is, for a given player $x$ that loses $p_x$ times, he contributes to ${p_x \choose 3} {n-p_x-1 \choose 2}$ to the total sum. This is because we can choose ${p_x \choose 3}$ ways to form the part of $A$ that beats $x$, and ${n-p_x-1 \choose 2}$ ways to form the part that doesn't beat $x$, and these are mutually exclusive and independent. Note that if $p_x < 3$ that number is zero as expected.

So the expected value is: $$E[X_3] = \frac{\sum_x {p_x \choose 3} {n-p_x-1 \choose 2}}{n \choose 5}$$ Because $f(t) = {p_x \choose 3} {n-p_x-1 \choose 2} - \frac{t(t-1)(t-2)(n-t-1)(n-t-2)}{3! 2!}$ is a convex function in $t$, we can bound this number by Jensen, noting that $\sum_x p_x = n(n-1)/2$ $$E[X_3] > \frac{{(n-1)/2 \choose 3} {n-(n-1)/2-1 \choose 2}}{n \choose 5}$$ By choosing $n$ carefully, or replacing the numbers 5 and 3 accordingly, we can write problems like: in such and such tournament, show that we can choose 5 players into group $A$ and 5 other players into group $B$ such that each player in group $B$ loses the majority of his games against players in group $A$, or each player in group $A$ wins the majority of his games against players in group $B$.

But finding $E[X_4]$ is a wholly different issue. We can still use the fact that $$E[X_4] = \frac{\sum_x {p_x \choose 4} {n-p_x-1 \choose 1}}{n \choose 5} = \frac{\sum_x {p_x \choose 4} (n-p_x-1)}{n \choose 5}$$ but unfortunately now $f(t) = {t \choose 4} (n-t-1)$ is a concave function, so we can't use Jensen. We can still use majorization theorem however, noting that $\sum_x p_x = n(n-1)/2$. If we want to find a sequence of $p_i$ that's absolutely majorized, we can say that: $$(n-1, n-2, \dots, 1, 0) \succ (p_1, p_2, \dots, p_n)$$ which must be true in the most extreme example that each player has an absolute skill level and each victory is transitive. However, computing $E_4$ in that case is difficult. $$E[X_4] > \frac{1}{n \choose 5} \sum_{k=0}^{n-1} {k \choose 4} (n-k-1)$$ which can be done analytically because the sums of $\sum k, \sum k^2, dots \sum k^5$ can all be computed via telescoping arguments.

If you want to be lazy, you can also say that $(n(n-1)/2,0,\dots,0)$ majorizes everything, but that lower bound is probably lame.

Why did I mention this? Because this type of analysis eventually opens up to problems like:

Show that we can choose $A$ and $B$ such that each member of $B$ loses at least 3 times against $A$, or that players from $A$ wins at least $22$ times against $B$, and so on.

What about the number of victories from $A$ to $B$ though? If we label this quantity $V$, then $E[V] = E[X_1 + 2X_2 + 3X_3 + 4X_4 + 5X_5]$, each of which can be evaluated but the even terms are ugly. $E[X_2]$ is not that bad but $E[X_4]$ is definitely not something you want to do too often.

However, there's a faster way to calculate $E[V]$. By symmetry we know it would be $25/2$, because for every choice of $A$ and $B$, there's an equal probability of choosing $B$ and $A$, and the sum of those victories must be 25.

A related problem from Iran Team Selection Test 2008/6.)

Suppose 799 teams participate in a tournament in which every pair of teams plays against each other exactly once. Prove that there exist two disjoint groups $A$ and $B$ of 7 teams each such that every team from $A$ defeated every team from $B$.

Call applicants to front

Let $n$ be a natural number, and we are given a sequence $a_1, a_2, \dots, a_{2n}$ whose elements are integers from 1 to $n$ inclusive, such that each element in $(1, \dots, n)$ appears at least once.

Now, suppose there are $n$ job applicants $J_1, \dots, J_n$ waiting on a line, in any order. We call them in for interviews using $a_i$ as our "call list." More formally, for $i = 1, \dots, 2n$, we call $J_{a_i}$ one by one.

If a particular job applicant $J_x$ is called for an interview, he has to pay a fee of $y-1$ where $y$ is his position in the line. For example, if he was the second person when called, he pays a fee of 1. If he was the front person, he doesn't pay. After the interview, he returns to the front of the line, and the interviewer proceeds with the next one on the call list.

For a given call list and initial ordering of applicants, we define income as the total fees paid by the applicants. For a given call list, its potential income is the sum of all income over all possible initial ordering of applicants. Now, to make things more interesting, before the interview day, the call list itself was shuffled, such that any $(2n)!$ permutation is equally likely to appear.

If you are tasked with putting together a call list, knowing that it will eventually be shuffled, how should you structure it so that the expected potential income is maximized?

Betting on cards

A deck consisting of $n$ red cards and $n$ black cards are shuffled. The cards are then flipped one at a time. Before each flip, you are allowed to make a bet on the color of the next card. If you guessed right, you win an amount equals to your bet. If you guessed wrong, you lose your bet. You don't have to bet on every flip, in fact you don't have to bet at all if you so wish. The bets can be any amount of real number, and you start with one dollar.

You decide to employ the following strategy. Suppose that, by counting already-flipped cards, you deduce that there are $R$ red cards and $B$ black cards left in the deck. If $R > B$, you guess red while betting $\frac{R-B}{R+B}$ of your total money. Similarly if $R < B$ you guess black while betting $\frac{B-R}{B+R}$ of your total money. If $R=B$ you don't bet that turn. Show that this strategy guarantees a final amount of: $$\frac{2^{2n}n!n!}{(2n)!}$$ Note: this final amount is much bigger than people think. That sum equals to: $$\left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$ which is already greater than 2, and only increases as $n$ increases. This is an extension to the obvious strategy to wait until the last card before we bet the one dollar that we start with, to which we'd be guaranteed a final amount of two.

First Solution

First we claim the following: if at any point there are $R$ red cards and $B$ black cards left in the deck, and your current total is $x$, employing the above strategy will give you a final amount of: $$\frac{2^{R+B}R!B!}{(R+B)!} x$$ That claim is easily verified if either $R+B=1$ because then we would know exactly what's left in the deck. Now we prove the claim by induction on $R+B$. Clearly if $R=B$ then we don't bet that flip, and we reduced it to the case $R+B-1$. But if $R \neq B$, and WLOG we may assume that $R > B$. We bet $\frac{R-B}{W+B}$ that the next card will be red.

Case 1: the next card is red. That means our current total becomes $(1 + \frac{R-B}{R+B})x = \frac{2R}{R+B}x$. But the deck now contains $R-1$ red and $B$ black, so by our induction hypothesis, our final amount will be: $$\frac{2^{R+B-1}(R-1)!B!}{(R+B-1)!} \frac{2R}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$

Case 2: the next card is black and we lost our bet. That means our current total is now $(1 - \frac{R-B}{R+B})x = \frac{2B}{R+B}x$ and the deck contains $R$ red and $B-1$ black, so our final amount is: $$\frac{2^{R+B-1}R!(B-1)!}{(R+B-1)!} \frac{2B}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$ And the claim is proven. Now it's straightforward to apply that if $R=B=n$, we have: $$\frac{2^{2n}n!n!}{(2n)!} = \frac{(2n)(2n-2)\dots (4)(2)}{(2n-1)(2n-3) \dots (3) (1)}$$ $$= \left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$

Expected number of draws

In an urn there are $n$ balls each with weight $w_i$, drawn one at a time without replacement. At any point of drawing, the probability of a ball being drawn is proportional to its weight. What's the expected number of draws before we draw ball 1?

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

Three independent random variables

3 independent random variables $A,B,C$ are drawn from the same distribution. Determine the correlation between $A-B$ and $B-C$.

Solution: Passengers Boarding Airplane

Credit goes to Ed Kao, Vallent Lee and Laurence Tai for helping with the second solution.

Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html

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?

Answer: $\frac{1}{2}$

First Solution

We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.

The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$

For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.

For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.

Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$

Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.

If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.

In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.

Thus the probability from case 2 is $\frac{1}{n-k+3}$

The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.

From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$

Second Solution
We make the following observations:

1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.

Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.

That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.

3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.

From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009

These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.

So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$

Drawing letters

A string of alphabets are randomly generated one letter at a time. Each time, one obtains the letter $A,\cdots,Z$ with probability $p(A),\cdots, p(Z)$. Given that the sum of these probabilities is 1, what is the expected number of draws before the string "DHARMATH" appears?

Paired cards

A standard deck of 52 cards is shuffled with uniform probability. A "pair" is defined as two numerically identical cards that are adjacent in the stack. What is the probability that the deck contains no pair?

Challenge: Find the probability that the deck contains exactly $n$ pair for $n=1,2,\cdots,26$.

Coin Toss

A boy tosses a fair coin repeatedly. Every time he gets a Head, he earns 1 penny, and every time he gets a Tail, he earns 2 pennies. He starts with no money. Prove that the probability of him at one time having exactly $n$ pennies is $\frac{2+(-\frac{1}{2})^n}{3}$

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.

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

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?