Three cryptographers are having dinner at their favorite restaurant. The waiter informs them that arrangements have been made for their bill to be paid anonymously. It may be that the National Security Agency has picked up the tab, or it may be that one of the cryptographers himself has done so. The cryptographers respect each other’s right to pay the bill anonymously, but they want to know whether the NSA is paying. Happily, there is a way to determine this without forcing a generous cryptographer to reveal himself.

Each cryptographer flips a fair coin behind a menu between himself and his right-hand neighbor, so that only the two of them can see the outcome. Then each cryptographer announces aloud whether the two coins he can see — one to his right and one to his left — had the same outcome or different outcomes. If one of the cryptographers is the payer, he states the opposite of what he sees. If an even number of cryptographers say that they saw different outcomes, then the NSA paid; if an odd number say so, then one of the cryptographers paid the bill, but his anonymity is protected.

Computer scientist David Chaum offered this example in 1988 as the basis for an anonymous communication network; these networks are often referred to as DC-nets (for “dining cryptographers”).

(David Chaum, “The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability,” Journal of Cryptology 1:1 [1988], 65-75.)

You have 12 coins that appear identical. Eleven have the same weight, but one is either heavier or lighter than the others. How can you identify it, and determine whether it’s heavy or light, in just three weighings in a balance scale?

This is a classic puzzle, but in 1992 Washington State University mathematician Calvin T. Long found a solution “that appears little short of magic.” Number the coins 1 to 12 and make three weighings:

First weighing: 1 3 5 7 vs. 2 4 6 8
Second weighing: 1 6 8 11 vs. 2 7 9 10
Third weighing: 2 3 8 12 vs. 5 6 9 11

To solve the problem, note the result of each weighing and assemble a three-digit numeral in base 3 as follows:

Left pan sinks: 2
Right pan sinks: 0
Balance: 1

For example, if coin 7 is light, that produces the number 021 in base 3. Now converting that to base 10 gives 7, the number of the odd coin, and an examination of the weighings shows that it must be light. Another example: If coin 2 is heavy, then we get 002 in base 3, which is 2 in base 10. Note that it’s possible to get an answer that’s higher than 12, e.g. when coin 7 is heavy — in that case subtract the base-10 answer you get from 26.

Another curious method to solve the classic puzzle, this one involving verbal mnemonics, appeared in Eureka in 1950.

(Calvin T. Long, “Magic in Base 3,” Mathematical Gazette 76:477 [November 1992], 371-376.)

09/30/2018 UPDATE: Due to an error in the original paper, the weighings I originally specified don’t work in every case — in the third weighing, the left pan should contain 2 3 8 12, not 1 2 8 12. I’ve amended this in the post above; everything should work now. Sorry for the error; thanks to everyone who wrote in.

A neat observation by Japanese mathematician Jun Maekawa: If an origami model can be flattened without damage, then at any vertex (meeting of edges) in its crease pattern the number of “valley” folds and “mountain” folds always differ by two.

The single-vertex crease pattern above has five mountain folds (folds whose outer surface is colored) and three valley folds (folds whose inner surface is colored). (The fifth mountain fold is a bit hard to notice in this example — it’s folded flat at bottom right.)

One consequence of this is that every vertex has an even number of creases, and therefore that the regions between the creases can be colored with two colors.

Paper folder Toshikazu Kawasaki found a related theorem: At any vertex, the sum of all the odd angles is 180 degrees (and likewise the even).