The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

  1. Self-preservation: A pirate values his life above all else.
  2. Greed: A pirate seeks as much gold as possible.
  3. Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

And here is a solution to the general case:
[Show Solution]

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.

Baseball division champs

Today’s post is a Riddler problem about baseball, and it goes like this:

Assume you have a sport (let’s call it “baseball”) in which each team plays 162 games in a season. Assume you have a division of five teams (call it the “AL East”) where each team is of exact equal ability. Specifically, each team has a 50 percent chance of winning each game. What is the expected value of the number of wins for the team that finishes in first place?

The problem statement is a bit vague, so we must make some assumptions in order to solve the problem. Our first solution assumes that the win-loss records of the teams are mutually independent.
[Show Solution]

This next solution explains how to tackle the more realistic case where the games are not played independently, and explains why the independence assumption is a good one for the AL East.
[Show Solution]

Double-counting, Part 2

This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!

First identity. This is Vandermonde’s Identity.
\[
\sum_{k=0}^p {m \choose k}{n \choose p-k} = {m+n \choose p}
\]

[Show Solution]

Second identity. This is the Christmas Stocking Identity. It is also sometimes called the Hockey-Stick Identity.
\[
\sum_{k=0}^m {n+k \choose n} = {m+n+1 \choose n+1}
\]

[Show Solution]

Third identity. This one looks similar to the first one, but notice that the upper coefficient is varying this time.
\[
\sum_{k=0}^p {k \choose m}{p-k \choose n} = {p+1 \choose m+n+1}
\]

[Show Solution]

Double-counting, Part 1

Double-counting is one of my favorite proof techniques. The idea is simple: count the same thing in two different ways. In this post, I’ll give some examples of double-counting in the context of proving identities involving binomial coefficients, but it’s a very general technique that can be applied to many other types of problems.

Pascal’s identity. The following is known as Pascal’s identity:

\[
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}
\]

Of course, Pascal’s Identity can also be proven directly using simple algebra, but there is a nice double-counting alternative. Suppose we have a group of $n$ people, and we’d like to choose a committee of $k$ members. There are $n \choose k$ ways of doing this. Now let’s count the number of committees in a different way. Suppose we pick out one particular person from the group, let’s call her Alice. There are $n-1\choose k-1$ committees that include Alice, because after we’ve included Alice, there are $k-1$ remaining committee members to choose out $n-1$ remaining people. Similarly, there are $n-1\choose k$ committees that exclude Alice, because all $k$ committee members must be chosen out of the remaining $n-1$ people. The total number of committees is equal to the number of committees that include Alice plus the number of committees that exclude Alice, and this completes the proof of Pascal’s Identity.

Binomial theorem. Here is another familiar identity:

\[
{n \choose 0} + {n \choose 1} + \dots + {n \choose n} = 2^n
\]

This identity can be directly obtained by applying the Binomial Theorem to $(1+1)^n$. But once again, we can use a double-counting argument. Suppose we have a group of $n$ people. Let’s count the total number of subsets of this group. One way to count is to realize that there are $n \choose k$ different subsets of size $k$. So the total number of subsets of any size is the sum on the left-hand side of the identity. On the other hand, we can count subsets by looking at each person one at a time. Each person can either be included or excluded in the subset ($2$ possibilities), which yields a total of $2\times 2 \times \dots \times 2 = 2^n$ possible subsets.

Binomial products. This example involves products:

\[
{n \choose s}{s \choose r} = {n \choose r}{n-r \choose s-r}
\]

Consider a group of $n$ people. This time, we count the number of ways of selecting a team of $s$ members, among which $r$ are designated as captains. One way to do this is to start by selecting the team, which can be done in $n \choose s$ ways. For each team, we then select the captains, which can be done in $s \choose r$ ways. The total is therefore ${n \choose s}{s \choose r}$. Another way to count is to start by selecting the captains first, which can be done in $n \choose r$ ways. Then, we must select the rest of the team. There remains $n-r$ people and we must choose $s-r$ to round out the team. So the total count is ${n \choose r}{n-r \choose s-r}$.

This technique of committee selection is very powerful. See if you can figure out how to apply it to the following example!

\[
{n \choose 1} + 2 {n\choose 2} + 3 {n\choose 3} + \dots + n {n \choose n} = n 2^{n-1}
\]

[Show Solution]

For more double-counting problems, check out Part 2!

Monsters’ gems

Once again, The Riddler does not disappoint! This puzzle is about slaying monsters and collecting gems.

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

Here is my solution:
[Show Solution]

A more brute-force approach:
[Show Solution]

Yet another solution approach with very nice write-up can be found on Andrew Mascioli’s blog

Overflowing martini glass

This Riddler puzzle is all about conic sections.

You’ve kicked your feet up and have drunk enough of your martini that, when the conical glass (?) is upright, the drink reaches some fraction p of the way up its side. When tipped down on one side, just to the point of overflowing, how far does the drink reach up the opposite side?

Here is my solution:
[Show Solution]

Counting parallelograms

The following problem appeared in the 1991 CMO, and it has a particularly clever solution.

In the figure, the side length of the large equilateral triangle is $3$ and $f(3)$, the number of parallelograms bounded by sides in the grid, is $15$. For the general analogous situation, find a formula for $f(n)$, the number of parallelograms, for a triangle of side length $n$.

triangle_lattice

[Show Solution]

Proud partygoers puzzle

Another great problem from the Riddler blog.

A group of N people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

The solution:
[Show Solution]

A clever integral

I was recently reminded of this problem from one of my favorite books: Problem-Solving Through Problems. The problem originally appeared in the 1980 Putnam Competition.

Evaluate the following definite integral.

\[
\int_0^{\pi/2} \frac{\mathrm{d}x}{1 + (\tan x)^{\sqrt{2}}}
\]

The solution:
[Show Solution]