Riddler: The Babies and the Dwarves

Two relatively easy problems in this weekend’s Riddler. First,

Your baby is learning to walk. The baby begins by holding onto a couch. Whenever she is next to the couch, there is a 25 percent chance that she will take a step forward and a 75 percent chance that she will stay clutching the couch. If the baby is one or more steps away from the couch, there’s a 25 percent chance that she will take a step forward, a 25 percent chance she’ll stay in place and a 50 percent chance she’ll take one step back toward the couch.

In the long run, what percent of the time does the baby choose to clutch the couch?

We can model this as a Markov chain. The probability of baby being n-steps away from the couch can be represented by an N-by-1 vector, p_k . The initial value of p_k is a probability of 1 in the first element (representing starting at the couch) and 0 elsewhere. The transition of probabilities from one step to another is have represented by a matrix, M , like so:

p_{k + 1} = M p_{k}

\begin{Bmatrix} p_{0, k + 1} \\ p_{1, k + 1} \\ \vdots \end{Bmatrix} =  \begin{bmatrix} 0.75 & 0.25 & 0 & 0 & \ldots \\ 0.25 & 0.5 & 0.25 & 0 & \ldots \\  \vdots & \ddots & \ddots & \ddots & \ddots \end{bmatrix}  \begin{Bmatrix} p_{0, k} \\ p_{1, k} \\ \vdots \end{Bmatrix}

In the long term, we assume that there is a steady state probability; in mathematical terms, there is some value of p_k which is invariant under the transformation of M :

p_{\inf} = M p_{\inf}

M is known, so solve for p_{\inf} :

(I - M) p_{inf} = 0

(I - M) = \begin{bmatrix} 0.25 & -0.25 & 0 & 0 & \ldots \\ -0.25 & 0.5 & -0.25 & 0 & \ldots \\  \vdots & \ddots & \ddots & \ddots & \ddots \end{bmatrix}

Any vector p_{inf} in which all the elements have equal value satisfy this equation. Since p_{\inf} represents the sum of probabilities, the total of all elements of p_{\inf} = 1 . That means that each element of p_{\inf} = \lim_{N\to\inf} 1/N = 0 . There is effectively zero probability that the baby will stay at the couch forever.

Now, the dwarves:

A giant troll captures 10 dwarves and locks them up in his cave. That night, he tells them that in the morning he will decide their fate according to the following rules:

The 10 dwarves will be lined up from shortest to tallest so each dwarf can see all the shorter dwarves in front of him, but cannot see the taller dwarves behind him.

A white or black dot will be randomly put on top of each dwarf’s head so that no dwarf can see his own dot but they can all see the tops of the heads of all the shorter dwarves.

Starting with the tallest, each dwarf will be asked the color of his dot.

If the dwarf answers incorrectly, the troll will kill the dwarf.

If the dwarf answers correctly, he will be magically, instantly transported to his home far away.

Each dwarf present can hear the previous answers, but cannot hear whether a dwarf is killed or magically freed.

The dwarves have the night to plan how best to answer. What strategy should be used so the fewest dwarves die, and what is the maximum number of dwarves that can be saved with this strategy?

Extra credit: What if there are only five dwarves?

The answer is straightforward: You can guarantee to save all but one dwarf, no matter how many there are; and that one dwarf has a 50/50 chance of making it. He just picks black if there is an odd number of black dots and white if there is an even number of black dots (which picked color refers to odd or even of which color isn’t important, as long as they all agree). The next dwarf in line knows that if the first dwarf sees an even number of black dots and he sees an odd number, dwarf number 2 knows that he’s wearing a black dot; but if dwarf 2 sees an even number then he’s wearing a white dot. Every further dwarf can deduce their own dot color using the information given by every previous dwarf.

I wish I could claim I was smart enough to come up with this on my own, but the truth is it’s a well known Google interview question.

The Riddler and the Gold Coins: An Alternative Solution

I’m a pretty big fan of the Riddler. I read the puzzles every week and usually try them when I think I’ve got a shot at getting them right.

Last week, the puzzles both were oriented around sorting between fake and real gold coins by using a limited number of weighings on a balance scale. First, the easy one:

You have nine gold coins, but one isn’t pure. One has been minted with a cheap alloy, and is known to be heavier than the others. You have a simple balance scale. How do you determine the impure coin with only two weighings?

The solution to this one was pretty straightforward, and my solution was identical to the one presented this week. The second riddle was a little harder:

You have 12 gold coins — or so you think! One is fake and is known to have a different weight than the others. It could be heavier or lighter; you only know it’s wrong. Using the same simple balance scale, how do you determine the incorrect coin, and whether it is heavier or lighter, in only three weighings?

I got the solution to this one too. However, I was disappointed to see that the solution presented in this week’s column was different from mine, and in my opinion, not nearly as elegant. The official included a pair of if-then type statements—weigh 4 coins against 4 other coins, and leave 4 coins off. If the scale balances, then the fake coin is in the group not on the scale, and it’s easy to find the right coin in 2 more weighings. If the scale doesn’t, then it’s one of the 8 on the scale and there is a more complex weighing scheme.

I think my solution, below, is better because it prescribes the exact same experimental procedure regardless of the outcome of the weighings. I also conjecture that the FiveThirtyEight solution is mathematically equivalent but easier to picture.

Label the coins A thru L. Use the table below to put the coins on the correct spot–L for left balance, R for right balance, O for off the scale. W1 is the first weighing, W2 the second, and W3 the third.


--| A | B | C | D | E | F | G | H | I | J | K | L |
---------------------------------------------------
W1| O | O | O | O | L | R | L | R | R | L | R | L |
W2| O | R | R | R | O | O | O | L | L | L | R | L |
W3| R | O | L | R | O | R | R | O | L | O | L | L |

Find the pattern of tips left (L), tips right (R), or balances (B) in these two
tables. The column indicates which coin is fake. If the pattern is in the first
table, the fake coin is heavy. If it’s in the second, it’s light.

Heavy table

| A | B | C | D | E | F | G | H | I | J | K | L |
-------------------------------------------------
| B | B | B | B | L | R | L | R | R | L | R | L |
| B | R | R | R | B | B | B | L | L | L | R | L |
| R | B | L | R | B | R | R | B | L | B | L | L |

Light table

| A | B | C | D | E | F | G | H | I | J | K | L |
-------------------------------------------------
| B | B | B | B | R | L | R | L | L | R | L | R |
| B | L | L | L | B | B | B | R | R | R | L | R |
| L | B | R | L | B | L | L | B | R | B | R | R |