Are you a good problem solver? Try to figure out what’s behind these riddles and write your answer in the comments section.
1. A group of prisoners are trapped in a forcefield. These prisoners are perfectly brave, meaning that they would attempt an escape on any positive probability of success. The prisoners are monitored by a guard who has only one bullet in his gun, but who also has perfect marksmanship skills (he never misses). A maintenance technician needs to tune up the forcefield generator, and so for one second, the forcefield is released. How can the guard still keep all the prisoners detained?
2. You have 12 identical-looking balls. One of these balls has a different weight from all the others. You also have a two-pan balance for comparing weights. Using the balance in the smallest number of times possible, determine which ball has the unique weight, and also determine whether it is heavier or lighter than the others.
3. A thousand wires hang on a very high tower, so high that you cannot see what tip belongs with what bottom. This is something you are interested in knowing. You have a battery and a light bulb which will light up if two wires connect it to the battery with appropriate polarity (i.e. the battery and bulb each have two contact points, and one of each is + and the other side is -). Wires may be tied together to form longer wires, and you can see the bulb light up even if you are on the opposite side of the tower. Since the tower is so high, you want to minimize the number of times you have to climb up and/or down the staircase, regardless of how much you have to do while you are at the top or bottom. What is the minimum number of traversals required?
Assuming that the guard knows the prisoners will leave on P > 0 and that the prisoners know the guard never misses, he simply announces that the first person to escape dies. P = 0, so the first guy doesn’t cross. (in the event that two try to cross at the same time, he’ll shoot the closest one, so that no one will be the closest.)
I like the 1st part, but maybe because it’s exam week, I’m not convinced of the second.
Someone might not be closest, but, theoretically, they could be exactly the same distance away. In which case P=0.5. An escape attempt is made.
Well, if the prisoners are social and honest, they’d agree to escape together and draw lots as to who goes first. Before the drawing, if there are k prisoners, the chance of escape is (k-1)/k, so everone will agree to this scheme (we can stipulate that the loser of the draw will be killed by the other inmates then and there if he refuses), and therefore all but one prisoners will escape because the guard only shoots the first (or nearest) one.
Name the three prisoners A, B and C. Then, impose three rules:
– The first one trying to escape will be shot.
– If prisoner A tries to escape at the same time as B or C, A will be shot.
– If prisoner B tries to escape at the same time as C, B will be shot.
Since A knows for sure that it will be shot if he tries to escape, he will not try to escape. Since A will not try to escape, B (and then C) will also not do the same.
matheusgr’s method will not work if
* the prisoners can make themselves indistinguishable
* prisoner A sacrifices himself for the good of the whole
* a smart prisoner talks the other ones into an escape attempt like this:
Assign each prisoner a probability, which is lower nearer the front of the guard’s “hit list”; so much so that prisoner A’s probability is practically zero. Then institute the rule that each prisoner is to attempt an escape with the probability they’ve been assigned; they are to determine this secretly (“so the guard can’t know”). A few “dry runs” should demonstrate to everyone that different prisoners get killed on different attempts (there is no certainty to die), and different ones escape. Prisoner A will see that he doesn’t have to escape and get shot. One of them will have the lowest letter to have gotten shot in the dry runs and never completed an escape, but will figure that he just got unlucky that nobody lower lettered attempted an escape on that particular run. There will probably be several people who never escaped during one of the dry runs, and most of them clearly got “unlucky” on that one.
If that psychology works well enough, some prisoners will escape even matheusgr’s guard.
Solution: The guard simply locks the door. 🙂
For the second riddle, I know that the 9-ball version can be solved in 3 weighings, and there’s an easy 4-weighing-solution for the 12-ball version.
A weighing can have 3 outcomes () and so reveals log_2(3)=1.58 bits of information. To pick one ball out of 12 is log_2(12)=3.58 bits of information, and we also require one additional bit for the knowledge whether the odd ball is heavy or light. Thus, it seems that a 3-weighing strategy might be possible here as well.
I figured out the solution for the 12-ball weighings.
1) Set apart 4 balls (group A). Weigh the other balls, 4 to each pan.
2a) If weighing 1) comes up equal, all balls on the scale must be standard, and the oddball is in group A. Take 3 balls from group A and weigh them against 3 standard balls.
3a) If weighing 2a comes up equal, the oddball is the 4th ball from group A that has not been weighed. Weigh it against a standard ball to find out if it is heavy or light.
3b) If weighing 2a comes up heavy for the group A pan, the oddball is heavy, otherwise it is light, and it is on that pan. Pick two group A balls from that pan and weigh them – the heavy/light one is the oddball, if they’re equal, it’s the one you didn’t pick.
2b) If the first weighing came up unequal, call the balls on the heavy pan group H and the balls on the light pan group L. Group A is now known to contain standard balls. Pick 3 balls from group H and 1 ball from group L and weigh them against 3 balls from group A and the remaining ball from group H. Weigh two of these 3 balls against each other two find out which one’s the light one; if they’re equal, it’s the one you didn’t weigh.
3c) If 2b) came up equal, the oddball is in the the 3 remaining balls of group L. Weigh two of them aginst each other to find the light one among the 3.
3d) If 2b) was light on the pan with the group L ball, either this ball or the group H ball on the other pan is the oddball. Weigh one of them against a group A ball to find out which.
3e) If 2b) was heavy on the pan with the 3 group H balls, the oddball is one of those. Weigh two of those against each other to find the heavy one among the three.
Done!
Editing error: Strike “Weigh two of these 3 balls against each other two find out which one’s the light one; if they’re equal, it’s the one you didn’t weigh.” from 2b).
The easy answer to riddle number 3 is 10, but it can actually be done in two traversals, though that will likely take longer than climbing up and down the tower a few times (unless the tower is really a space elevator or some such or you have testing equipment that carries out the algorithm), because my first test is going to find the two wires that I have hooked up to the lamp at the other end, which requires almost half a million tests on average (I think it “only” takes around half a million more tests until I’m finally done, which compares badly to the ten-thousand tests needed for the ten traversal solution).
3. Connect all bottoms in pairs, take one wire and make a knot, climb tower with lamp, connect all wires to a long chain, observe lamp when connecting the battery for the light up-time, id est the inductive response, to find out the internal order, the wire with the lowest induction is the one with the knot. Climb down with lamp, do the same at the bottom.
1) The only way to make sure that none of the prisoners cross the force field is for the the force field not to go down. Therefore the 1 bullet must be used on the Technician.
I’ll read the next two tomorrow
I have a marvelous proof of puzzle two but it won’t fit in the margin.
Actually, I typed in a semi-lenghty response narrowing it down a bit, but in my haste to submit, I messed up the password, and upon being instructed to back-click, the text box was empty.
tl/dr: yeah, I know it’s three. I don’t remember exactly how. Four is trivial, so it has to be three.
Shoot the technician