There was an episode of Brooklyn 99 that involved a riddle: there are 12 men on an island, one is slightly heavier or lighter than the others, there are no scales but there is a see-saw, and you can only use it three times. Who's the odd guy?
I had never heard of Brooklyn 99, but someone at work asked me that riddle, so I scribbled some and thought I had an answer. Though it had lots of fiddly details. Then I looked at it closer then realized, hey, this is actually an answer for 13 guys on an island, not just 12. And it answered whether each guy was heavier or lighter as well, which the original question hadn't asked. Maybe I made a mistake? Usually riddles like this are as hard as they can be.
Each measurement with the see-saw gives one of three answers: heavier, lighter, or equal. There are three measurements, so there are at most 3*3*3=27 outcomes. If the outcome also tells you whether the guy is heavier or lighter, for n guys that's 2n outcomes. 2*13=26 which might work, but 2*14=28 which will not. But, the question didn't ask whether they were heavier or lighter. If you just have to identify the person, that might work for up to 27 guys. Is there an answer for 14? I didn't know. I wrote a computer program to find out.
The program has two classes: Dice and Island. Island takes a possible scheme for doing three measurements with a see-saw and tests whether it works for each of the guys being the odd one, either heavier or lighter. Dice calls Island with all possible ways of doing those three measurements. It's actually 13 possible measurements: 1 first measurement, 3 second measurements depending on the answer to the first measurement, and 9 third measurements depending on the answers to the first two measurements. 1+3+9=13. The program has to fill in how to make all 13 possible measurements. Dice actually constructs pieces of the measurements as Island uses them, and Island can quit early, and all the combinations for later choices don't need to be considered. How long the program takes is exponential in the number of choices to be considered. The trick to making the program fast is to quit as early as possible.
As measurements go on, guys are in four classes: unknown, not light, not heavy, or equal (both not light and not heavy). Each guy in each measurement might learn if they are not heavy or not light. A measure is unequal if and only if the odd guy is one one side. If a measure shows the left side is heavier, then the left guys are not light, the right guys are not heavy, and the unmeasured guys are equal. If there was a known not heavy guy on the left and the left was heavier, now you also know that guy is not light, so he's equal. If a measure shows the left and right are equal, all guys on the left and right are equal and the unmeasured guys don't change. Choosing a measurement means choosing how many unknown, not heavy, not light, equal guys to put on each side. If you have an equal number of guys on each side (oppositely paired so that each pair is seated an equal distance from the middle), the see-saw will balance if they are all equal, and show the left is heavier only if the odd guy is heavy and on the left or lighter and on the right.
Measurements only leave unknown guys if the measure came out equal, showing the odd guy wasn't measured. There's only one combination that is all equals, namely = = =, so you can prove at most 1 guy is odd using that trick. 14 guys needs 13*2+1=27 outcomes, which might be feasible. But 15 would need 12*2+3=27, would need to distinguish between 3 unmeasured guys. So 15 guys shouldn't be possible. Further, after 1 measurement there can be at most 9 possible odd guys, after 2 measurements at most 3 possible odd guys, and after 3 measurements exactly 1 possible odd guy. For example, if there are 12 guys and you measure 1 guy on each side for the first measurement and they come out equal, that leaves 10 possible guys, 10 > 9, which rules out having only 1 on each side for the first measurement.
If a measurement needs 2 not-light guys on the left and 2 not-light ones on the right, which ones do you pick? It doesn't matter. So, number all guys 1 to n and go through them in order, putting them on the left and right until there are enough from each class on each side. I have the program pick the number on each side, then the number in each class on each side. When picking the number for a class, you can't pick so many that you'd have too many on that side, and you also can't pick so few that there aren't enough possible guys in the remaining classes to fill up both sides. Constraining the range to pick from that way makes the program faster. If there are equal guys on both sides of a measure, that's pointless, you could do the same measure simpler if you removed equal guys from both sides until at least one side had no equal guys, so also require at least one side to have 0 equal guys.
Since guys are placed 1..n, the early guys are measured most often, so the nth guy is the hardest for all the choices to get right. So, when testing choices, first test the nth guy being the odd one (both heavier and lighter), then the n-1th, and so forth.
The Dice class is fun. It lets Island calls Dice::Choose(n), and it returns 0..n-1. If Island calls Choose(n) m times, then Dice calls Island nm times with all combinations of answers to all those Choose(n). As long as Island is deterministic given the choices already made, it doesn't matter if all the n are the same, or if sometimes Choose(n) is called more times than others. Essentially Dice keeps a counter, and uses a few bits of that counter for the answer to each call to Choose(), and increments it by the appropriate amount based on what the last call to Choose() was.
That's it. So, is it possible to do 14 guys? No. Is it possible to do 13? Yes, 48020 ways. Here's a sample answer. 0: is the first measure, 1: is the second if 0: had left heavier, 2: is equal, 3: is left lighter, 4: is if 1: had left heavier, 7: is if 2: had left heavier, 10: is if 3: had left heavier. The first four numbers are the number of (unknown, not light, not heavy, equal) guys on the left, the next four are for the right.
0 : 4 0 0 0 4 0 0 0 1 : 0 0 2 1 0 1 2 0 2 : 1 0 0 1 2 0 0 0 3 : 0 0 2 1 0 1 2 0 4 : 0 0 0 1 0 0 1 0 5 : 0 1 0 0 0 1 0 0 6 : 0 0 0 2 0 1 1 0 7 : 0 0 1 0 0 0 1 0 8 : 0 0 0 1 1 0 0 0 9 : 0 1 0 0 0 1 0 0 10: 0 0 1 0 0 0 1 0 11: 0 1 0 0 0 1 0 0 12: 0 0 0 2 0 1 1 0 |
But wait. A see-saw is a LEVER. If you put 5 guys at distance 4, and 4 guys at distance 5, they should balance. So you don't need to have an equal number of guys on each side. What if you allow an unequal number of guys on each side? Can you do 14 guys then? Yes! How about 15? No. Here's a sample answer for 14.
0 : 5 0 0 0 4 0 0 0 1 : 0 1 2 0 0 1 2 0 2 : 2 0 0 0 1 0 0 1 3 : 0 1 2 0 0 1 2 0 4 : 0 0 1 0 0 0 1 0 5 : 0 1 0 0 0 1 0 0 6 : 0 0 1 0 0 0 1 0 7 : 0 1 0 0 0 1 0 0 8 : 0 0 0 1 1 0 0 0 9 : 0 0 1 0 0 0 1 0 10: 0 0 1 0 0 0 1 0 11: 0 1 0 0 0 1 0 0 12: 0 0 1 0 0 0 1 0 |
Here's the program: guy.cpp, compile it g++ -O3 guy.cpp -o guy, run it guy.exe, it is looking for solutions to 14 guys where side can be unequal. It finds 5443011 of them. It has the Dice class in C++, which is useful for lots of things.
Now, how a human would find these solutions on their own by just thinking about it in their own head, I don't know. I haven't given it any thought.
Code for least squares linear regression analysis
Ye Olde Catalogue of Boy Scout Skits
A dollhouse bookshelf
Table of Contents