Narrowing by logic, choosing by stopping

Squeeze out the one right answer from clues. Or decide, with too little information, when to stop. The three works here are games of thinking and deciding.

A grid of clues (the site’s “Logic Grid”)

You read clues such as “Ann is not in the red house” or “the cat owner lives next to the blue house”, fill in a grid, and settle who goes with what. The program checked that all 36 puzzles have exactly one solution. Every puzzle can also be solved by clues plus the rule of “only one per row”, with no guessing (logic-grid/engine.test.ts).

The best-known puzzle of this kind is called “Einstein’s riddle”. But there is no evidence that Einstein made it, and the same goes for the theory that Lewis Carroll did. What is known is that this form of puzzle appeared in a magazine issue of 17 December 1962, with the solution printed on 25 March 1963.

Knights and knaves (the site’s “Knights and Knaves”)

On an island live knights, who always tell the truth, and knaves, who always lie. Three people each say something. Who is a knight and who is a knave? Each person is a knight or a knave, so there are 2×2×2 = 8 cases. Check them one by one against what was said and an answer comes out. The program checked that in all 68 puzzles exactly one of the eight cases is consistent. Every puzzle has three speakers and uses at least two types of statement (knights-knaves/engine.test.ts).

The name “knights and knaves” was popularised by Raymond Smullyan’s 1978 book. Similar puzzles came earlier, among them one in Kraitchik’s 1953 book and one that Nelson Goodman put in a newspaper in 1931. At the root lies the liar paradox: a person who says “I am a liar” is in trouble whether telling the truth or lying.

Choosing by stopping (the site’s “Secretary Problem”)

Applicants come one at a time, and you must accept or reject each on the spot. Someone you turn down cannot be called back. How do you pick the best? The best strategy is to let the first n/e applicants pass (e is about 2.718), then take the first one who is better than everybody so far. With many applicants, the chance of success approaches 1/e, about 0.368. It is sometimes called the 37% rule.

The program checked that with 20 applicants the best number to skip is 7, with a success rate of about 0.384, and that for large numbers the rate comes close to 1/e. It also checked that the formula for the success rate agrees with trying every order, up to seven applicants (secretary-problem/engine.test.ts).

As for history, Merrill Flood is said to have talked about it around 1949 as the “fiancée problem”, without publishing. The first appearance in print was Martin Gardner’s February 1960 column. Several people solved it, including Lindley in a 1961 paper, and who was first is disputed (Ferguson’s 1989 paper discusses the dispute). We do not decide it here.

What they share

• Find the contradiction: cross out, one by one, the cases that clash with the clues.
• Check there is just one answer: a good puzzle has exactly one.
• Decide before choices run out: the secretary problem is practice in deciding by a rule when information is incomplete.

The puzzles in all three are made for this site. “Einstein’s riddle” itself is not reproduced.