Liars, Truth Tellers, and Random Answers
By John P. Robertson
This is another puzzle from Peter Winkler. You are at a fork in the road, and you want to know which of two roads leads to the village. There are three natives present, one who always tells the truth, one who always lies, and one who answers at random, but you don’t know who is who. How can you ask two yes-or-no questions, with each question addressed to one native, and determine which road leads to the village? It’s not fair to ask, ``Did you hear they are giving away free beer in the village?’’ and follow them to the village.
The problem involved cutting a white cake with chocolate frosting and flipping the pieces over. You fix an angle ?, successively make cuts of that angle, flip each piece cut over in place, and cut the next piece adjacent to the one you just flipped. We asked how many cuts and flips it took before the top of the cake was all chocolate again if ? were 181 degrees, and if ? were one radian (180/? degrees).
Dave Oakden said he found the solution quite surprising (as did I!) and wrote: “The key to the solution is that when you go around the cake for the second time the cut lines from your first time around are flipped and become the cut lines for the third time around. In general if the angle A is such that n • A is less than 360 degrees and (n+1) • A is greater than 360 degrees then the cake can be divided into 2 • n + 1 pieces that change position but remain in the same order. Each cut consists of flipping and reversing two adjacent pieces. It is fairly easy to demonstrate that after 2 • n • (n + 1) cuts you will be back to your starting point.
“To answer the questions you posed:
Frank Chang submitted a solution to the puzzlement for ? equal to 181 degrees, and David Uhland submitted solutions for both angles.
- For an angle of 181 degrees, n = 1 and four cuts will return the cake to its original chocolate up position.
- For an angle of one radian, n = 6 and it will take 84 cuts.
Additional Solvers for a Previous Puzzlement
Charles Stimler, Dave Westerberg, and Lili Xu solved the puzzle from last November.