Tag: recursion

On the tenth Friday, all mathematicians will resign. To understand why this happens, we’ll use a recursive approach similar to what we did for the puzzle of the pirate booty.

For simplicity, we’ll say a mathematician is flawed if they made a mistake, and perfect otherwise. Let’s look at the world through the eyes of Alice, one of the ten mathematicians. Alice doesn’t know whether she is flawed or not. She does, however, know how many of her colleagues are flawed.

According to the problem statement, all the mathematicians are flawed. So Alice sees that all nine of her colleagues are flawed. Let’s solve a simpler version of the problem first. What if none of Alice’s colleagues were flawed? In this case, the news that “someone here has made a mistake” can only mean one thing: that “someone” must be Alice! So Alice will resign on Friday.

What if exactly one of Alice’s colleagues is flawed? Two possibilities:

• If Alice is perfect, then the flawed mathematician will see that everyone else is perfect and resign on Friday, just as Alice would have done in the previous case when she saw her colleagues were all perfect.
• If Alice is flawed, then nothing happens on Friday. Alice then deduces that she must be flawed and resigns on the next Friday.

What if exactly two of Alice’s colleagues are flawed? Two possibilities:

• If Alice is perfect, then each flawed mathematician sees one other flawed mathematician. As in the previous case, we expect them to both resign on the second Friday.
• If Alice is flawed, then nothing happens on the second Friday. In that case, Alice will know of her flaw and resign on the third Friday.

The pattern is clear: if Alice has $k$ flawed colleagues but Alice is perfect, then the flawed mathematicians all resign on the $k^\text{th}$ Friday. If Alice is flawed, then nothing happens on the $k^\text{th}$ Friday, and Alice resigns on the $(k+1)^\text{st}$ Friday (along with all the other flawed mathematicians). In particular, if all ten mathematicians are flawed as in the problem statement, they all resign on the tenth Friday.

But but but…

It seems that we have a paradox — we aren’t telling the mathematicians anything they don’t already know! Each mathematician can clearly see that they have flawed colleagues, so why should explicitly announcing this fact make any difference? The answer lies in the distinction between mutual knowledge and common knowledge.

If everybody knows some proposition $P$ to be true, then $P$ is mutual knowledge. However, if everybody knows $P$, and everybody knows that everybody knows $P$, and everybody knows that everybody knows that everybody knows $P$, and so on, then $P$ is common knowledge. Although the fact that there is at least one flawed mathematician is mutual knowledge, it is not common knowledge. When the super-mathematician makes her announcement that there is at least one flawed mathematician, it becomes common knowledge, and this makes all the difference.

Rather than giving a detailed solution, I will defer to some other existing solutions online that are already well-explained. No need to reinvent the wheel! Here are some pointers.

• The solution to the blue eyes puzzle featured on the xkcd website.
• The wikipedia article on common knowledge, which uses the blue eyes puzzle as an illustrative example.
• A post on the math stackexchange site that gives a detailed an formal proof of result.

This problem is a perfect example of when to use recursion. If there are $P$ pirates, when each pirate contemplates how to vote, they are comparing what would happen if they voted yes (and agreed to the current proposal) to what would happen if they voted no (and the current pirate died, reducing to the $P-1$ case).

Let’s start with two pirates and build up from there. For each case, here is a list of each pirates’ share of the gold. We ordered the pirates from lowest rank to highest rank (captain).

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & 10 \end{bmatrix} && 1\\
v_3 &: \begin{bmatrix} 1 & 0 & 9 \end{bmatrix} && 2\\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & 9 \end{bmatrix} && 2\\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_7 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_8 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_9 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5 \\
v_{10} &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5
\end{align}

Let’s examine this table one row at a time. If there are two pirates ($v_2$), a majority is decided by a single vote. Since the captain gets to vote, they can safely propose to keep all the gold.

If there are three pirates ($v_3$), a majority is decided by two votes. So the captain needs to secure one extra vote. The first pirate (lowest rank) won’t win anything if the captain dies, because we would reduce to the $v_2$ case. The captain must give this pirate at least one gold piece to buy their vote and avoid death, but can keep the remaining $9$ pieces.

Similarly, if there are four pirates ($v_4$), a majority is decided by two votes. This time, the first pirate’s vote costs two gold pieces because they stand to win one gold piece if we reduce to $v_3$. However, the second pirate’s vote now costs one gold piece because they win nothing in the $v_3$ case. A similar argument applies as we continue to add pirates.

The final solution is that if we number the pirates $1,2,\dots,10$ in order from lowest rank to highest rank, then pirates $2,4,6,8$ each get one gold piece and the captain gets $6$ gold pieces.

As we saw in the previous solution, it makes sense to recurse on $P$, the number of pirates. If $G$ is the number of gold pieces, the pattern we observed in the simpler case still hold here, and we can continue it until the captain runs out of gold and is no longer able to bribe enough of his fellow pirates. So the table looks like:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & G \end{bmatrix} && 1 \\
v_3 &: \begin{bmatrix} 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
&\vdots &&\vdots\\
v_{2G+1} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 \end{bmatrix} && G+1\\
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1
\end{align}

In the last two rows of the table, there are $G$ 1’s. In the case with $2G+2$ pirates, a majority is decided by $G+1$ votes, so the captain wins nothing; they must forfeit all the gold in order to buy the votes necessary to survive. From this point forward, it may seem that if we add any additional pirates, they will be killed because there isn’t enough gold to buy enough votes. However, this isn’t quite the case. Here is what happens if we keep adding pirates:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}3}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}2 \\
v_{2G+4} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} && G+2 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}5}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}6}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}7}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} & {\color{red}0} \end{bmatrix}\hspace{-2cm} && \color{red}G\color{red}+\color{red}4 \\
v_{2G+8} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\hspace{-2cm} && G+4
\end{align}

Once we get to $P = 2G+3$ pirates, the captain will always be killed (deaths are indicated in red) since there isn’t enough gold to buy the required votes. In the $2G+4$ case, however, the second in command is doomed to die if he votes to kill the captain, so he will vote yes even if offered nothing. This gives the captain a free vote, which is enough to secure the required $G+2$ votes. The captain must make an offer that compares favorably to the $2G+2$ case since the intermediate case $2G+3$ always leads to $2G+2$.

In the $2G+5$ case, none of the pirates have an incentive to keep the captain alive (since everybody will be safe with $P=2G+4$). The same happens with $2G+6$ and $2G+7$. Once we arrive at $2G+8$, three of the pirates are doomed if the captain dies, so they will vote yes even if offered nothing. Once again, this allows the captain to barely survive. This pattern continues, each time doubling the interval length between safe captains.

The solution to the general problem. Number the pirates $1,2,\dots,P$ in order from lowest rank to highest rank. If we have $G$ gold pieces to distribute, then we consider two cases:

1. If $P \le 2G+2$, then:
• If $P$ is odd, pirates $1,3,5,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-1}{2}$ pieces.
• If $P$ is even, pirates $2,4,6,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-2}{2}$ pieces.
2. If $P > 2G+2$, then the highest ranked captains will die until there are $P = 2G+2^k$ pirates remaining with $k$ as large as possible. Then:
• If $k$ is even, pirates $1,3,5,\dots,2G-1$ each get one gold piece and nobody else gets anything.
• If $k$ is odd, pirates $2,4,6,\dots,2G$ each get one gold piece and nobody else gets anything.

In the case where $P \ge 2G+2$, the solution is not unique in the sense that once we arrive at $P=2G+2^k$, there are other admissible ways of dividing up the gold besides the one shown above.