Logic Puzzle Two
Logic Puzzle TwoNot really a logic puzzle, but a challenge to devise a strategy.
100 lawyers are about to be buried up to their necks in sand, all facing down the line. Then I'm going to come along from behind and place on each head a hat, either red or blue. Starting with the rearmost lawyer, each lawyer will say out loud just "red" or "blue". If they say the colour of their hat then they will, eventually, be released. Otherwise, they will be left until the tide comes in.
They can discuss beforehand what their strategy will be. I can listen to their discussion and then choose what hats to place on what heads.
What strategy should they choose to give the greatest expected number of rescues?
Can the buried lawyers wait until all the hats have been placed before calling out "red" or "blue"?
Yes - all hats are placed before the first lawyer, who is the rear-most, has to say something. Otherwise I can provably expect to kill half of them.
Naturally, each lawyer cannot see that lawyer's *own* hat color.
Can the lawyer in the back really see *all* the colors in front, or just the colors of the 2 in front?
Does the second-lawyer-from-the-back really *know* there are exactly 100 lawyers, and that there are 98 lawyers in front and only 1 behind? Or does that lawyer see just enough to tell that there are at least 2 lawyers left to go in front?
Yes, and yes, each person can see all the hats in front of them and they all know that there are 100 of them. You may choose to consider, offer and/or solve such variants.
I can save 100% of the lawyers if and only if #red=50. -- WyattMatthews
You are mistaken. No approach can guarantee to save the first lawyer.
Obligatory: Put green hats on them without telling, fewer lawyers is the optimized solution.
Are these the SixThinkingHats? Or the TwoDrowningHats??
My first thought is maybe TitForTat - each lawyer calls out the hat color he sees immediately in front of him.
But if you knew they were going to do that, you would just alternate red-blue-red-blue-red-blue.
Hmm... Maybe each lawyer looks at *all* the hats in front of him, and calls out whichever hat is the *majority* ...
How does that help him?
OK, we need to start inductively. Though that can be misleading if you don't understand ALL of the assumptions behind your first cases..
Possible optimum strategies (so far):
As it happens, the lawyers were facing away from the incoming tide. The first lawyer realized that since what he would say was determined by the strategy agreed, he was probably doomed to drown. He therefore silently chose the opposite strategy, hoping that this switch would not be anticipated. The second lawyer realized the first might have done this, and so decided to defer saying anything for as long as possible. Fortunately, the first lawyer's bluff worked, and he was released. As he fled (to the nearest court), he made sure the remaining lawyers knew that he had survived, and so would realize that the strategy had been successfully switched. Eventually, all the lawyers survived.
[The reason this entire discussion was stupid was because it got lost in a discussion of strategy and treachery without any established framework within which to discuss them, without ever talking about what kinds of strategies are possible or even whether a strategy is necessary. This is exactly like talking about a spoken language without first establishing what kind of mouth parts are possessed by the species that speaks it. Or what kind of construction techniques to build a house before you've decided what building materials it's possible to use! In fact, this fatal error can be seen in the very first paragraph of this section above when it assumes, falsely, that the first lawyer's survival is connected to a "strategy".]
[So, to flesh out the scenario, I ask:]
[Is there any way for the lawyers to know the success or failure of previous lawyers' responses?]
Starting with the lawyer at the back, they will say out loud just "red" or "blue".
Does this mean that they have two choices, only saying "red" or only saying "blue", or does it mean that their vocabulary is only the words "red" and "blue"? If the latter, each lawyer just says "red blue". Then they have all said the color of their hat.
If they only get to say one of the words, do the lawyers only get to say their chosen word once? If they get to say it as many times as they like, the first lawyer could pick a random color and say it in an encoded fashion. For example, once represents red, and twice represents blue. They then start with the one in front of them and work their way down the line. The first lawyer has a 50% chance of living and all of the others survive.
If they only get to say one of the words, and only once, there are questions of inflection. For example, drawn out means red, and quick means blue. Each lawyer uses this to tell the lawyer in front of them what color their hat is, and the next lawyer uses this information to decide what word to say, and the color of the hat in front of them to decide how to say it. Again, everybody lives but the first lawyer, who has a 50% chance.
I can see you're the kind of person who creates the need for lawyers in the first place. Regardless, they can each say only one word, without inflection, and that word must either be "red" or "blue".
POSSIBLE SPOILERS BELOW .
.
.
.
.
By generalizing the inductive solution above to N, we can set red=1 and blue=0. Every lawyer take the colors he can see and XOR them together, which we will call these results A1, A2, ..., AN. The first lawyer say A1. The 2nd lawyers can deduce the color of his own hat (C2) by comparing A1 and A2, namely, C2 = A1 XOR A2, he says C2. 3rd lawyer deduce C3 = A1 XOR C2 XOR A3. In general CI = A1 XOR C2 XOR ... XOR C(I-1) XOR AI.
So every lawyer except the first will escape, the first will die because you will put the opposite of A1 on his hat.
Ah... but if the first lawyer knows you will put the opposite of A1 on his head, to assure his death, then the first lawyer, naturally looking out for himself, will say the opposite of A1 to save himself. But, knowing that lawyers will be lawyers, maybe you don't put the opposite of A1 on the first layers head, because you anticipate his thinking... but if the first lawyer anticipates that ... and so on... So it really is a 50/50 chance for the first lawyer.
[The first lawyer has a choice: either go with the system they all agreed on, or in a desperate attempt to save himself name the wrong color. In the latter case, all his fellow lawyers are fed wrong information and will call out the wrong color, condemning themselves to certain death. Since the first lawyer is not sure if his cunning plan will save him, you can expect 0.5 lawyers to survive. Alternatively, if the first lawyer sticks to the scheme, 99.5 lawyers will survive. Not knowing whether the first lawyer will stick with the scheme or not, brings the average expected number of saved lawyers back to 50. And I guess this number can not be improved upon with any scheme. In other words, the puzzle is pointless if you allow the first lawyer to cheat the others. Right?]
[If the first lawyer is freed, he has to avoid the incoming tide. Nothing in the original terms prevents the next lawyer hearing the first one being released or seeing him depart. Even without such information, subsequent lawyers can reason that if it's still possible that all will die, they might as well guess at random. Hence the expected survival rate cannot fall below 50%.]
[Hm. Assuming that each lawyer knows which lawyers before him were set free, and what they called out, and assuming that each is free to change his mind about following the agreed strategy: if everyone simply follows the strategy, 99 lawyers will be saved, and the first will have a 50% chance. So far, so good. But, what if the first lawyer changes his mind. He should have called 'red', but instead he calls 'blue'. There is still a 50% chance that he will be set free, so the second lawyer has no information whether or not the first one made the correct call. The second lawyer now has to decide whether the first one has stuck to the strategy. If he trusts his colleague, he will call out the wrong color, and not be allowed to leave. This information is important to the third lawyer, who now knows that the information before him is corrupted. The lawyers may have agreed that in such a case, the chain will start all over again. But of course, the third lawyer now only has a 50% chance of getting freed, no matter what he does. It seems that, moving up in the chain, any lawyer will have a 50% chance of survival, no matter what. This way, no strategy would give a number of expected survivors above 50. However, the lawyers are not stupid (another implicit assumption), so they know that every lawyer before them that is freed increases the chance of an unbroken strategy: a lawyer that does not follow the strategy has a 50% chance of getting freed, yet the chance that n lawyers in a row are freed while the strategy was broken is .5^n. The more lawyers are freed, the greater the trust that the chain is unbroken. Hm, gotta get back to work. However, the puzzle to me now is not the right strategy to follow, but what the number of expected survivors really is. I don't think it's 99.5. It's either 99 if the lawyers are not allowed to break the strategy, (in which case the first one is doomed), or something else otherwise. Any thoughts?]
An extension to this will give the first lawyer a 50% chance. They can all agree to XOR an arbitrary "choice" bit (C0) to all calculations, and that C0 can be chosen by some external signal visible to all lawyers when the first lawyer says his answer. E.g., C0=1 if he says it when a passing cloud blocks the sun. So it lets the first lawyer say either red or blue without compromising the scheme.
Does that really work? I've listened to all they say, and if all lawyers can see the C0 stimulus then so can I. Surely I can still take out the first one at least.
Say, if the agreed definition for C0=1 is "saying his answer when a cloud blocks the sun", and C0=0 otherwise. How can you know if the first lawyer will choose C0=1 or 0? (That is, unless you have a weather report saying "no visible clouds at all for the whole day.")
If I interpret you correctly - which I might not be, I've mis-understood you before - you are suggesting that they use the timing of the first "red" or "blue" to convey more information. That's not allowed. I can prevent that by saying that they have to give their answer when told to, not when they choose to.
You interpret what I say correctly, I am suggesting they use the timing for the first "red" or "blue" to convey more information, which wasn't forbidden in the original puzzle. No, I don't the agree that you can "prevent" that by changing the rules now. There is no point playing a puzzle if the rules can be changed halfway through. OTOH, if you call that a more difficult variant, I can try to see what "side channels" I can find to let the 1st lawyer pick either answer without compromising the scheme (e.g. C0=1 if the frontmost lawyer tilt his head to the left, C0=0 if he tilts to the right).
So, now, how much more precise do you want me to be? It seems that your idea of fun in this game is to try to find all the possible loopholes in the specification and then try to exploit them, and that's fair enough, but it's not mine. I thought my intention was clear, but if you want me to produce a 100 page specification of what they are and are not allowed to do I'll just go away and not play any more.
That's how logic puzzles are played - people try to spot logic loopholes in the question to find solutions to seemingly "impossible" or "difficult" situations (e.g. ever heard of the puzzle about 3 light switches with 3 light bulbs across the house? That answer involves using side-channels also). I suppose your intention is to pose a puzzle to give people a challenge, but now it seems you get offended whenever someone tries to find a way to save the 1st lawyer.
Maybe you are offended because you think people here are playing with you (I don't understand what the other guy a couple sections above is trying to argue, mind you, nor am I the one asking question in the section immediately above), but I am playing against the puzzle itself, pure and simple.
If I am trying to be an ass, I would suggest the lawyers use DH key-exchange algorithm (doing the calculations in their head) and encrypt all their discussion so you will not know their strategy. In fact, given the basic strategy, they just need to securely communicate 1-bit (C0) of information in their discussion.
I'm not offended - I've just come to realize that you ( and possibly others) are playing a different game, and it's simply one that I don't enjoy. I'm trying to be polite and letting you know that no, I don't really care to play that game thank you.
[I'll inject my two bits. The italicized author's intentions have been clear from the first. The puzzle's original definition said that the hat poser gets to listen in on everything the lawyers say. The intention is clearly that there is to be no secure channel of communication. Evidently, the other author decided to introduce a side-channel for secure communication. When the italicized author rejected that proposal, he went on to try to create a different side-channel for secure communication. When it was pointed out that the intention had always been from the very beginning that no secure channel of communication is possible the poster then goes on to whine, impute the italicized poster's motives, claim that only secure channels of communication can solve the problem and then propose yet another secure channel of communication. At that point, I have to ask myself what the proper word is to describe a person of such obvious stubborn stupidity. Any ideas?]
Huh? How is "e.g. C0=1 if the frontmost lawyer tilt his head to the left, C0=0 if he tilts to the right" a secure channel? If I overhear them agreeing to that strategy, and I later observe which way that lawyer tilts his head, I know exactly what the strategy tells that lawyer to say, before the lawyer says it.
If this sort of "additional bit of randomness" can be used for something useful, that would be very interesting - because we can communicate such things at nearly twice the speed of light (using the polarity of entangled photons), much faster than any other kind of communication.
In reference to the "not a logic puzzle" statement at the top... This is indeed more of a "LateralThinking" problem. The first prisoner is of course doomed (unless he knows a priori the distribution of red and blue hats), but the remainder are safe. Think creatively: how can you communicate out-of-band information when speaking the words "red" and "blue"? Can you both identify your hat color but also inform the next prisoner of his hat color?
It might seem that the first is doomed, but it's been admitted that the hat-placer should choose the first lawyer's hat at random, which means the first lawyer has a 50-50 chance of rescue. Also, people have been reluctant to follow through on their ideas - an effective strategy is trivial for a small number of buried lawyers, and with just a little thought can be extended to as many lawyers as you wish.
The first lawyer is not doomed. The solution is trivial and anyone who doesn't see it is a fool. This page is a LOGIC puzzle, not a game theory problem or a word game. Think math damnit! For pete's sake, doesn't anyone here except Wyatt know that logic is a branch of math?
Whether the lawyers' strategy can be overheard is irrelevant.
Something is fishy. Either the strategy is deterministic, in which case the hat on the head of the first lawyer will be chosen to be exactly the opposite color to the colour the strategy requires. Or the strategy is non-deterministic, but my back of the envelope calculations seem to indicate that the survival chances shrink more for the later lawyers than the chances increase for the lawer employing non-deterministic choice (however I'm to lazy to come up with a formal proof). Thus it seems that the author is playing games with us and will probably pull a purple hat out of his pocket...
I believe the purple hat is 'I never said the hat-placer is malicious'. Thus, assuming (!) a uniform distribution of hat-placer intents, on average 50% of the times the first lawyer will get a chance to survive. However, the burden is on the original problem author to prove that the intent of people that engage in burying lawyers in sand in front of impending tide has a uniform random distribution. In other words, the original problem is underspecified and we are wasting our time.
Why on earth would lawyers want to save each other? Couldn't you choose a more altruistic profession? I've heard it before, though, so I'd better not spoil it. -- AndrewCates PS
Presumably, the first lawyer wants to guarantee that 99 lawyers will still be around to sue your butt.
EditText of this page
(last edited May 31, 2006)
or FindPage with title or text search