This week's puzzle is about a perplexing pedigree. Can you untangle its twisted lines of descent?
Sunday Puzzle #6: The Riddle Of The Six-Grave Plot (aka "Lichtenberg's" Riddle)
While ambling about your local cemetery, you stumble upon a grave marker situated before a six-grave plot. Glancing down, you notice an inscription upon the family stone. It reads:
Here lie...
2 Grandmothers with their 2 Granddaughters
2 Husbands with their 2 Wives
2 Fathers with their 2 Daughters
2 Mothers with their 2 Sons
2 Maidens with their 2 Mothers
2 Sisters with their 2 Brothers...
Yet but 6 corpses all lie buried here,
All born legitimate, from incest clear.
How is this possible?
This week's puzzle was submitted by reader Phil Winkelman, who came across it in The Waste Books, a collection of notes and aphorisms compiled by 18C German polymath Georg Christoph Lichtenberg. According to Winkelman, Lichtenberg got the riddle from "someone else," so it's difficult to say how long it's been around:
Lichtenberg later refers to it being "in the Taschen-Kalender for 1792" — and this publication can be found online (http://ds.ub.uni-bielefeld.de/viewer/image/2…) — but this seems to have been edited in part by Lichtenberg, so my belief is that this is not where he got it, but rather where he passed it on.
This puzzle took me some time to figure out. I highly recommend using pencil and paper, and encourage you to upload any diagrams you create in the process of puzzling.
We'll be back next week with the solution – and a new puzzle! Got a great brainteaser, original or otherwise, that you'd like to see featured? E-mail me with your recommendations. (Be sure to include "Sunday Puzzle" in the subject line.)
Art by Tara Jacoby
SOLUTION to Sunday Puzzle #5: 23 Prisoners, 2 Switches
Last week, I asked you to devise a way to free yourself and 22 of your fellow prisoners from incarceration with the aid of two defunct light switches, lest the whole lot of you perish.
Let me preface this by saying you all rock. I've always thought highly of io9's commenters, but the level of communication I've seen you all engage in on the Sunday Puzzles these past few weeks has been, I think, especially noteworthy.
Take last week's puzzle, for example. This was a tough logic puzzle, but within an hour of posting, hawkingdo had proposed a solution that, while incomplete, would provide the foundation for a back-and-forth between himself and several other commenters that eventually resulted in a correct solution, arrived at more-or-less jointly by transitnap and Gabe47.
From a metacognitive standpoint, the thread initiated by hawkingdo is fascinating; reading through the whole thing is a little like watching a thought-process unfold before your eyes. It's also a little messy (thought processes often are, which is why it can be enormously helpful to document one's problem solving progress and plans of attack on a spreadsheet – or, better yet, in a notebook), so I've presented a cleaner version of the solution below.
Solution
The key to solving this puzzle is to 1) Find a way for prisoners to convey that they have visited the switch room, and 2) Assign a single prisoner the task of tallying everyone's visits. We'll call the tally-keeper The Counter. All 23 prisoners must agree ahead of time that The Counter is the only one who will state that all prisoners have visited the switch room.
The prisoners have two switches at their disposal. We'll call them switch A and switch B. To convey information, the prisoners agree ahead of time that switch A will be the "flag switch," and switch B will be the "sham switch." The Counter can only turn switch A OFF, and the other prisoners can only turn it ON. By this method, switch A being in the ON state can be used to signal that a prisoner has visited the switch room, and is the switch The Counter will reference to keep track of the other prisoners' visits.
INSTRUCTIONS FOR EVERY PRISONER BESIDES THE COUNTER
You must maintain an individual tally of the number of times you have flipped switch A to the ON position. This tally will start at 0. Your actions will depend on the state of switch A and the number of times you have switched it ON.
If, when you enter the switch room, switch A is in the OFF position, you must flip it to the ON position if and only if the number of times you have turned switch A to the ON position is either 0 or 1. Upon flipping the switch, increment your individual tally. If switch A is already in the ON position, or if you have already flipped switch A to the ON position twice before, you are to flip switch B, regardless of its position. (Remember, switch B is the sham switch. It conveys no information. Rather, it is used to avoid confounding the signaling abilities of switch A.) In this way, it can be assured that, given enough time, every prisoner will flip switch A to the on position twice, and only twice.
INSTRUCTIONS FOR THE COUNTER
If you are The Counter, you also maintain a tally. That tally starts at 0, and is equal to the total number of times you flip switch A to the OFF position. (Remember: You, The Counter, are only permitted to flip switch A OFF; you are never permitted to flip switch A ON.) Your actions will depend on the state of switch A and then number of times you have switched it OFF.
If, when you enter the switch room, switch A is in the OFF position, you are to flip switch B, regardless of its position. If, when you enter the switch room, switch A is in the ON position, you are to flip switch A to the OFF position, and increment your tally. When your tally reaches 44, you are to announce to the warden that ever prisoner has visited the switch room at least once. (Having each prisoner flip switch A twice and only twice solves the "unknown initial state" problem; i.e. If, on her first visit, The Counter finds switch A in the ON position, having the prisoners flip the switch two times means she no longer has to worry about whether switch A started in the ON position, or was flipped by another prisoner, who entered the room before her.)
As hawkingdo noted in his original (albeit incomplete) solution: This will take a while, but it does ensure the prisoners will get out alive – eventually.
Considerations
I. Identifying the Switches
There was some confusion this week over the matter of how the prisoners are supposed to assign identities to the switches. While this was not originally intended to be a part of the riddle, reader David Bautista provides several ways of approaching the problem:
I don't think the switch location was given. Due to the complexity of the switch location, I guess it just has to be assumed that the prisoners will be able to easily distinguish and agree upon which switch the important switch is.
- They could say which ever switch is closest to the door is the important switch.
- However if seem to be at an equal distance to the door, then whichever switch is closest to the ground is the important switch.
- However if both switches are equal distance to door and on the ground, then the switch to the right when the prisoner is facing the direction he/she came in.
- I understand it can get more complex like what if there is more than 1 entrance and the warden brings them in at random entrances, etc. If that is the case than it's another puzzle in itself. So it should be safe to assume that the prisoners can distinguish which is the important switch.
- For a better understanding we can say switch A is the important switch and switch B is the not important switch.
II. Problematic Phrasing
In the thread initiated by hawkingdo, reader holdencash correctly identified a problem in the original phrasing of the riddle, which states that "given enough time, everyone will eventually visit the switch room as many times as everyone else." By this phrasing, the warden could bring everyone to the switch room one time and one time only. Alternatively, he could bring everyone to the switch room 100 time and 100 times only – but if the first 2200 visits are all by people OTHER THAN THE COUNTER, then The Counter has no way of counting anything.
Most of us took it on good faith that the warden would keep bringing prisoners to the switch room indefinitely, but holdencash is technically correct (the best kind of correct, we all know). A better way to phrase that section of the riddle would be to state that the warden will continue to select prisoners indefinitely, and select them with equal probability.
III. Alternate Solutions
There is more than one way to solve this riddle. I've even encountered a couple that do not require The Counter to tally 44 switches. One such solution that I find particularly elegant is documented by Berkeley researcher John Bethencourt:
Appoint one prisoner to be special; call her the 'tally-keeper'. Then each prisoner should have the following behavior:
Non-tally-keeper
Each of these prisoners can be in three states: 'waiting', 'ready', and 'done'. They start out in the waiting state. The first time they enter the switch room, they observe the position of the left switch and switch the right switch. Their action on subsequent visits depends on their state. If they are in the waiting state, they check to see if the left switch is in a different position than it was when they were last there. If not, they switch the right switch and leave. If so, they enter the ready state. Then if the left switch is up, they switch it down and enter the done state, otherwise, they switch the right switch. If they are in the ready state when they enter the room, then if the left switch is up, they switch it down and enter the done state, otherwise, they switch the right switch. If they are in the done state, they always switch the right switch. These prisoners never say that all the prisoners have entered the switch room.
Tally-keeper
The tally-keeper should keep a 'personal count'. This count should start at zero. The first time they enter the switch room, they observe the position of the left switch and switch the left switch. On subsequent visits, they check whether the left switch is in a different position than it was when they were last there. If so, they increment their count. In either case, they switch the left switch.
This strategy does in fact guarantee that the prisoners will not be fed to the alligators and that, with probability one, they will be set free after a finite amount of time.
I've checked this a couple of times now and it seems to hold up.
IV. How Long Are The Prisoners Incarcerated?
Bethencourt created a perl script to simulate how long it would take for the prisoners to be freed. According to his calculations, the 44-count strategy documented above would require an average of 1,125 total switch room visits. The alternative solution presented in Consideration III, however, requires an average of just 715 visits. Assuming the warden has prisoners visit the switch room room an average of once per day, the two strategies would result in roughly three years and two years of imprisonment, respectively.