Thursday, October 11, 2007

Skeptic's Circle #71: Hard

Following are the hard problems for this Skeptic's Circle. Math isn't as much a requirement as for the medium problems, but you'll have to compensate with a ton of advanced logic.

Great Galileo's Ghost

Cranks have always loved to compare themselves to Galileo. Sick of this, one day Greta Christina decided to set them straight once and for all. To do this, she decided to go on a fictional journey to the afterlife to find Galileo himself so he could explain to them why they're acting like idiots. However, when she reached the afterlife, she ran into a little problem.

It seems that one day, Galileo accidentally touched a noodly appendage he shouldn't have, and ended up with a couple clones. On top of this, the three are cursed to always stay together and that if any yes-or-no question is posed to one of the three, they all must answer it. Any other type of question will be ignored by all three. Each of the clones plus the original has a specific curse on them, but it's unknown who has which curse. One of the curses requires the bearer to tell the truth to any question, another curse requires the bearer to lie in response to any question. The third curse causes the bearer to randomly choose between telling the truth and lying before answering each question.

Each of the Galileos knows whether it's the original or a clone, but without knowing which bears which curse, it would be tricky to figure it out. Is there a questioning procedure that would work here?

Now, Greta can't go back to the real world with three mixed-up possible Galileos, but fortunately, there's a way to break the curses. If any of them is ever faced with a question they can't answer (for instance, they're bound to tell the truth for this question, but the question has no truthful answer that doesn't result in a paradox), they'll go "Voip!" and vanish (so sayeth the FSM). If the two clones both vanish, the original Galileo will be freed from all the curses on him. However, he could vanish too if he's asked a question he can't answer, and if he does, it's game over. Is there a way to target out the two clones and make them vanish while keeping Galileo safe?

If you can accomplish that, one further challenge: Can you make both clones vanish with a single question, even if you haven't previously figured out which one is the real Galileo?

Super-Scammer Secrets

Lord Runolfr recently got a couple of e-mails from scammers, raising my suspicions that something big was afoot behind the scenes. I called up a few contacts, did some research, hired a few James Bond-alikes, and here's what I've figured out:

There's some evil mastermind behind the whole plan, and he's about as supervillanous as they come. This of course means that he wants to capture one of my James Bond-alikes and subject him to an intricately detailed explanation of his evil plan before killing him in a creative way. Apparently, the way he's decided to go about this revelation is through an overhead transparencies with the key points of his evil plan (you'd think he'd have better technology than my high school, but he's out to make money, so he saves it where he can).

Now of course, he's wary of this transparency falling into the wrong hands, so he's come up with a plan to keep things safe. He's figured out some method to spread the information across multiple sheets, arranging it so that if we get a hold of any two, we'll still have no idea what he's planning. So, what we need to figure out now is some possible ways he might have done this, so if we manage to get our hands on more than two, we'll know how to read them (if it's not immediately obvious). What are some possible things he could do? Remember that he's out to save money, so splitting it up to have a single word on each slide or something huge like that doesn't seem too likely.

Harebrained Hat Help

Orac reports that the University of Maryland's Shock Trauma center has gone to the dark side, citing how Reiki therapy is now being used to "help" patients. Well, I did some digging of my own, and it turns out this isn't the craziest thing they're doing. They've got something even dumber going on, called "Colored Hat Therapy." Here's how it works:

A bunch of patients are seated in a circle, and a hat is placed on each one's head. They don't know the color of their own hat, but they can see everyone else's hat. There are many colors of hats, but each color present shows up on at least two hats. The patients sit in the room for a while, and every couple of minutes an announcement comes on the PA system, asking anyone who's figured out the color of their own hat to announce it and then leave the room. The theory goes that the magical hat energy must have seeped into their brain, and they're now cured.

Of course, most of the time it doesn't work so well, and people guess incorrectly about their hat color, miss their chance to get it and never figure it out, or get screwed up by inferring wrong things from other people's mistakes. However, one day, purely by chance, everyone brought into the room was an expert at logic puzzles, and they all managed to figure out the colors of their hats. How did they do this?

(Aside: When one of these experts left the room, a nurse noticed that the wound he was suffering from hadn't magically healed, and this therapy was quickly abandoned.)

Singular Sword Slashes

Martin Rundkvist recently uncovered a unique 16th century sword, and he was wondering how many lives it might have taken. Well, I did a little Tardis travel archeology of my own, and I managed to come pretty close to getting the answer before I was discovered and had to flee ran out of funding.

It turns out this sword was used in a ceremonial mass execution. 100 condemned prisoners were brought out and given one last chance at life. They were all stood up in a line and had a hat put on their head, colored either red or blue. No one knew the color of their own hat, but they could see the color of every hat in front of them. If they guessed correctly, they were spared, but if they guessed incorrectly, they were killed on the spot. This particular sword was used for the killings, and it was so fast and efficient that none of the prisoners in front would be able to hear a sound from the death, and so would have no idea if the guess was correct (though they would be able to hear the guess).

Unfortunately, I didn't see the actual procedure, but I did learn two things that might give us a clue as to what happened: First, the prisoners were given a chance to discuss a plan amongst themselves before the ceremony and decide on it. However, the executioner was listening in and would likely set up the hats to thwart the plan as best as possible. The second thing I learned is that these prisoners were all condemned to death for being part of a "dangerous cult" - which was actually more along the lines of Mensa. So, these are pretty smart people, and we could trust them to come up with a pretty good plan.

Putting this all together, what probably happened during the ceremony, and how many lives did the sword take?

Ending Erroneous Expectations

The Sexy Secularist writes in about how he was able to persuade his mother against recommending the atrocious woo film What the (Bleep) Do We Know?. You see, personally, I know that the whole Law of Attraction thing is bull. Why? Because I was expecting at least one post sent in would have some tenuous connection to pirates and allow me to bring you this classic puzzle. But nope, no pirates. Well, screw you guys, I'm doing pirates anyways!

A crew of 5 logic pirates comes upon a treasure of 100 gold coins. According to the rules of the logic pirates, to distribute the loot the most senior pirate must first propose a plan, and then they'll all vote on it. If at least half agree with the plan, they'll go with it. If not, the most senior pirate has to walk the plank, and then the next most senior pirate has a chance to propose a plan. This continues until a plan is accepted.

Each pirate is perfectly logical and has the following priorities they will strictly pursue: First, they don't want to die. Second, they want to get as much money as possible. If everything else is equal, they'd rather see more of their seniors walk the plank.

So, what plan can the most senior pirate of this group of 5 propose that will get him the most coins? Figured that out? Now, try the situation with 6 pirates and only one coin; what happens there?

Back to index


Adam said...

Well, for the Galileo puzzle, if you start with something like "Are you a clone that is..." then almost any trick question will do for the second part. The real Galileo gets out of it by not being a clone.

For instance, "Are you a clone that is lying?"

Adam said...

Hmm. Maybe not. But it's the right step, maybe....

Lord Runolfr said...

I suppose I should make some effort to solve my own puzzle.

One solution that occurs to me (without particularly deep thought) is to make three transparencies that each include about a third of the content of the plan.

Take a paper copy of the plan. Place a transparency over it and trace over about a third of the content (say, the vertical straight lines). Place another transparency over that and trace another third (say, the horizontal straight lines). Finally, use a third transparency to trace the remainder (curved lines).

Destroy the original, and you now have to stack and align the transparencies on the projector to see the plan.

miller said...

For the Galileo puzzle, you can ask the following compound question to voip out lying clones:

Is the following true: You will answer this with "yes" or (inclusive) you are the real Galileo.

Similarly, the following will voip truth-telling clones.

Is the following true: You will answer this with "no" or you are the real Galileo.

Alternating between these two questions will eventually voip a clone with the random curse.

I think I might be able to put that all together in a single compound question, but it'd be messy, and I need to think it over some more.

Simon said...

No, it's not particularly messy:

"Is it the case that you are a clone and that you will either answer this question truthfully with a 'no' or falsely with a 'yes'?"

exarch said...

Yeah, I think Great Galileo's Ghost was pretty much answered by previous posters.

The Super-Scammer Secrets could be solved with something resembling RAID1. Two datasheets and one control sheet. Set up in such a way that the two datasheets together don't make any sense until the control sheet blocks out the right words/letters.

The Harebrained Hat Help is another one of those where other people's inability to figure out what the colour of their hat is, adds information about the colour of your own.

If one of the prisoners in the Singular Sword Slashes was willing to sacrifice his own life for that of the others by getting last in line, then only his life would have been taken.

With Ending Erroneous Expectations, the key is to get two people on your side. That can be achieved by making the lowest ranking pirates happy by giving them more loot than they could expect once you're dead and the second highest ranking splits it all with number 3. For the one coin problem, it depends on whether the second highest ranking pirate realizes that his neck is on the line as much as yours, and neither of you has any chance of getting that coin.

Okay, enough puzzling and reading. Back to work ...

Infophile said...

Super-Scammer Secrets - The problem with that is that you want it to make no sense regardless of which two sheets are stolen. In this case, if the control sheet is stolen, some data can still be inferred. There is a solution that makes it so absolutely nothing can be inferred if any two sheets are stolen, though.

Edward said...

We can answer the pirates problem using induction, of sorts.

Consider the situation with 5 pirates. If it ever gets down to two pirates, the senior one can simply award all the money to himself and vote for it. With three pirates, the senior one has to convince one other pirate to vote for his plan. The cheapest way of doing this is to award the junior pirate 1 coin and keep 99. Then with four pirates, the senior one only has to convince one other pirate to join him. If it gets down to three, the middle one can't expect to make anything, so he can be bought with 1 coin. With five pirates, the senior pirate needs two others to join him. He can do this by giving one coin to each of the 3rd and 5th most senior pirates, since they'll get nothing if he dies. He would keep the other 98 coins to himself.

Now consider six pirates and only one coin. As before, with only two pirates, the senior pirate can award all money to himself. With three, the senior pirate needs to award the one coin to the junior pirate. With four, the senior pirate can award the coin to either of the two pirates immediately below him. With five pirates, the senior pirate need to convince two pirates to join him, which is impossible. Therefore the second most senior pirate will die if it gets to him, so he will vote for absolutely any plan the most senior pirate proposes. The most senior pirate can then avoid death by awarding the coin to the most junior pirate.

Rick Taylor said...

In the singular sword slashes, none of the prisoners were killed.

They all got together and agreed as follows. Whoever was last in line would call out his own hat based on the parity of red hats he saw before him. If he saw an even number of red hats, he'd call his red; if he saw an odd number red hats, he'd call his blue. That man might die, but the next in line, seeing the hats in front of him and knowing the parity of red hats including his own could deduce his hat color. The man in front of him, now knowing both the color of the hat behind him and the parity of all the hats besides his own could deduce his own, and so on to the front of the line. The executioner, hearing this and seeing he could not avoid sparing all but the last in line, arranged the hats to ensure at least he was killed, even though the 99 others were spared, and that was that.

Only it wasn't. All one hundred silently reasoned that the executioner would have to place an even number of red hats in order to kill the last one in line. And so they abandoned their plan and used that information to save them all from last to first.

Rick Taylor said...

Singular slashing sword continued:

The truly delicious part of that last solution is that even if we assume the executioner anticipated they would change their strategy to trick him (no reason to as he isn't part of the mensa cult) and put an odd number of red hats to on them, the last man in line would die, but the 99 remaining would still live, even using the wrong information. So there's no reason for them not to try!

RodeoBob said...

Got the Hats puzzle solved. It does, however, depend on everyone being an expert at logic, and everyone following the same game plan...

The color of the wearer's hat is the same color as the smallest group of colored hats he or she can see, and they must make their guess (and leave the circle!) at the first opportunity allowed.

To make it clearer, let's break the process up into 5-minute rounds. (at the end of each 'round', the announcement comes on asking folks to announce the color of their hat)

In the first round, anyone who can only see one hat of a specific color is wearing that color hat. (we know there must be at least two, right?)

In the second round, anyone who can see only two hats of a given color is wearing that color. (we know that there must be three of each color now, since any color that were only present on two heads should have left last round...)

The puzzle only works if everyone is looking, and if everyone leaves at the right time. If somebody falls asleep, or isn't paying attention, or loses count and misses a round, the whole thing falls apart.

Infophile said...

Yup, you got it. Of course, all those catches were the reason I put in the provision in my problem that it was only ever possible when everyone in the group was an expert at logic puzzles.

Rick Taylor said...

There's an extension to the hats problem. It's my own idea, though I don't know if someone else might have thought of it too. To make things more concrete, assume that there are sixty of them, thirty with red hats and twenty with green, and ten with blue. And to begin with, they know nothing except the color of everyone else's hat; we remove the original condition of the problem that they know there's at least two hats of each color. Under these conditions, no one cannot deduce the color of their own hat. Then someone comes in (wearing no hat of their own), observes everyone, and says where everyone can hear and see him, there is at least one red hat and at a least one green hat in the room. As in the previous problem, the twentieth round after the announcement, the people with green hats leave, and after the thirtieth round, the people with red hats leave (and the poor blue hatted patients are clueless).

Now, here's the question, and it's a subtle one. If no one had come in to announce that there was at least one red and one green hat, they would have sat there indefinitely, unable to make a deduction. So the announcement must have given the people an extra piece of information they didn't have before that allowed them to eventually deduce the color of their own hat. This is surprising, as of course the announcement was of a fact that everyone in the room already knew. So the question is, state precisely what the people in the room knew immediately after the announcement that they didn't know before, that changed things and allowed some of them to eventually deduce their hat color.

Infophile said...

Aha, that's a good one. Here's how I'd explain it (limiting it to just saying there's at least one red hat):

Basically, what everyone knows now is that, in the hypothetical case that only one person were wearing a red hat, that person would now be able to deduce the color of their hat. Now, at this point it's hypothetical, but as each announcement comes on, they gain a new piece of information by the fact that no one stood up. After the first message they knew that in the hypothetical case where only two people were wearing red hats, they'd then be able to figure it out.

Each round of PA announcements adds a new piece of information, which they always treat simply as a hypothetical situation that never happened. Eventually, they get to the hypothetical system that if 29 people were wearing red hats, they'd have been able to figure it out at the last PA announcement. That they couldn't, and that this person can see 29 other hats, means that there must be one extra red hat, on their head.

Rick Taylor said...

There's a way of putting it that doesn't refer to hypothetical situations, that only refers to the current situation.

Actually, it's hard to say what that hypothetical statement means. If one interprets it as, "In a room where only one person is wearing a red hat and they can see the color of the hats everyone else is wearin, if someone says at least one person is wearing a red hat, the person wearing it wil be able to deduce the color," that's something they all knew before the announcement, and it's not new information. If one interprets it as, "If only one person in _this_ room is wearing a red hat, they'd know it now," it's hard to say what that mans. Strictly logically it's trivially true, because a false condition always implies any condition, but then it was known true before the announcement as well.

miller said...

Oh, the scammer secrets suddenly seems so obvious after your hints.

The final information could be conveyed as a bunch of pixels, either black or white. Let's think of these as bits, where black is 1 and white is 0. To encode each bit, we will first create 2 slides with completely random bits. The last slide will be created non-randomly such that at each position, the sum of the bits (mod 2) is the same as the bit in the final information. If you have any two of these slides, you will simply have two slides with random bits, and will be able to determine nothing from it.

However, taking the sum of bits would be difficult, and I wonder if there is a solution in which the decryption process is easy, perhaps making use of the fact that these are transparencies. If the three slides were all green, all blue, and all red, then the message would be legible, at least in theory, just putting the slides on top of each other.

The follow-up to this puzzle would be: is there a way such that any n-2 out of n slides can give you all the information, while any less will give you nothing?

Infophile said...

You're getting close to solving it. Just think a bit more on what's possible with transparencies, and what the final result will look like. It's actually a bit more of a jump from the solution you proposed (which is a common guess, though not physically possible with transparencies) to something that works though, it seems.

Rick Taylor said...

Hmmm, should I go ahead and put a solution to the problem I proposed?

Infophile said...

Sure, I'm curious to see what solution you were thinking of.

Anonymous said...

So's been weeks since the puzzles were posted, and solutions attempted. When could we expect a solutions that are still unsolved?