We are going to interview some students tomorrow for a position in my lab, so I was reading about brainteasers in preparation (and also because they are fun). The switches puzzle is really cool. Reading it, I got pretty discouraged, but I really like the answer. I definitely started off with a lot of unnecessary assumptions. You can read the answer, but I suggest you give it a try first. Also, note that the answer is suboptimal—it can be done more efficiently. Anybody know how?
However, the bad king problem can go fuck itself. I can’t believe how convoluted the answer they give is—totally insane. There is a dirt simple, brain-dead solution (anybody else see it?).
The article through which I discovered most of these puzzles is a review of “Moving Mount Fuji”, which is sometimes interesting and other times ridiculous. For example, I find his solution to the piano tuners question to be horrifyingly complex and error-prone. I would need to have a serious discussion with anyone who came up with that solution to make sure he wasn’t a complexifier. :-P
There are also a bunch more such interesting puzzles at [wu:riddles]. And this page is hilarious.
“Any complex problem has a simple solution … usually the wrong one.”
—H.L. Mencken