Wayne sprung this question on me yesterday. I swear he should have been a CS major.
The Hundred Hatted Prisoners
There are a hundred prisoners in a dungeon, sentenced to be executed the next morning. Fortunately for them, the king of the land is eccentric and offers them a chance to survive. He tells them he’ll line them up, one in front of the other, with the most guilty in the back and the least guilty in the front. They’ll be bound, so it will be impossible for them to see those behind them, but they’ll be facing down a gentle slope and will be able to see all the prisoners in front of them clearly.
Next, the king will place a hat on the head of each prisoner. Some hats will be blue and some will be red, but the exact number of each is secret. The prisoner in the very back will be able to see which color of hats the other ninety-nine prisoners are wearing. The second prisoner will be able to see the hats of the ninety-eight prisoners in front, but not his own or the one on the prisoner in the back. It will continue like this, up to the prisoner at the very front of the line, who cannot see any of the hats.
Finally, the king will walk up the line, starting from the back, going to the front, asking each prisoner what color his own hat is. Anyone who answers incorrectly will be executed immediately, via silent odorless methods undetectable to those who haven’t yet been asked what color their hats are.
The prisoners may talk with each other tonight and collude to create a strategy for the next day. Once they are lined up for execution, though, they will not be allowed to speak, except to answer the king when he asks, “What color is your hat?” Even then, they may only utter a single word, “red” or “blue”.
If the prisoners work together with the right strategy, how many need to risk their lives?
This logic puzzle doesn’t really have a “sucker answer” like the coin-tossing one did, but the answer is a smaller number than one might first think. It’s a smaller one than I first thought.
Imagine there’s a completely random event with two outcomes, say flipping a coin. Each flip has an equal probability of landing heads or tails. Now imagine that we’re interested in seeing how long it takes to get a certain sequence of outcomes. Pattern 1
Tails, Heads, Tails Pattern 2
Tails, Heads, Heads
Now, suppose we flip a coin until Pattern 1 is reached, note how many coin flips it took, and then we repeat the process many times and average how many flips it takes to get a tails-heads-tails sequence . After that, we go through the same process to see how many flips it takes to get Pattern 2, a tails-heads-heads sequence.
On average, which pattern takes fewer coin tosses?
They'll happen equally fast, on average. (78%, 1,775 Votes)
The results weren’t exactly stellar. As expected, the sucker answer of “They’ll happen equally fast, on average.” got the vast majority of the votes. The correct answer of “Tails, Heads, Heads takes fewer tosses!” drew less than ten percent of the total. Worse still, the people who chose “Tails, Heads, Heads takes fewer tosses!”, outnumbered those who admitted defeat more than five-to-one.
It wasn’t all bad, though! Some commenters not only arrived at the correct answer, but produced programs to prove it. The very first such comment was well-formatted LISP code. I have to say, it’s great to be getting feedback back of this level of geek-cred.
Some commenters produced a mathematical derivation of the average number of coin flips that it takes to get a tails-heads-heads sequence vs. a tails-heads-tails sequence. The problem is tricky, but it really is a simple problem. Once it’s properly framed, it’s a first year high school algebra problem– two linear equations to be solved for two unknowns. Here’s a basic walk-through of the process to find out how many flips it takes, on average to get THT:
First, let's define a few terms:
N[THT|TH] is the average flips to get THT once we already have TH
N[THT|T] is the average flips to get THT once we already have T
N[THT|] is the average flips to get THT, starting from scratch
The easiest term to find is N[THT|TH]. There's a 50% chance that
we'll get tails on the next flip. In that case, the number of flips
to match the pattern is 1. If we get heads on the next flip, then
the number of flips is 1 + N[THT|]. Therefore,
N[THT|TH] = .5(1) + .5(1 + N[THT|]), or
N[THT|TH] = 1 + N[THT|]/2
If we already have N[THT|T], then we have a 50% chance of
getting heads, which would mean the total flips would be that flip,
plus N[THT|TH], and a 50% chance of getting tails, which would
mean that flip plus N[THT|T]. Therefore,
N[THT|T] = .5(1 + N[THT|TH]) + .5(1 + N[THT|T])
N[THT|T] = 1 + N[THT|TH]/2 + N[THT|T]/2
N[THT|T]/2 = 1 + N[THT|TH]/2
N[THT|T] = 2 + N[THT|TH]
If we're starting from scratch, i.e. N[THT|], we have a 50% chance
of tails, which would give us that flip plus N[THT|T], and a 50%
chance of heads. Since heads would be useless, that would mean
one flip plus N[THT|]. Therefore,
N[THT|] = .5(1 + N[THT|T]) + .5(1 + N[THT|])
N[THT|] = 1 + N[THT|T]/2 + N[THT|]/2
N[THT|]/2 = 1 + N[THT|T]/2 (subtracting N[THT|]/2)
N[THT|] = 2 + N[THT|T] (multiplying each side by 2)
Now, we know that starting from scratch takes two more flips than
starting from T, or four more flips than starting from TH. We plug
this back in.
N[THT|TH] = 1 + N[THT|]/2 (our first equation)
N[THT|] = 4 + 1 + N[THT|]/2 (substituting for N[THT|T]
N[THT|]/2 = 5 (subtracting N[THT|]/2)
N[THT|] = 10
On average, it takes ten flips to get tails-heads-tails.
After getting the general idea, it’s very quick to solve for how many flips it takes to get THH:
Here are the basic equations for N[THH|TH], N[THH|T], and N[THH|]:
N[THH|TH] = .5(1) + .5(1 + N[THH|T])
N[THH|T] = .5(1 + N[THH|TH]) + .5(1 + N[THH|T])
N[THH|] = .5(1 + N[THH|]) + .5(1 + N[THH|T])
Solving for N[THH|]:
N[THH|]/2 = 1 + N[THH|T]/2
N[THH|] = 2 + N[THH|T]
Solving for N[THH|T]
N[THH|T] = 1 + N[THH|TH]/2 + N[THH|T]/2
N[THH|T]/2 = 1 + N[THH|TH]/2
N[THH|T] = 2 + N[THH|TH]
Solving for N[THH|TH]
N[THH|TH] = 1 + N[THH|T]/2
N[THH|TH] = 1 + (2 + N[THH|TH])/2
N[THH|TH] = 2 + N[THH|TH]/2
N[THH|TH]/2 = 2
N[THH|TH] = 4
Plugging in and solving for N[THH|], we get:
N[THH|T] = 4 +2
N[THH|] = 4 + 2 + 2 = 8
On average, it takes eight flips to get tails-heads-heads.
Even though the math involved is basic, it’s very easy to jump to the wrong conclusion. As one commenter mentioned, one of the brightest collections of people on the planet tanked on a logically equivalent question. Like me, the speaker of that video was also thinking about the long and ignoble history of experts bungling mathematics in courts. Our brains just aren’t really wired for mathematical abstraction.
Notes: 1) Only one vote per IP address was allowed, but the vote counts on this poll are just as unreliable as any other internet poll. I re-worded the poll options after about 150 votes had already been made, in order to make the question less ambiguous. People were also perfectly free to read all feedback from other visitors before voting.
2) This probability puzzle has a wide variety of applications, including in determining bankroll a successful gambler or investor will need, and in gene sequencing.
3) I’m in a sleep-deprived state as I post this. Please be gentle on any errors.
This is the second part of The Enemies of Reason, in which Professor Dawkins interviewed various practitioners of pseudo-science. In this video, Dawkins focuses on the booming alternative health business:
It’s the hottest alternative health fad. It boasts and impressively vast and well-stocked medical cabinet; it’s endorsed by royalty and the stars, and is doing a booming trade in high street pharmacies. Five hundred million people world-wide claim to use it.
What is it? It’s a system for dosing up on a dilute solution of… water.
In all honesty one of the factors that has led me to invest so much in Chinese companies is the undervaluation of the RMB. The explosive growth of the middle class and the economy as a whole is the main reason, but currency concerns definitely factor in. Yesterday, I stumbled on the most jaw-dropping estimate for RMB-appreciation I’ve seen yet.
Ever wonder why so many expert witnesses lead juries astray due to mathematical errors? Or why so many gamblers and investors are so bad at assessing relatively simple probability questions? First imagine that you consider yourself an expert (at something other than math), and then you encounter a question like this…
Imagine there’s a completely random event with two outcomes, say flipping a coin. Each flip has an equal probability of landing heads or tails. Now imagine that we’re interested in seeing how long it takes to get a certain sequence of outcomes.
Tails, Heads, Tails
Tails, Heads, Heads
Now, suppose we flip a coin until Pattern 1 is reached, note how many coin flips it took, and then we repeat the process many times and average how many flips it takes to get a tails-heads-tails sequence . After that, we go through the same process to see how many flips it takes to get Pattern 2, a tails-heads-heads sequence. For example if we start flipping a coin for pattern 1 and we see:
tails, heads, heads, tails, heads, tails
Then we reached Pattern 1 after only six coin tosses. Sometimes it will take as few as three coin tosses, but other times it will take many more. If we were to repeat this test thousands of times and calculate the average number of tosses it takes to get Pattern 1 and compare it to the average number of tosses it takes to get Pattern 2, which be the bigger number?
On average, which pattern takes fewer coin tosses?
They'll happen equally fast, on average. (78%, 1,775 Votes)
The first correct answer with a valid explanation wins a beer (if you can make it to Taipei to collect). Update: Two correct answers are in! Ray Myers, with some lisp code to brute force the answer, and Robin with a clear explanation of why. When and if you make it out to collect, drinks at the Taiwan Beer Factory are on me.
Yesterday, Morris Chang, the CEO of Taiwan Semiconductor Manufacturing Corp., spoke to the American Chamber of Commerce on Taiwan’s international competitiveness. For the most part he had good things to say, ranging from education to work ethic to democracy:
“Taiwan benefits from a highly educated population, a healthy ecosystem and industrious, diligent workers,” said Chang. The island, he added, has one of the highest literacy rates in the world. In addition, up to 70 percent of the college-age population go on to attend institutions of higher learning. Strong technical abilities also make Taiwanese workers highly desirable.
“While such measurements are not easily quantifiable,” stressed Chang, “I think that anyone who has worked with Taiwanese people will agree that they are very industrious and hard-working.”
In terms of the ecosystem, Chang reported that Taiwan has had an evolving market economy for 20 to 30 years; politically, freedom and democracy have been present for more than 10 years.
He did mention a few areas for improvement. The first is economic openness to globalization:
“This is the biggest weakness in the near term,” said Chang. “Incomplete globalization is becoming more and more a drag on the economy. During the last 10 years, as globalization has accelerated, Taiwan has either stood still or even gone backward.”
During this time, said Chang, Taiwan should have become the portal to the world’s fastest-growing economy-China.
“If Taiwan had seized the opportunity 15 to 20 years ago, its economic development would be much faster. It simply failed to take advantage of that opportunity.”
Chang also commented about a need for more democratic institutions to accompany its progress of the last decade. Specifically, he mentioned the needs for greater balance between the branches of the government, for moving to a high trust society, and for better corporate governance. Like many, many foreign teachers I know in Taiwan, Chang expressed hope for a transformation of educational systems that would lead to a greater emphasis on creativity, claiming that “There is too much emphasis in Taiwan on transfer of knowledge and not enough on independent, creative thinking”.
Finally, he touched on the three links that Chen and Hseih have been sparring over so bitterly this month.
Since China is so large and Taiwan much smaller, Chang recommended that Taiwan serve as a portal to its much bigger neighbor, saying, “Given that Taiwan has only 2 percent the population of China, I think that it is best if Taiwan-similar to Hong Kong-plays the role of a gateway.”
Any resulting divisions of labor, in investment or R&D between Taiwan and China are still very much an “academic question,” as Taiwan is not yet sufficiently open to China, although Chang did not see any particular reason to fear competition from Chinese companies.
“It is not a question of losing out to Chinese companies but to any companies,” he said. “To keep from losing out, you have to safeguard your trade secrets and protect your IP.”
Regardless of which presidential candidate wins the next election in March, Chang thinks a more open policy to China will emerge. When asked what he would do if he had a magic wand that could solve any problem facing Taiwan, Chang responded with: “Right now, I would lift restrictions on investment and open the three links,” saying these policies have contributed to one of Taiwan’s chief weaknesses, namely an economy that is “incompletely globalized, incompletely opened.”
I recently received this email from a high school teacher in Florida:
I came across your textbook reviews online and they all seem to focus on college level chinese and traditional characters. I just started teaching high school Chinese and I’m looking for a textbook that will allow me to focus on tones, simplified characters, and pinyin. A workbook or audio cd that goes along with it would also be helpful. Do you have any recommendations? Thanks in advance.
Then, in a follow-up email, she said:
… the focus is on language, culture and society. Unfortunately, the language aspect of the class is not supposed to be too intensive, but I would be happy if the students could get the tones down and learn some basic survival Chinese and sentence patterns. I’m thinking about using the New Practical Chinese Reader available on Amazon.com. Do you have any experience with this book? Thanks!
I haven’t ever used the New Practical Chinese Reader, but I know that the Far East series I reviewed has simplified versions of their books and they have some books for younger learners, too. Unfortunately, I haven’t seen many books targeted at high school students. I’ll bet John might know, though. Can anybody else help Ruth out?
Solar Power, it’s not just for granola-chomping hippies anymore. Solar power generation has been increasing exponentially for decades, but as futurist Raymond Kurzweil once said, nobody notices exponential growth until it hits the “knee of the curve“. Fortunately for us and our planet, it nearly has.
Between 2000 and 2004, the increase in worldwide solar energy capacity was an annualized 60 percent. Since 2005, production of photovoltiacs has grown somewhat more slowly due to temporary shortages in refined silicon. Still, technological progress has been relentless. In 1990, each watt of solar power from an array cost $7.50. By 2005, average prices in the US were nearly halved, at $4.00. Today, the price stands at about $3.60, even with the refined silicon shortages. Mass produced cells typically have an efficiency of about 17.5%, with some at the very high end achieving 30% efficiency. Meanwhile, designs already exist to take take advantage of nano-engineering and shave the cost per watt of solar cells to a tenth of their current level.
As solar power has been getting cheaper and more refined by the year, oil costs have been going up. It still isn’t to the point at which solar power as cost efficient as traditional methods, but the trend is definitely in that direction. In some areas in which power companies pay a premium on energy sold back to them from residential customers who generate their own solar power, the adaption of this technology has been dramatic.
Last year, global solar power spending topped fifty billion dollars, with Germany and China leading the way forward. Each country spent over ten billion dollars on solar power, and saw dramatic increases in deployment, far ahead of what their governments had expected. Germany leads all countries in solar power generation:
” There are now more than 300,000 photovoltaic systems in Germany — the energy law had planned for 100,000.
Spread out across the country, they are owned by legions of homeowners, farmers and small businesses who are capitalising on the government-backed march into renewable energy.
By tapping the daylight for electricity — which power companies are obliged to buy for 20 years at more than triple market prices — they are at the vanguard of a grassroots movement in the fight against climate change. “
China is becoming both a top user and maker of the technology:
“The technological prowess of China is growing a lot faster than people in the West reckon,” said Andrew Wilkinson, co-manager of a fund at the investment bank CLSA Emerging Markets that invests in Asian clean-energy industries.
Suntech’s 3,500-strong work force at four sites in China produces photovoltaic cells, the delicate, hand-sized black silicon panels that can transform sunlight into electricity.
At a time when China’s Communist leaders are trying to turn lumbering state companies into nimble global competitors, Suntech already goes head-to-head with Japanese and European rivals in foreign markets. Shi says that all of Suntech’s technology comes from its own labs.
Interestingly, China is also undertaking an ambitious project to spread the use of solar power in Africa. They’re both training technicians and investing in joint-ventures in undeveloped countries.
[BEIJING] Chinese scientists are to train 10,000 technicians from African and other developing countries in the use of solar energy technologies over the next five years.
Describing the plans, Xi Wenhua, director of both the Institute of Natural Energy (INE) and the China Solar Energy Information Centre, told SciDev.Net the training will include programmes on small-scale solar power generation and solar-powered heating and irrigation.
Using funding from the central and provincial governments, the INE — part of the Gansu Provincial Academy of Sciences — has established an eight-hectare training facility powered entirely by solar power. The facility, which is the largest in Asia, has trained more than 400 people from 70 countries in Africa, Asia and Latin America since 1991.
Raymond Kurzweil’s prediction that by 2030 we’ll be able most of our projected energy costs at that time through solar power still sounds bold. I sure wouldn’t want to bet against him, though. He’s the guy who predicted both Deep Thought’s defeat of Gary Kasparov and the mapping of the human genome 15 years before they happened.