(Update: Meme Warning - Einstein has not been shown to have written this problem. Please see Part 2 for a further explanation)
I like to do mathematics and logic problems for fun. There are different classes of problems that I find interesting. If you look in the magazine racks at your local newsstand, you'll see crossword and other puzzle books. When I need some mental golf, i.e. I don't really want to think about math or other stuff, I grab a copy of one of these babies. Most of these puzzles are simply the recognition of simple patterns in a one-person game (no, not game theory) with the application of a set of simple rules for the solution.
I bumped into Einstein's Riddle the other day. Einstein's Riddle is a puzzle that Albert Einstein wrote way back before I was born. The problem was formulated as a "Logic Puzzle" in the form of those I mentioned in the above books. Einstein felt that only 2% of the people in the world could solve this puzzle. Perhaps in his day this was the case, but puzzles of this nature are commonplace in puzzle books in your local grocery stores. Having done a few of these puzzles in my day (my Mom would usually "borrow" these books when I visited her and Dad on vacation in Florida), I would rate Einstein's Riddle a three on a scale of one to five. It is somewhat difficult, i.e. beginners may find it a little difficult, but advanced puzzlers would likely complete it in under an hour (I can hear some now; 20 minutes baby!).
Thanks to Turing, Post, Church, Kleene, Blum and many others throughout the twentieth century, we have many disciplines including The Theory of Computation (TOC) and Computational Complexity (CC). These great explorers of mathematics, logic and the emerging disciplines of TOC and CC are the reason that you and I and everyone who is involved with computers have a profession in which to earn a living. Many of these names and the associated disciplines are still in their infancy, but have matured to a point in which I believe Einstein would be proud to witness. While there is much to learn in these disciplines, there are many great results that contribute to the common knowledge to solve problems of this nature as a pastime. How times change!
I've published a short article and an exhibit in the form of an Excel spreadsheet to demonstrate Einstein's Riddle and a simple approach to solving this problem. You can use the empty grid worksheet as a template to solve the problem on your own if you would like. I also only give the answer in the last few worksheets of the Excel workbook. I really don't go into the details of the techniques and details for solving the problem, but rather the approach to the problem. There are opportunities for a measure of complexity of this class of problems, but I'm trying to be friendly today and have just shown some of the basics rather than get into theory.
----
Updated: I mistakenly had the wrong percentage listed as "Einstein felt that only 98% . . ." and now reads "Einstein felt that only 2% . . .". Thanks to The Armed Geometer.
----
Contact me here if you have a comment.