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, . The initial value of 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, , like so:
In the long term, we assume that there is a steady state probability; in mathematical terms, there is some value of which is invariant under the transformation of :
M is known, so solve for :
Any vector in which all the elements have equal value satisfy this equation. Since represents the sum of probabilities, the total of all elements of . That means that each element of . 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.