A tale of two cities

In an island with 257 cities, there are 2018 railroad segments such that each segment connects exactly 2 cities, and each pair of cities are connected by at most 1 segment. A group of 10 cities is called "clustered" if each pair of those 10 is connected by a segment.

Prove that there exist 2 unconnected cities that we can connect without increasing the number of clustered groups.

Solution

Proof by contradiction. Suppose we cannot connect two cities without increasing the number of clustered groups.

Let $n=257$ be the number of cities. Take all possible groups of 10 cities, ${n \choose 10 }$ of them, and count how many segments there are among them. Of course, if the group is clustered, it should have ${10 \choose 2} = 45$ segments. Let $S$ be the sum of unconnected pairs, over all possible groups of 10 cities.

Now let us count $S$ in a different way. Take 2 connected cities $A$ and $B$. The segment $AB$ contributes to $S$ only when the chosen group of 10 cities include $AB$, so this segment is counted ${n-2 \choose 8}$ times. Because there are 2018 segments, then $S$ must be:

$$S = {n-2 \choose 8}.(2018)$$

Note that $2018 < 2020 = 8n-36$, so $S < {n-2 \choose 8}.(8n-26)$. That means, on average, there are $S / {n \choose 10 }$ segments.

Various double counting problems

These problems can all be solved by the double counting principle, that is, to count the same object two different ways and assert that those must match.

Suppose $n > 4$. Let $A_1, A_2, \dots ,A_k$ each be a set of $n$ integers, where $k \leq 4^{n-1} / 3^n$. Show that we can color each integer with one of the four colors so that each set contains integers of 4 different colors.

In a party attended by $n$ people, there were a number of handshakes. A group of 10 persons is called "tight" if each person shook hands with the other 9. It is known that we cannot add another handshake (two people who didn't shake hands now shaking hands) without increasing the number of tight groups. Prove that the number of handshakes is at least $8n-36$

In a class with many students, we choose 2016 committees among them. Each committee has 11 students, and each student may belong to multiple committees. Prove that there is a way to choose some of the students so that each committee has at least one chosen and one unchosen student.

chessboard manhattan move

Given a $2015 \times 2015$ chessboard, a pawn is placed at the bottom left corner. At each turn, the pawn may move one, two, or three squares to the right or to the top, and the goal is to reach the top right corner. The rules are: If the previous move was to the top, then the next move must be to the right. If the previous move was to the right, then the next move must be to the top. The pawn may not move to the left or to the bottom at any point. The difference of length between each two adjacent moves must be exactly 1. How many legal paths are there for the pawn to reach the top right corner?

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

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

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

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.