Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[GendoIkari]

Inspired by probability paradoxes... I'll start with my favorite:

On an island where 200 people live, there are 100 people with blue eyes, and 100 people with brown eyes. The people on this island have no mirrors, and are not allowed to discuss eye color to find out what color their own eyes are. They live by a code that says that if anyone ever discovered his own eye color, he must leave the island at dawn the morning after he makes the discovery. Also, everyone on the island is great at logic, if a conclusion can be logically deduced, he will do it.

One day, a stranger shows up, and after looking around he announces "I can see someone with blue eyes."

What effect does this have on the inhabitants? Who leaves the island when?

[Watno]

Do people on the island know that there are 100 of each eye color?
Do people on the island see each other?

[GendoIkari]

The do not know how many of each there are... they do all see each other. So a blue-eyed person will know that there are at least 100 brown-eyed people and at least 99 blue-eyed people, but he won't know if his own eyes make it 100-100 or 101-99.

[Watno]

And the stranger sees all the people?

[GendoIkari]

Yes, he makes his announcement in front of everyone.

[Davio]

Can the inhabitants discuss the number of eye colors?

Like can one say to the other "I see 100 brown eyed persons", without uniquely identifying one?

[Jimmmmm]

The stranger must leave, since he said "I can see someone with (my) blue eyes", indicating he knows that his eyes are blue?

[GendoIkari]

Can the inhabitants discuss the number of eye colors?

Like can one say to the other "I see 100 brown eyed persons", without uniquely identifying one?

No. That would make it pretty trivial.

[GendoIkari]

The stranger must leave, since he said "I can see someone with (my) blue eyes", indicating he knows that his eyes are blue?

No... the stranger doesn't live by their rules... I should have clarified that the stranger's eye color is irrelevant... assume his eyes are green.

[Jimmmmm]

The stranger must leave, since he said "I can see someone with (my) blue eyes", indicating he knows that his eyes are blue?

No... the stranger doesn't live by their rules... I should have clarified that the stranger's eye color is irrelevant... assume his eyes are green.

Yeah, I hoped that wasn't it.

[bozzball]

The blue-eyed islanders leave the island on the 100th day, with the brown-eyed ones joining them the next day.

[Jimmmmm]

The only blue-eyed guy who forgot to wear his sunnies?

Yeah, I'm stumped.

[bozzball]

The blue-eyed islanders leave the island on the 100th day, with the brown-eyed ones joining them the next day.

The second part of the sentence is only true assuming that everybody knows that their eyes are either blue or brown.

[GendoIkari]

The blue-eyed islanders leave the island on the 100th day, with the brown-eyed ones joining them the next day.

The second part of the sentence is only true assuming that everybody knows that their eyes are either blue or brown.

For those who want to spoil the answer for themselves, bozzball got it perfectly! Have you seen this before, or did you figure it out?

[Ozle]

If they are great at Logic, why cant someone just go round and count the number of brown eyed people. if he gets to 100 then he knows he has blue eyes?

No need for strangers at all....

[Reyk]

For those who want to spoil the answer for themselves, bozzball got it perfectly! Have you seen this before, or did you figure it out?

It's very beautiful and I couldn't figure it out. As a (strong) hint for others:
Assume there are 198 brown eyed people and only 2 blue eyed rather than 100/100.

[Watno]

I had a reason of thought that led me in similar direction, but I don't see how the stranger is relevant. Everyone knows he sees a blue eyed person, because they see one themselves. So, how does he provide any additional information?

[Reyk]

If they are great at Logic, why cant someone just go round and count the number of brown eyed people. if he gets to 100 then he knows he has blue eyes?

No need for strangers at all....

because ...

The do not know how many of each there are... they do all see each other. So a blue-eyed person will know that there are at least 100 brown-eyed people and at least 99 blue-eyed people, but he won't know if his own eyes make it 100-100 or 101-99.

[soulnet]

Only homosexuals (and maybe asexuals?) would remain in the Island for more than a couple of days, given that there are only males on it. Actually, I guess almost every male in the world enjoy some form of interaction with females, so probably everyone will eventually leave if they can.

On a more serious note, I've heard an equivalent problem more tha 10 years ago, non-equivalent statement and answer, but the same reasoning behind the solution, so I'm going to guess that it is an old problem, and probably is recorded in a couple of books.

About the stranger being relevant
They know there is someone with blue eyes, and they also know everyone knows that, and they also know everyone knows everyone knows that, but blue eyed people do not not (everyone knows)⁹⁹ that, because you need to see at least 100 people to be sure of that, and blue eyed people only see 99

[Watno]

I think I see it now.

[Reyk]

I had a reason of thought that led me in similar direction, but I don't see how the stranger is relevant. Everyone knows he sees a blue eyed person, because they see one themselves. So, how does he provide any additional information?

The stranger is relevant because know everybody knows that everybody knows there is a blue eyed person.

[Ozle]

http://xkcd.com/blue_eyes.html

[GendoIkari]

I had a reason of thought that led me in similar direction, but I don't see how the stranger is relevant. Everyone knows he sees a blue eyed person, because they see one themselves. So, how does he provide any additional information?

It took me a really, really long time to accept the fact that the stranger's announcement could possibly change anything / realize why it's so. Yes, everyone on the island knows that that is at least 1 blue-eyed person, because they all see a blue-eyed person. In addition, everyone knows that everyone else knows that there is a blue-eyed person, because they see at least 2 blue-eyed people, so each other person must also see at least 1 blue-eyed person as well. However, before the stranger, not every one knew that everyone knew that everyone knew that everyone knew that everyone knew ... (repeat to the 100th level)... that there's at least 1 blue-eyed person. The stranger's announcement turns it into fully common knowledge. It's easier to see if you think of the case of only 3 people with blue eyes and 3 people with brown eyes.

[Ozle]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

[Reyk]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Yes, they can assume this in that moment, when the stranger is speaking, but only until day three.

[Qvist]

Why don't they just look into the water of the ocean around them? 
But this is an interesting riddle and pretty similar to one I enjoyed the most.


There are 3 Logic students having their final exam. The professor says:
"Instead of writing an exam I just let you having a final test.
There are 5 hats, 3 of them are red and 2 of them are white.
Please stand in a row, so that one of you can see the other two, another one can only see one and the front one can see no-one.
I will put a hat on each of you and then removing the 2 leftover hats out of the room.
You aren't allowed to talk or use any help or items.
If anyone of you can tell me what color the hat has he's wearing, all of you pass this test."
After an hour of silence the student on the front who couldn't see any other student gives the right answer.
--
How did he do that and what color had his hat?

[soulnet]

Alternate solution: They will all return to the deck when the game ends.

I guess this being in the non-Dominion related subforum, this solution is incorrect, though.

[GendoIkari]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Before the stranger's comment... if you are B1, you know that everyone knows there's at least 1 blue-eyes. However... for all you know, you have green eyes. So you assume for the moment that you do have green eyes. And if you do, then B2 would only be seeing 1 blue-eyes person (B3), and so B2 has no way of knowing whether or not B3 sees a blue-eyes person. So for all you know, B2 doesn't know if B3 knows that there's a blue-eyes person.

[Ozle]

I can understand it with 98 green and 2 blue obviously, as the other blue person must only be able to see me

[Ozle]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Before the stranger's comment... if you are B1, you know that everyone knows there's at least 1 blue-eyes. However... for all you know, you have green eyes. So you assume for the moment that you do have green eyes. And if you do, then B2 would only be seeing 1 blue-eyes person (B3), and so B2 has no way of knowing whether or not B3 sees a blue-eyes person. So for all you know, B2 doesn't know if B3 knows that there's a blue-eyes person.

Perfect, got it

[Ozle]

Its very much like the Unexpected Hanging Paradox

[Reyk]

Why don't they just look into the water of the ocean around them? 
But this is an interesting riddle and pretty similar to one I enjoyed the most.


There are 3 Logic students having their final exam. The professor says:
"Instead of writing an exam I just let you having a final test.
There are 5 hats, 3 of them are red and 2 of them are white.
Please stand in a row, so that one of you can see the other two, another one can only see one and the front one can see no-one.
I will put a hat on each of you and then removing the 2 leftover hats out of the room.
You aren't allowed to talk or use any help or items.
If anyone of you can tell me what color the hat has he's wearing, all of you pass this test."
After an hour of silence the student on the front who couldn't see any other student gives the right answer.
--
How did he do that and what color had his hat?

I assume his (nr. 1) hat is red. If hats of nr. 2 and nr. 1 were white nr. 3 - who can see both - would announce his red hat.
If he doesn't do this nr. 2 can announce his red hat if nr. 1 has a white one.
If he doesn't do this either nr. 1 can announce his red hat regardless of the color of the other two.

[GendoIkari]

Its very much like the Unexpected Hanging Paradox

Hah, I just spend some time a few days ago trying to explain that one.... I host a game night, and we were talking about switching which night we have it. We couldn't decide on a night, so I joked that game night would be on a random night each week; and no one would be able to expect which night it happens on; until I send the email saying it's time for game night... the paradox of the unexpected game night.

[Galzria]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

[Ozle]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Before the stranger's comment... if you are B1, you know that everyone knows there's at least 1 blue-eyes. However... for all you know, you have green eyes. So you assume for the moment that you do have green eyes. And if you do, then B2 would only be seeing 1 blue-eyes person (B3), and so B2 has no way of knowing whether or not B3 sees a blue-eyes person. So for all you know, B2 doesn't know if B3 knows that there's a blue-eyes person.

Hang on, lost it again!
Haha

B1
B2
B3
B4
GX (assume the number of green people doesnt matter?)

I am B1, I dont know whether I have green eyes or not, but now we are back to where I was before taking meout of the equation, that B2 can clearly see two people with Blue eyes, so could be talking about either of them, B3 or B4.

[Galzria]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

I'll even be nice, and tell you that the number that comes after the X is 102.

[Ozle]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

78?

[Galzria]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

78?

No!

[theory]

The blue eyes puzzle was nicely laid out by xkcd a while ago: http://xkcd.com/blue_eyes.html (no spoilers)

if you want the solution, replace "blue_eyes.html" with "solution.html"

[GendoIkari]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Before the stranger's comment... if you are B1, you know that everyone knows there's at least 1 blue-eyes. However... for all you know, you have green eyes. So you assume for the moment that you do have green eyes. And if you do, then B2 would only be seeing 1 blue-eyes person (B3), and so B2 has no way of knowing whether or not B3 sees a blue-eyes person. So for all you know, B2 doesn't know if B3 knows that there's a blue-eyes person.

Hang on, lost it again!
Haha

B1
B2
B3
B4
GX (assume the number of green people doesnt matter?)

I am B1, I dont know whether I have green eyes or not, but now we are back to where I was before taking meout of the equation, that B2 can clearly see two people with Blue eyes, so could be talking about either of them, B3 or B4.

When you go to B4 instead of B3, you just have to extend the logic out one step further. As B1... assume for the moment you have green instead of blue eyes. Think about what B2 now knows... Well, B2 is now in the exact same position that B1 was in earlier, back when it only went up to 3. So for all you know, B2 could be following all the same logic that you would follow if you were B1 in the situation where it only went up to 3 instead of 4.

[Reyk]

Nope, still dont getit.

Start with 3 people with blue and 3 with green.
B1
B2
B3
G1
G2
G3

Now obviously they can all see each other, and the Blues can see 2 other blues.

So when the stranger turns up and says I can see someone with blue eyes.
If I am B1, he can possibly be talking about B2, B3 or even me. But also i know that B3 can see B2 (and vice versa), so they could assume the stranger is talking about the other one.

Before the stranger's comment... if you are B1, you know that everyone knows there's at least 1 blue-eyes. However... for all you know, you have green eyes. So you assume for the moment that you do have green eyes. And if you do, then B2 would only be seeing 1 blue-eyes person (B3), and so B2 has no way of knowing whether or not B3 sees a blue-eyes person. So for all you know, B2 doesn't know if B3 knows that there's a blue-eyes person.

Hang on, lost it again!
Haha

B1
B2
B3
B4
GX (assume the number of green people doesnt matter?)

I am B1, I dont know whether I have green eyes or not, but now we are back to where I was before taking meout of the equation, that B2 can clearly see two people with Blue eyes, so could be talking about either of them, B3 or B4.

That's why they all leave the island on 100th day and not earlier.

[Drab Emordnilap]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

72

x + 1 and x - 1 are both prime.

[Galzria]

Logic Problems? Ehhh... This is close enough:

Here's a sequence of numbers. Can you tell me what the next number is and why?:

4, 6, 12, 18, 30, 42, 60, X

72

x + 1 and x - 1 are both prime.

Yes!

[Ozle]

Haha I only got that wrong because I cant add up!

[Qvist]

Why don't they just look into the water of the ocean around them? 
But this is an interesting riddle and pretty similar to one I enjoyed the most.


There are 3 Logic students having their final exam. The professor says:
"Instead of writing an exam I just let you having a final test.
There are 5 hats, 3 of them are red and 2 of them are white.
Please stand in a row, so that one of you can see the other two, another one can only see one and the front one can see no-one.
I will put a hat on each of you and then removing the 2 leftover hats out of the room.
You aren't allowed to talk or use any help or items.
If anyone of you can tell me what color the hat has he's wearing, all of you pass this test."
After an hour of silence the student on the front who couldn't see any other student gives the right answer.
--
How did he do that and what color had his hat?

I assume his (nr. 1) hat is red. If hats of nr. 2 and nr. 1 were white nr. 3 - who can see both - would announce his red hat.
If he doesn't do this nr. 2 can announce his red hat if nr. 1 has a white one.
If he doesn't do this either nr. 1 can announce his red hat regardless of the color of the other two.

Exactly. This might be not so complicated as Galzria's, but I like it a lot because it's hard enough for an "average guy" without being so complicated to not understand the solution.

[Ozle]

OK, finally got the eyed people day one, i missed that they all left on the 100th day! (Thought they left on that day!)

[GendoIkari]

Ok, another favorite, definitely difficult.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower. There you will find 2 levers that each can be set to either up or down. You must flip exactly one lever (either from down to up or up to down), then I will return you to your cell. I won't tell you what position the levers are in to begin with, but I won't ever touch the levers. If at some point you think that every single one of you have visited the tower at least once, then let me know. If you are correct, and everyone has visited the tower at least once, I will release all of you. But if you are wrong, then you will stay here forever."

What plan do the maidens come up with that night?

[jonts26]

I'll just leave this here

http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

[DStu]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

[Galzria]

I'll just leave this here

http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

The simpler version that I know of that is:

There are two computers, and two doors. Behind one door is a lion that will eat you, and behind the other is freedom and riches that will leave you happy for life.

One computer is programmed to answer any query made of it truthfully.
The other is programmed to answer any query made of it falsely.

You do not know which computer is which.

You may input one question only into one of the two computers. What question do you ask, and which computer do you ask it of?

[GendoIkari]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

[jonts26]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

[DStu]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

[DStu]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

The answer is incredible large...

[GendoIkari]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

Granted, once you reach 49 you're pretty likely to be safe... but there is a way to be sure.It's still your basic answer; just with a minor change.

[eHalcyon]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

Granted, once you reach 49 you're pretty likely to be safe... but there is a way to be sure.It's still your basic answer; just with a minor change.

Have each regular maiden signal twice instead of just once. Master maiden counts to 99 instead of 49.

[GendoIkari]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

Granted, once you reach 49 you're pretty likely to be safe... but there is a way to be sure.It's still your basic answer; just with a minor change.

Have each regular maiden signal twice instead of just once. Master maiden counts to 99 instead of 49.

Right.

[Jimmmmm]

My take on the blue eyes problem:

If there was exactly one person with blue eyes, they would leave the very next morning (morning 1). If there were exactly two, both would realise this after the other did not leave on morning 1, and leave on morning 2. If there were exactly 3, they would all see that the other two did not leave on morning 2, and then all leave on morning 3. And so on and so forth. So each morning that no one leaves increases the minimum number of people with blue eyes. On morning 99 when the other 99 people with blue eyes don't leave, everyone realises there must be at least 100 people with blue eyes, and all the people with blue eyes realise their eye colour and leave on morning 100, which makes everyone else realise they don't have blue eyes, since if they did all the blue-eyed people would hang around until the next morning.

In fact, if there are only two colours then you know already the exact morning you will leave, morning x + 1, where x is the number of people you can see with blue eyes.

[WanderingWinder]

My take on the blue eyes problem:

If there was exactly one person with blue eyes, they would leave the very next morning (morning 1). If there were exactly two, both would realise this after the other did not leave on morning 1, and leave on morning 2. If there were exactly 3, they would all see that the other two did not leave on morning 2, and then all leave on morning 3. And so on and so forth. So each morning that no one leaves increases the minimum number of people with blue eyes. On morning 99 when the other 99 people with blue eyes don't leave, everyone realises there must be at least 100 people with blue eyes, and all the people with blue eyes realise their eye colour and leave on morning 100, which makes everyone else realise they don't have blue eyes, since if they did all the blue-eyed people would hang around until the next morning.

In fact, if there are only two colours then you know already the exact morning you will leave, morning x + 1, where x is the number of people you can see with blue eyes.

This (last point anyway) can't be right, because you can make the same argument for the number of people you can see with non-blue eyes, and x for the two cases need not be equal.

Edit: I was assuming you were talking about the no new person showing up case, which I now realize isn't clear. The person showing up and saying blue breaks the symmetry, making my point not applicable

[pacovf]

My favorite puzzles have already been posted (blue eyes, 100 prisoners), so I'll just post a somewhat easy one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

[Drab Emordnilap]

My favorite puzzles have already been posted (blue eyes, 100 prisoners), so I'll just post a somewhat easy one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

Does the captain get a vote? I forget.

[Jimmmmm]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

My first thought is this: Start from the back of the line. If you're at an odd position, say the colour of the hat directly in front of you. There's a 50% chance of this being successful. If you're at an even position, simply say the colour that the person behind you said. This will save at least 50 of them, and on average 75. There may well be a way to do better, especially since using this strategy, the first person to speak will know exactly who will live and who will die.

[WanderingWinder]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

My first thought is this: Start from the back of the line. If you're at an odd position, say the colour of the hat directly in front of you. There's a 50% chance of this being successful. If you're at an even position, simply say the colour that the person behind you said. This will save at least 50 of them, and on average 75. There may well be a way to do better, especially since using this strategy, the first person to speak will know exactly who will live and who will die.

If you're forced to start at the back of the line and move up, you can save everyone except the dude at the back with 100% certainty, and that guy has a 50-50 shot. Not sure if being able to do better than this by going in some other order, but I don't think so.

[Jimmmmm]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

My first thought is this: Start from the back of the line. If you're at an odd position, say the colour of the hat directly in front of you. There's a 50% chance of this being successful. If you're at an even position, simply say the colour that the person behind you said. This will save at least 50 of them, and on average 75. There may well be a way to do better, especially since using this strategy, the first person to speak will know exactly who will live and who will die.

If you're forced to start at the back of the line and move up, you can save everyone except the dude at the back with 100% certainty, and that guy has a 50-50 shot. Not sure if being able to do better than this by going in some other order, but I don't think so.

I had a feeling there was a way to guarantee either 99 or 100 (I may have heard of it before), but I have no idea how. Like, the only possible information each person can get is from what the very first person said.

Edit: I'm assuming you can't give across any information by the timing etc that you say your colour.

[WanderingWinder]

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

My first thought is this: Start from the back of the line. If you're at an odd position, say the colour of the hat directly in front of you. There's a 50% chance of this being successful. If you're at an even position, simply say the colour that the person behind you said. This will save at least 50 of them, and on average 75. There may well be a way to do better, especially since using this strategy, the first person to speak will know exactly who will live and who will die.

If you're forced to start at the back of the line and move up, you can save everyone except the dude at the back with 100% certainty, and that guy has a 50-50 shot. Not sure if being able to do better than this by going in some other order, but I don't think so.

I had a feeling there was a way to guarantee either 99 or 100 (I may have heard of it before), but I have no idea how. Like, the only possible information each person can get is from what the very first person said.

Edit: I'm assuming you can't give across any information by the timing etc that you say your colour.

Simple version. Treat say white hats as 1s, or really just count them. Guy in back says white if there's an odd number of white hats in front of him, black if there's an even number. He gets a 50-50 shot - there's no way for him to tell what his own hat is, nobody can see it. Next guy in front of him counts the number of white hats. If guy behind him said white, then he know guy behind him saw an odd number of white hats. If this is the case, he can count number of white/black hats in front of him, and if it's also odd, he knows he's wearing black, or if it's even, he knows he's wearing white. If guy in back said black, he knows that there were an even number of white hats, and if he also sees an even number, he's wearing black, and if he sees an odd number, he must be wearing black. Then everyone else just keeps this even-odd counter in their head. Every time somebody says white, because everyone before them and after the first guy was right, they flip the counter in their head. Then they count the number of whites in front of them and compare, is that number even or odd. If it matches their counter, they must be wearing black. If it differs, then they must be wearing white. Ergo, everyone except the last guy can be sure.[/quote]

[Jimmmmm]

Ah, very nice.

[Grujah]

I looove the maiden one. count 50 unique visits with only 2 bits, it's awesome
I did not solve it.

100 prisoners are about to be executed. The king, in his mercy, decides to give them a chance for pardon. Each prisoner will be given either a white or a black hat at random and are then arranged in a line such that each prisoner can see every other prisoner in front of him, but none behind him. The prisoners are given some time to formulate a strategy, but once they are lined up, each prisoner can only speak a single word, either black or white. If the prisoner correctly identifies his own hat color, he goes free. If not, he dies.

What is the best strategy for allowing the most number of prisoners to go free?

I think this is it:
The one at the far back counts the number of white hats. He says white if it is even, black if it is odd. He is 50-50.
Guy in front of him now knows if he is black or white (if he sees the same oddity, he is black, otherwise he is white).
Guy in front of that guy now eliminates the last guy from calculations, and does the same.
And so on..

Last guy in line is 50-50, rest are 100-0.

Right?

Edit: Ninja'd by WW, but I didn't know this beforehand ( I did know blue eyes from xkcd )

[Lekkit]

Ah, very nice.

Love the spoiler tags on this one.

[Jimmmmm]

Ah, very nice.

Love the spoiler tags on this one.

[Grujah]

My favorite puzzles have already been posted (blue eyes, 100 prisoners), so I'll just post a somewhat easy one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

Does the captain get a vote? I forget.

Figured this one out. Yeah, cap gets a vote too, checked wiki for exact setup. Also, they want as much money as they can get (greedy), and if they can kill some other pirate while still receiving the same amount of money, the will do so (bloodthirsty).

[Jimmmmm]

My favorite puzzles have already been posted (blue eyes, 100 prisoners), so I'll just post a somewhat easy one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

Captain keeps 97 for himself and gives 1 to each of 3, 5 and 7?

[pacovf]

Captain keeps 97 for himself and gives 1 to each of 3, 5 and 7?

Yep! Obviously, if the pirates could leave the ship, I'm sure that wouldn't be the solution

Does the captain get a vote? I forget.

Figured this one out. Yeah, cap gets a vote too, checked wiki for exact setup. Also, they want as much money as they can get (greedy), and if they can kill some other pirate while still receiving the same amount of money, the will do so (bloodthirsty).

Ah, you beat me

You can solve the problem too if the captain doesn't get a vote; it's slightly harder, and gets you a different result, but the way you get the solution is the same.

[Grujah]

I'll just leave this here

http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

The simpler version that I know of that is:

There are two computers, and two doors. Behind one door is a lion that will eat you, and behind the other is freedom and riches that will leave you happy for life.

One computer is programmed to answer any query made of it truthfully.
The other is programmed to answer any query made of it falsely.

You do not know which computer is which.

You may input one question only into one of the two computers. What question do you ask, and which computer do you ask it of?

I solved this one as a kid, asked in a bit different form, so this might not be a valid query to put in:
Are the truth-telling computer and door with riches on booth the same side? (i.e. left)
If the answer is yes, you go to the door on the same side as the computer that you asked at, otherwise on the other door.)

If not, you need to artificially pair the computers and the doors in some fashion, and than ask a more complicated query, i.e.
"If I name you the "green" computer, and the other one "blue" computer, and I name door 1. "green" and door number 2 "blue", are both truth telling computer and door to the riches of the same "color"?

[Galzria]

I'll just leave this here

http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

The simpler version that I know of that is:

There are two computers, and two doors. Behind one door is a lion that will eat you, and behind the other is freedom and riches that will leave you happy for life.

One computer is programmed to answer any query made of it truthfully.
The other is programmed to answer any query made of it falsely.

You do not know which computer is which.

You may input one question only into one of the two computers. What question do you ask, and which computer do you ask it of?

I solved this one as a kid, asked in a bit different form, so this might not be a valid query to put in:
Are the truth-telling computer and door with riches on booth the same side? (i.e. left)
If the answer is yes, you go to the door on the same side as the computer that you asked at, otherwise on the other door.)

If not, you need to artificially pair the computers and the doors in some fashion, and than ask a more complicated query, i.e.
"If I name you the "green" computer, and the other one "blue" computer, and I name door 1. "green" and door number 2 "blue", are both truth telling computer and door to the riches of the same "color"?

The simpler answer, without needing to define anything at all (and probably derives from the question Jonts linked), is "What door would the other computer tell me contains the riches?"

If you asked the Truth computer, he would answer by directing you to the door with the Lion.
If you asked the Lying computer, he would answer by directing you to the door with the Lion.

In either case, you choose the opposite door.

[WanderingWinder]

Another hat problem (the first one I ever heard):
Four buys are captured, yadda yadda,  and put, buried in sand up to their necks, into the following arrangement:
O O O | O
Where O represents a guy's head and | represents a wall that can't be seen through. All of them are facing the direction that corresponds to right in the above diagram. They are told that two of them will have white hats on their heads, the other two black hats. The first thing any of them says must be their own hat color; if they do this, all are freed; if not, they are all executed.
The hats are put on them in the order Black/White/Black|White. Who is able to free them all (none of them, one, or multiple people; if more than 0, specify which)?

[liopoil]

The second person can.

They see a black hat. They know that if they have a black hat as well than the person in the back will see two blacks and will say white. When the person in the back doesn't say white the second person knows that their hat must be white.

[Polk5440]

I love the blue eyed islanders problem because it shows what a strong/important assumption common knowledge is and helps you to understand the difference between Nth level knowledge and common knowledge.

[jonts26]

Another hat problem (the first one I ever heard):
Four buys are captured, yadda yadda,  and put, buried in sand up to their necks, into the following arrangement:
O O O | O
Where O represents a guy's head and | represents a wall that can't be seen through. All of them are facing the direction that corresponds to right in the above diagram. They are told that two of them will have white hats on their heads, the other two black hats. The first thing any of them says must be their own hat color; if they do this, all are freed; if not, they are all executed.
The hats are put on them in the order Black/White/Black|White. Who is able to free them all (none of them, one, or multiple people; if more than 0, specify which)?

So only one person has to say their hat color?

The guy in second position should know the color of his hat. If he and 3rd position had the same color hat, guy in first position would be able to immediately know his hat was the opposite color. After waiting a while, second position knows first position says nothing, thus indicating his own hat is different than the guy in front of him.

[Ozle]

Second guy can sayhis. Because he knows if he is the same as the guy in front of him the guy at the back would know his hat, therefore he must have a different colour to the guy in front

[Titandrake]

Woops was on wrong page.

[Jimmmmm]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

[Titandrake]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

[Jimmmmm]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

Pretty much my exact thoughts.

[Titandrake]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

Pretty much my exact thoughts.

More thoughts (no solution yet)

Let's say there are 7 pirates. The captain proposes a split, which I'll label A,B,C,D,E,F,G. The 4th to last pirate can say, "If the 3rd last, 2nd last, and 1st last pirate vote no with me, I will propose D_2,E_2,F_2,G_2 (with D_2 >= D, E_2 >= E, F_2 >= F, G_2 >= G)" Because the pirates are bloodthirsty, the last 4 pirates will all agree to vote no and kill the captain. A similar argument can be done for any number of pirates (except 2), so the first captain will always die.

The tricky part is that the 4th to last pirate will know this, and knows that if he is the captain and hasn't made the others agree to a promise to pass his proposal, he will die. He can ask the others to vote no until he is the captain, but some of the pirates won't agree. My guess is that it is impossible for the 4th last pirate to design a promise that ensures he does not die. If such a promise is made, the other pirates can simply disagree.

The correct answer might actually involve the first half of pirates making an agreement to vote yes because otherwise they'll all die, but balancing it with bloodthirsty makes it tricky.

[pacovf]

I'd put the order of priorities of pirates this way:
-Survive
-Earn as much money as possible
-Kill as many pirates as possible

So, in the case that pirates are perfectly trustworthy, a follow-up to Titandrake's post:

[EDIT: actually, it doesn't work; I'm still thinking on it, but I forgot that in a 4 crew ship, any deal that doesn't involve the captain requires all other pirates to agree, so that they represent the majority]
-With 4 pirates, if no promise is made, the second pirate will accept whatever the captain offers, 0 coins included, or otherwise he will die, as Titandrake said.
However, the third pirate can strike a pact with the second pirate: if he votes against the captain, he will accept a 0, 100, 0 split afterwards, which the second pirate and fourth pirate would normally accept, since that way they kill one extra pirate; but the fourth pirate can also offer a 0,0,100 split, which is equivalent for the second captain; as such, they will both rise their offers until they both reach 99 coins for the second pirate and one coin for the relevant pirate, so that doesn't seem like a very good split for the third or fourth pirates. Assuming (*), this means a 99, 1, 0 split.
Thus, the captain (a bit nervous since everybody is discussing his death) will instead try to earn the loyalty of the third or fourth pirate, and one coin for the fourth pirate should suffice , since otherwise he would earn nothing. But! Whatever 100-n, 0, 0 n split the captain proposes, the second pirate can offer the same to either the third or fourth pirate, and they will accept, since they are bloodthirsty. As such, the captain, trying to survive, will offer the 100 coins to either the third or fourth pirate, and the second pirate, seeing that he will earn nothing, will also offer 100 coins to either the third or fourth pirate, as he is bloodthirsty.
Probably before reaching that point, the captain and the second in command will realize that it may be better to reach an agreement between them, but that's prisoner dilemma: if the captain offers a 100-n, n, 0, 0 split, the second pirate could accept, or try to get a better deal with either the third or fourth pirate, which is always possible, since a 0, n, 0, 100-n split seems better for him (he gets to kill the captain); but that reasoning leads to a 0, 0, 0, 100 split (according to the previous paragraph), which is worse than the previous 100-n, n, 0, 0 split...

Adding extra rules about how and when the pirates can strike a deal would make this quite easier... or solvable...

*I would add that, if a pirate has the choice among more than one deal that are equivalent to him (according to the three laws of buccaneering above), he will choose the one proposed by the highest ranking pirate. It can shave some lines of discussion for higher number of pirates.

[qmech]

Here's my favourite hat problem.  It might not be quite right for this thread, but I'll throw it out there anyway.

A countable infinity of people are all standing in a line and wearing a black or white hat.  Everybody can see the colours of the hats of the (infinitely many) people standing in front of them.  They must all simultaneously shout out a guess as to the colour of their own hat.  Can they ensure that only finitely many people guess wrong?

[liopoil]

AHHH! INFINITY! 

Can they talk before announcing at all?

[qmech]

Yes, they can make whatever (mathematically ideal) arrangements they like.  And, if you decide it matters, there is a first person, at the back of the line, who can see everybody else.

[Galzria]

Are they spaced close enough to touch one another? If so then it's easily solvable for (Infinty - 1), with a 50% chance of all of them guessing correctly.

However, I don't think that's to the spirit of the question.

[DStu]

Can they ensure that only finitely many people guess wrong?

I'd love to be convinced otherwise, but: No.

Edit: Ok, I see a slim path that might work...
Hats are black/white with probability 1/2 and independent?

Edit2: A very slim path...

[liopoil]

yeah. After they have the hats on they have absolutely no means of communication... so it should be impossible.

[qmech]

The hats colours are chosen by the devil after you've decided on your strategy.  And no touching!

[Grujah]

is infinite time available?

[qmech]

is infinite time available?

Yes, and more.  Any precisely stated strategy would be legal, regardless of whether or not it could actually be implemented in a physical universe.

[DStu]

The hats colours are chosen by the devil after you've decided on your strategy.  And no touching!

Then no.

Edit: Except if I may use non-euklidian geometry.

[Grujah]

is infinite time available?

Yes, and more.  Any precisely stated strategy would be legal, regardless of whether or not it could actually be implemented in a physical universe.

How do they coordinate the exact moment when they all shout it together?

[qmech]

They all know in advance.  Or any other answer that prevents them passing information that way: for example, they could each write down their guesses on a piece of paper that nobody else can see.

[Watno]

I think I heard this one before and didn't get it, but i remember it only worked with the Axiom of Choice

[DStu]

I think I heard this one before and didn't get it, but i remember it only worked with the Axiom of Choice

If  I remember correctly, Axiom of Choice follows from the rest of ZF if you only have sets with 2 elements.  But could be wrong...

[Watno]

The Axiom of Chioce is trivial for all countable sets, but I don't see how that matters?

[DStu]

The Axiom of Chioce is trivial for all countable sets, but I don't see how that matters?

I just meant you don't need to assume AC as the part of it that you (probably) need, you get for free...

[Grujah]

They all know in advance.  Or any other answer that prevents them passing information that way: for example, they could each write down their guesses on a piece of paper that nobody else can see.

my plan is that they somehow, make black hats "ones" and white hats "zeroes", and than all should after X seconds (X being the number that they binary represent) somehow led by the last person in line. But there is no way for him to lead it that way.

[shMerker]

Does everyone know how far they are from the back of the line?

[qmech]

Does everyone know how far they are from the back of the line?

There are four possible variations:

1) The line has a start point
2) The line is doubly-infinite

a) The positions are labelled, and each person knows the label of their position
b) The positions are unlabelled

Each statement of the problem has an answer: starting with 1a may well make you more comfortable (it did me).

[pacovf]

I guess you cannot give a clue to those of us that are clueless...?

I cannot fathom how:
-Infinite people discuss a strategy;
-Devil puts hats on people according to the strategy they have agreed upon;
-Without any means to communicate (since they have to shout simultaneously, which negates the possibility that waiting "t" seconds before shouting means anything) after the hats are on, they have to guess the colour of their hat;

can somehow lead to a finite amount of errors. Afterall, the impossibility to communicate once the hats are on means that they cannot react to the devil's strategy, while the devil can react to their strategy, which would mean that their best shot at surviving would be to guess randomly...

[Kuildeous]

The hats are put on them in the order Black/White/Black|White. Who is able to free them all (none of them, one, or multiple people; if more than 0, specify which)?

I'm a little confused by this. If the first person who says something is correct, then they all go free, but if he is incorrect, then they are all executed. So I'm not sure what it means that "multiple people" is an option here….unless it's for the sake of completeness.

I had misread this puzzle at first and thought that everyone had to get their hat color correct. I was able to figure out how #2 and #3 could get their colors, but I was at a loss for the two outside people. But if the outcome hinges on the first guy to say something, then I agree that person #2 can set them free.

In fact, I think it only takes one guy to free them all no matter how the hats are distributed. It just depends on how they're arranged to determine if the savior is person #1 or person #2.

[Ozle]

For the infinite people in a line question (using Red or Blue Hats)

For the infinite people in a line puzzle, you can save all but the first one can't you?

The first person shouts out BLUE if he can see an odd number of red hats, and RED if he can see an even number.

The second person can then count how many red hats he can see, if it is an odd number and the person has shouted BLUE, then he knows he is wearing a RED hat.

The next person can then count the Red hats, he knows there is an odd or even number depending on what the two people before him shouted, so therefore knows what he is wearing.

This then follows on down the line for ever?

I am unsure what the infinity adds to the puzzle, makes it needlessly complicated.

[Drab Emordnilap]

In the Devil's Infinity hats, don't they ALL have to guess at the same time?

[DStu]

@Ozle. They all shout out at the same time, so that doesn't work.

I am unsure what the infinity adds to the puzzle, makes it needlessly complicated.[/spoiler]

Even if they wouldn't shout out at the same time, they will in almost all cases (and certainly in the worst case for your strategy) see infinite Blues and Reds, which is neither odd nor even, so infinity adds that this strategy does not work.

[Grujah]

For the infinite people in a line question (using Red or Blue Hats)

For the infinite people in a line puzzle, you can save all but the first one can't you?

The first person shouts out BLUE if he can see an odd number of red hats, and RED if he can see an even number.

The second person can then count how many red hats he can see, if it is an odd number and the person has shouted BLUE, then he knows he is wearing a RED hat.

The next person can then count the Red hats, he knows there is an odd or even number depending on what the two people before him shouted, so therefore knows what he is wearing.

This then follows on down the line for ever?

I am unsure what the infinity adds to the puzzle, makes it needlessly complicated.

Yeah, this is the solution I posted for last similar riddle, but here they need to guess all at the same time.

[Ozle]

Oh, bugger.

Back to the drawing board then

[qmech]

Yes, simultaneous guessing, and everyone is looking in the direction that lets them see infinitely many others.

Here's another way to think about it for those worried about the mechanics of communication.  A strategy is just a huge lookup table for each person, mapping the infinite pattern of hats they see to a guess of red or blue.  And the strategy is assigned to each person by you, the God of the Matrix, who has absolute freedom, unconstrained by time or space.

[Grujah]

Well,

there is no true random so one could see a pattern over time?

[DStu]

Well,

there is no true random so one could see a pattern over time?

It's not even stated that it's random...

edit: Beside this, of course there exists true random.
edit2 scnr

[Grujah]

Well,

there is no true random so one could see a pattern over time?

It's not even stated that it's random...

If it is not random, than it has a pattern, than it is easy to solve. \o/.

[mith]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

What is their optimal strategy?

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

[DStu]

If it is not random, than it has a pattern, than it is easy to solve. \o/.

That's not true, it could be the binary of an unknown irrational number for example...

[Grujah]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

They can all see eachother, right?

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

Switch papers?

Seriously, what are they able to do after hats are given? I guess they can't talk otherwise it is trivial. Can they move? Can they "form pairs"? Can they see each other?

[DStu]

I desperately want to give a hint on that one in light of one of DStu's posts...

ok, we have some nitpicking with axiom of choice, that can't be it. Don't see anyway what that can have to do with it.
The non-euklidian geometry was a joke but of course would work.

so my best guess is "infinity is neither odd nor even".  But even if we could get this principle to infinty, you can pass no info, that doesn't help.
What else did I say?  The post with random? You could argue that the sequence set up by the devil must have some finite complexity (but why should that be true), and that in this sense there is some finiteness in the series, but even if you would limit the devil to finiteness you yourself would need at least as much capacity as the devil to find the regularity, which I don't think is reasonable to assume...

[jonts26]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

What is their optimal strategy?

Can they see each other but not their own hats? Do they know if someone has already made a guess? I'm assuming no communication. I need constraints.

[Galzria]

What if they agree to all yell "Black" if anywhere in front of them they see even a single black hat, otherwise they yell "White"?

This would mean that any person wearing a Black Hat will guess Black if any person in front of him has a Black hat on. And if nobody does, then every person in front of him will guess correctly (even though he is wrong). This guarantees some number X of infinity will be correct.

[DStu]

But you nevertheless have infinitely many people who guess wrong.

[Tables]

What if they agree to all yell "Black" if anywhere in front of them they see even a single black hat, otherwise they yell "White"?

This would mean that any person wearing a Black Hat will guess Black if any person in front of him has a Black hat on. And if nobody does, then every person in front of him will guess correctly (even though he is wrong). This guarantees some number X of infinity will be correct.

The difficulty isn't getting an infinite number of correct solutions. It's getting a finite number of incorrect solutions.

[jonts26]

Here's my favourite hat problem.  It might not be quite right for this thread, but I'll throw it out there anyway.

A countable infinity of people are all standing in a line and wearing a black or white hat.  Everybody can see the colours of the hats of the (infinitely many) people standing in front of them.  They must all simultaneously shout out a guess as to the colour of their own hat.  Can they ensure that only finitely many people guess wrong?

Everyone is standing on some sort of non-euclidean plane such that each can see himself from behind and thus just says what color hat he's wearing. 100% success rate.

[mith]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

What is their optimal strategy?

Can they see each other but not their own hats? Do they know if someone has already made a guess? I'm assuming no communication. I need constraints.

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

Switch papers?

Seriously, what are they able to do after hats are given? I guess they can't talk otherwise it is trivial. Can they move? Can they "form pairs"? Can they see each other?

For both puzzles: They are given the opportunity to see each others hats (but not their own), and then are taken away to isolated cells. No communication once the hats are given out.

[Galzria]

What if they agree to all yell "Black" if anywhere in front of them they see even a single black hat, otherwise they yell "White"?

This would mean that any person wearing a Black Hat will guess Black if any person in front of him has a Black hat on. And if nobody does, then every person in front of him will guess correctly (even though he is wrong). This guarantees some number X of infinity will be correct.

The difficulty isn't getting an infinite number of correct solutions. It's getting a finite number of incorrect solutions.

But this gives you a guarantee of 1. Always. Every other guess may be wrong but you WILL have 1 correct. What's more, it's IMPOSSIBLE to have all guess correctly here. So your range is {1, (Infinity -1)}

[liopoil]

infinity minus one is infinity. You need a guaranteed finite number of incorrect answers.

[Ozle]

Separate them into infinite groups, then it becomes like every other hat problem?

[eHalcyon]

Separate them into infinite groups, then it becomes like every other hat problem?

But those hat problems don't have them speak simultaneously.

Also, I don't think there was a solution to a hat problem with 100% success for every participant.  So even if you separate them into infinite groups of finite people, each of those groups may have one incorrect, one incorrect in each of infinite groups is an infinite number of incorrect people.

[fractic]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.


The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

[Tables]

For the second problem, can we assume every suitor's suitability is independent of one another and uniformly distributed?

[fractic]

You can assume that no two suitors are equally suitable, and that they appear in a completely random order.

[Tables]

Ah, okay, but you cannot know where a suitor is in terms of rank? Just how suitable they are linearly?

In that case I think I've read the solution before in a book by Ian Stewart. It's pretty neat, and nice and mathematical IIRC.

[fractic]

Yes basically that. So if the princess sees the 10th suitor she immediately knows (for example) that he's better than 6 of the ones she saw before but worse than the other 3. But she has no idea how close this this 10th suitor is to the best one.

[Grujah]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

[Grujah]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

[Grujah]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

If it is better than at least X of them, where X is the number of remaining suitors, go for him?

[mith]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

Yep, that's it. As for proving it's optimal, the worst case can't be better than the average case.

[Grujah]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

Yep, that's it. As for proving it's optimal, the worst case can't be better than the average case.

well, Duh. 

[fractic]

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

I checked this topic and the probability paradoxes one but didn't see it.

As for as the answer goes: Not really I think. Of course the prisoners can assume that the previous one succeed since they already lost otherwise. But there is no real point in doing this. In fact the optimal solution has every prisoner follow the same strategy not caring about what the previous guys did. They are trying to exploit a certain property that the distribution of the papers might have.

If it is better than at least X of them, where X is the number of remaining suitors, go for him?

Sorry but, This strategy will obviously frequently select a suitor that isn't even better than all the previous ones. All though if the princess is OK with an average candidate rather than the perfect one this strategy might be better.

[mith]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.

Well, as a starting point: Each prisoner starts with their named box, then opens the box corresponding to the piece of paper, and so on until they either find their name or run out of tries. If the largest cycle contains 50 or fewer boxes, they will all succeed; otherwise, they will all fail. I am far too lazy to figure out what the probability of success is...

[jonts26]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

Just to be clear, are we trying to maximize the chances that the princess picks the one very best suitor, or are we trying to maximize the expected suitableness of the suitor she does pick, or is the distinction not relevant?

[fractic]

Just to be clear, are we trying to maximize the chances that the princess picks the one very best suitor, or are we trying to maximize the expected suitableness of the suitor she does pick, or is the distinction not relevant?

We want to maximize the chances of the princess picking the best suitor. Maximizing for the best expected suitability probably involves a different strategy.

[Grujah]

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

I checked this topic and the probability paradoxes one but didn't see it.

As for as the answer goes: Not really I think. Of course the prisoners can assume that the previous one succeed since they already lost otherwise. But there is no real point in doing this. In fact the optimal solution has every prisoner follow the same strategy not caring about what the previous guys did. They are trying to exploit a certain property that the distribution of the papers might have.

Here it is:
http://forum.dominionstrategy.com/index.php?topic=4644.0

(Spoilers obviously, ehunt posted (on page 2) what seems to be definite solution?)

I was wrong on strategy, completely

[mith]

Simpler calculation than I had feared. I should be less lazy.

[fractic]

Well, as a starting point: Each prisoner starts with their named box, then opens the box corresponding to the piece of paper, and so on until they either find their name or run out of tries. If the largest cycle contains 50 or fewer boxes, they will all succeed; otherwise, they will all fail. I am far too lazy to figure out what the probability of success is...

This is basically correct. I'll explain in the spoiler how it works.

Since the answer doesn't really depend on the number of prisoners, let's assume there are 2n of them and that they open n boxes each.
Each prisoner will first open the box with their name on it and then every time the box with the name that is on the paper in the previous box. If he could open as many boxes as he
wants this will eventually lead back to the box with his name on it, and therefore the previous box contained his own name. If you have trouble seeing this, consider
that there are only a finite number of boxes and that every box shares a name with only a single piece of paper.

The prisoners now escape if every one of them finds their own name within n boxes. So if there is a single cycle of n+1 or longer they will fail. It's easier to compute the probability of failure, so we'll do that. Now there can only be 1 cycle of n+1 or longer since there are only 2n boxes. Let k>n the chance that there is a k-cycle is

(number of ways to choose k names to go in the cycle)x(number of way to order them in the cycle)x(number of ways to permute the other 2n-k names)=(k!/((2n)!x(2n-k)!)x(k-1)!x(2n-k)!=k/(2n!)

So the total number permutations with a n+1 cycle or longer is (n+1)/2n!+(n+2)/2n!+...+n/(2n!). Since the total number of permutations is 2n! this means that the chance of failure is
exactly 1/(n+1)+1/(n+2)+...+1/2n.

Using the approximation for the harmonic series that says 1/1+1/2+...+1/n ~=~ log(n) we see that the chance of failure is approximately log(2n)-log(n)=log(2) ~=~0.69.

So our inmates have just over 30% chance of freedom.

Here it is.

I just typed up the solution myself too but thanks for the link.

[DStu]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

[Titandrake]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

I have seen this problem before, but didn't solve it at the time. It was for a team competition at a summer program I went to. It was a more general version though: In a team of 7 people, each member is given a number from 1 to 6. We just brute-forced it by all guessing 4.

[jonts26]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

You can beat that by guessing randomly.


The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

No one knows if another person submitted a guess. See each others hats and then go to seclusion.

[Titandrake]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

You can beat that by guessing randomly.


The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

No one knows if another person submitted a guess. See each others hats and then go to seclusion.

That's not stated in the problem, but if you assume that then I don't know.

I also missed the "nobody guesses incorrectly" line, which makes guessing randomly a pretty bad idea. Also have to modify the strategy to #1 or #2 not guessing tells #3 something.

[Grujah]

I also missed the "nobody guesses incorrectly" line, which makes guessing randomly a pretty bad idea. Also have to modify the strategy to #1 or #2 not guessing tells #3 something.

I missed that line too :s

[DStu]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

Oh, there are just 4 people. 11/16 is 5 people and 5 hats...  Ok, let's rethink this... In this case just assuming the same principle works here (have no doubt that it will)

... gets me to  ... hmm, it's 1/2 here, but that of course can be achieved trivially.  Have to modify...

Edit:

OK, can reproduce 11/16 for 4 people

[ghostofmars]

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

If the people know, if someone else guessed, I suggest the following strategy
Player 1: If nobody says anything for 30 seconds, I say 'black'.
Player 2: If Player 1 has black hat, say nothing, otherwise wait for 20 seconds and then say 'black', if nobody else did.
Player 3: If Player 1 or 2 have black hat, say nothing, otherwise wait for 10 seconds and then say 'black', if Player 4 didn't.
Player 4: Say 'black' if none of Player 1-3 has a black hat.
This would work for all but the 'all white' case... = 15/16

[mith]

Repeating since it's buried at the bottom of page 5:

"For both puzzles: They are given the opportunity to see each others hats (but not their own), and then are taken away to isolated cells. No communication once the hats are given out."

[ghostofmars]

Now, I also get 11/16...

[mith]

You can do better.

[DStu]

You can do better.

Than I say 3/4. I think I've proven an upper bound of 4/5, and 12/16 is the only 1/16 left which is smaller than 4/5, each deterministic strategy has an sucessrate which is an mutiple of 1/16, an I doubt that a random strategy will help. qed.

Can  now please someone say something concerning these infinitely many hats?

[mith]

Your upper bound suggests you've figured out the basic idea, so a hint for getting to 3/4: What would the answer be if there were only three men?

[mith]

And a hint on the infinite hats.

Re: DStu's reply 100 - If you are choosing from a countably infinite number of finite sets, the Axiom of Choice is free. When would it not be free?

[DStu]

Your upper bound suggests you've figured out the basic idea, so a hint for getting to 3/4: What would the answer be if there were only three men?

I thought getting to 11/16 is the basic idea, but I don't find the last case...

[DStu]

And a hint on the infinite hats.

Re: DStu's reply 100 - If you are choosing from a countably infinite number of finite sets, the Axiom of Choice is free. When would it not be free?

I'm not the expert in set theory, but afaik it's still free if you are choosing from any number of finite sets, at least if these finite sets are ordered, which is the case here. Say white<black

So the other way round take countable number of  uncountabe  large sets

But after all, I still don't see how the AC should give me a strategy to guess correctly, as it's usually pretty non-constructive.

[pacovf]

If any of you lack the capacity to solve problems involving infinitely countable hats (I know I do), here's one of my favourite puzzles (this one is by Raymond Smullyan; I had to retranslate the version I have, so sorry if the English is wonky):

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

[Ozle]

Helen

[pacovf]

Helen

I'll wait for the spoilered explanation since, you know, there's a 50% chance to guess randomly

[Ozle]

Darn, foiled!

I'd have got away with it if it wasn't for those pesky kids!

[qmech]

Hats:

The Axiom of Choice hint isn't so helpful - the Axiom of Choice is true!  People don't flag up when they use any of the ZF axioms, and it's quite possible to happily do things that require Choice before you know anything about it (countable unions of countable sets shocked me the first time it was pointed out). 

The next set of tags is a different hint.  It's not a hint I've ever given before, because I've never tried to help anyone solve this (aside: if you're a mathematician in training, you're strongly encouraged not to read the hint).

Suppose g is a good guess for hat pattern H. When else is g a good guess?

[mith]

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"

The point of the hint was simply to point out that the choosing here will not be "Pick a color for each person", where the AoC is true without assumption. The solution requires a different application of AoC, and is not valid in a set theory where the AoC is not true.

[ghostofmars]

Now I have 12/16
The general idea is that everyone tries to make a guess, if it could be that someone guessed wrong, which will be correct, if the other one did not submit a tip and false if the other one guessed wrongly. Hence, the negative results, collapse on particular cases and the positive ones survive.

The following set of rules produces the 12/16 result listed below:
1) If A sees 3x the same color, he guesses "black"
2a) If A has a white hat, B, C, and D know that A can only be wrong if they have all the same color, so if they see the same color twice they guess the opposite color.
2b) If A has a black hat and B sees that C and D have black hats, B guesses 'black' otherwise he doesn't guess at all.
3a) If A and B have black hats, C and D guess "black", if they see that the other one has a white hat.
3b) If A has a black hat and B a white one, C and D guess "white", if they see that the other one has a black hat.

Hat Color |  Guess  | Correct?
 A B C D  | A B C D |
 b b b b  | b b     | Yes
 b b b w  |     b   | Yes
 b b w b  |       b | Yes
 b b w w  |     b b | No
 b w b b  | b b w w | No
 b w b w  |       w | Yes
 b w w b  |     w   | Yes
 b w w w  | b       | Yes
 w b b b  | b w w w | No
 w b b w  |       w | Yes
 w b w b  |     w   | Yes
 w b w w  |   b     | Yes
 w w b b  |   w     | Yes
 w w b w  |     b   | Yes
 w w w b  |       b | Yes
 w w w w  | w b b b | No

[mith]

Yep, that will work. You approached this a little differently than I did, but it's the same idea:

The trick here is that there is necessarily an equal number of right and wrong answers, but you can set things so that the wrong answers are all clumped together under the same few hat arrangements while the right answers are spread out. The general idea for the solution then is to select some number of "bad" arrangements, where all the other ("good") arrangements differ by 1 hat from at least one of the bad sets, with the rule "If you see that the other three have hats corresponding to one of the bad arrangements, guess the opposite color from what your hat is in that arrangement", which leads to everyone guessing wrong on those, while at least one guesses right on all the others.

We have a general upper bound of n/(n+1) - 4/5 in this case - because the total number of right and wrong answers must be the same. For example, we can't survive 13 of the cases here, because we would need 13 right answers and 13 wrong answers, but with 3 bad cases left there are only 3*4 wrong answers available.

The simplest way to do it with 4 - and this is where the hint came in - is to ignore one of the people entirely and just consider the other three, because with 3 you can also achieve a 3/4 success rate. (Apparently, in the more general problem you can reach the upper bound of n/(n+1) if n = 2^k-1 for some k, by using the corresponding Hamming code.)

Rule: Ignore the fourth person. Among the remaining three, if anyone sees two like hats, guess the opposite.

(This is basically ghostofmars' rule 2a, but applied to both halves of the problem by ignoring A entirely.)

[Jack Rudd]

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

I've got some of the way, but I can't seem to get further off the top of my head.


OK, assuming that Arthur, John and William are the men, and Beatrice, Helen and Marguerite the women, what do we have?

Suppose the sister of Mr White is Beatrice. Then Mr White cannot be Arthur (because Arthur's sister isn't Beatrice), nor can he be William (because William is William Black), so he is John. Thus the men are Arthur Brown, William Black and John White. Also, Beatrice is not married to Helen's brother (because Mr White's sister is married to the brother-in-law of Helen's brother), so must be married to Marguerite's brother. Thus Marguerite is married to Helen's brother and Helen to Beatrice's brother - but this would make Helen Mrs White, when we already know Marguerite is Mrs White.

Therefore the sister of Mr White is Helen. (This fits in with her date of birth - 26 weeks before a date in August is nearly always a date in January.) Now who is Mr White? Suppose he's John. In that case, John is the brother of Helen, Arthur the brother of Marguerite and William the brother of Beatrice. This would in turn imply that John is married to Marguerite, Arthur to Beatrice and William to Helen. In which case the women are Marguerite White, Helen Black and therefore Beatrice Brown.

Alternatively, Mr White could be Arthur. In which case our men are Arthur White, John Brown and William Black. Arthur married Marguerite and his sister is Helen, so the man who married Beatrice has Marguerite as a sister and the man who married Helen has Beatrice as a sister.

[pacovf]

You are globally right, yes. The end of the puzzle is somewhat more subtle though.

[Axxle]

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.

Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.

I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

Granted, once you reach 49 you're pretty likely to be safe... but there is a way to be sure.It's still your basic answer; just with a minor change.

Have each regular maiden signal twice instead of just once. Master maiden counts to 99 instead of 49.

Right.

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

[eHalcyon]

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

[pacovf]

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

That's the problem: no maid can be sure that she's the first to be taken to the switch room.

[Axxle]

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

That's the problem: no maid can be sure that she's the first to be taken to the switch room.

Doesn't matter As long as there's at least one a day, you can declare Day 1 as off switch day.

[eHalcyon]

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

That's the problem: no maid can be sure that she's the first to be taken to the switch room.

Doesn't matter As long as there's at least one a day, you can declare Day 1 as off switch day.

Right.  I'd actually thought about that but I made different assumptions based on the initial presentation of the puzzle.  But I can see how you might arrive at different assumptions.  For your solution to work, the following assumptions must be made:

At least 1 maid is taken each day.
The maids are aware of what day it is.
More specifically, they need to know when it is day 1, and at least one maid must be taken on day 1 in order to do the initial setting.

[jotheonah]

Somehow this thread moved from "fun logic puzzles" to "math people speaking another language."

But I remember learning about the Axiom of Choice in one of my philosophy classes. I just can't for the life of me remember what it is. Anyone want to venture a layman's explanation?

[theory]

It's just another term for mathematicians' most preferred axiom at any given time.  (Since given any number of axioms you can always come up with a most preferred axiom.)

[DStu]

But I remember learning about the Axiom of Choice in one of my philosophy classes. I just can't for the life of me remember what it is. Anyone want to venture a layman's explanation?

The Axiom of Choice tells you that when you have a set of sets, that there exists another set which contains exactly one element of each of these sets.  So say you have {{0,1,2},{4,2,1},{5,3,1}}, there exists a set which has exactly one elementof {0,1,2}, one of {4,2,1} and one of {5,3,1}.

With these example this seems quite obvious, and indeed it is.  But if you have more and larger sets, like infintely many infinite large sets, then this is not so clear anymore.  Or better, it maybe looks like that should be true, but it doesn't follow from the other axioms one uses so far (Otherwise one wouldn't need another axiom).

The famousness of AC is that it is somehow on the edge of reasonablefullness.  That is, while if you assume it is false, you get some unreasonable results (most known maybe that there exists Vectorspaces without a basis), it itself implies some unreasonable results (most known maybe the Banach Tarksi Paradox , telling you that you can decompose a ball into subsets, than move and rotate these and end up with two balls).

Therefore, the AC is the most controversial of the usually used axioms, which means that everybody outside of maybe logic and set theory just uses it, when they need (Which is not that often at least explicitely, but as said, it comes in disguise sometimes like with the basis of Vectorspaces)  But I think in these fields people care more, and also historically it was a bit disputed.

[ghostofmars]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

If my calculations are correct, skip the first 37 and then take the next one, which exceeds all prior suitors. I get 37.1% chance to find the best suitor in this fashion.

[Watno]

The Axiom of Choice tells you that when you have a set of sets, that there exists another set which contains exactly one element of each of these sets.  So say you have {{0,1,2},{4,2,1},{5,3,1}}, there exists a set which has exactly one elementof {0,1,2}, one of {4,2,1} and one of {5,3,1}.

It doesn't quite work that way. Suppose you have {1}, {2} and {1,2}. Then there is no set that contains exactly one element of each set. You neeed to take an indexed family of sets, and then you get an indexed family of elements.

[jotheonah]

That was enough to jog my memory, thanks.

[theory]

Hence the famous joke:

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"

The Axiom of Choice is intuitive, but implies the well-ordering theorem which is not, and implies Zorn's lemma, which is too advanced for Earthlings to have an intuition about.

[jotheonah]

Sometimes you have to recognize that there's a level of geek you will never achieve. But I do feel like you guys make me smarter, too. I was really proud of myself when I figured out the blue eyes thing well enough to explain it to a friend.

[theory]

Here's a logic problem:


How many times is 0 a correct answer to this puzzle?
How many times is 1 a correct answer to this puzzle?
How many times is 2 a correct answer to this puzzle?
How many times is 3 a correct answer to this puzzle?
How many times is 4 a correct answer to this puzzle?
How many times is 5 a correct answer to this puzzle?
How many times is 6 a correct answer to this puzzle?
How many times is 7 a correct answer to this puzzle?
How many times is 8 a correct answer to this puzzle?

(The answer is unique.)

[Galzria]

Here's a logic problem:


How many times is 0 a correct answer to this puzzle?
How many times is 1 a correct answer to this puzzle?
How many times is 2 a correct answer to this puzzle?
How many times is 3 a correct answer to this puzzle?
How many times is 4 a correct answer to this puzzle?
How many times is 5 a correct answer to this puzzle?
How many times is 6 a correct answer to this puzzle?
How many times is 7 a correct answer to this puzzle?
How many times is 8 a correct answer to this puzzle?

(The answer is unique.)

Gut instinct says One, since the statement "1 is the answer to this puzzle" is true exactly "1" time. If the statement "4 is the correct answer to this puzzle" were to be true, then it would still only be true exactly "1" time.

Perhaps that's poorly explained, but it's what I instinctively see.

[jotheonah]

How many times is 0 a correct answer to this puzzle?

Isn't this a paradox (not unlike "This sentence is a lie")?

Assume that 0 is never a correct answer. Then the correct answer would be 0.
Assume that 0 is sometimes a correct answer. Then the correct answer would never be 0.
So the answer can neither be 0, nor can it be anything else.

[theory]

The answer isn't a single digit, it's a series of digits.  The goal is to come up with the 9 answers that are internally consistent.

[jotheonah]

But the very first one seems to be inherently unanswerable.

[Rabid]

How many times is 0 a correct answer to this puzzle? 5
How many times is 1 a correct answer to this puzzle? 2
How many times is 2 a correct answer to this puzzle? 1
How many times is 3 a correct answer to this puzzle? 0
How many times is 4 a correct answer to this puzzle? 0
How many times is 5 a correct answer to this puzzle? 1
How many times is 6 a correct answer to this puzzle? 0
How many times is 7 a correct answer to this puzzle? 0
How many times is 8 a correct answer to this puzzle? 0

[Jack Rudd]

Here's a logic problem:


How many times is 0 a correct answer to this puzzle?
How many times is 1 a correct answer to this puzzle?
How many times is 2 a correct answer to this puzzle?
How many times is 3 a correct answer to this puzzle?
How many times is 4 a correct answer to this puzzle?
How many times is 5 a correct answer to this puzzle?
How many times is 6 a correct answer to this puzzle?
How many times is 7 a correct answer to this puzzle?
How many times is 8 a correct answer to this puzzle?

(The answer is unique.)

At least one of {4, 5, 6, 7, 8} has a nonzero answer. Otherwise there would be at least five times that 0 was a correct answer, leading to a contradiction. However, no two of them can each have a nonzero answer. If they did, the pair that did would have to be 4 and 5 (as any other pair would immediately sum to more than 9), but then, even with 5 0s and 4 1s, there couldn't be four numbers that appeared once.

Thus exactly one of {4, 5, 6, 7, 8} has a nonzero answer, and that number is the number of times 0 appears. By the same logic as before, it has to be exactly 1 (because otherwise we end up with, at a minimum, two 4s and a 2 adding up to 10). Therefore there exists at least one 1 - and exactly one 1 would lead to a contradiction in the 1s themselves, so there must be at least two 1s.

This gives us: A 0s, where A is at least 4.
B 1s, where B is at least 2
At least 1 B
Exactly 1 A

These add up to 8, so we have scope for increasing A or B beyond the minimum. Increasing B to 3 would cause an extra 1 to come in as well, so there is no room for it, but we can increase A to 5 with no problem. Thus:

How many times is 0 a correct answer to this puzzle? 5
How many times is 1 a correct answer to this puzzle? 2
How many times is 2 a correct answer to this puzzle? 1
How many times is 3 a correct answer to this puzzle? 0
How many times is 4 a correct answer to this puzzle? 0
How many times is 5 a correct answer to this puzzle? 1
How many times is 6 a correct answer to this puzzle? 0
How many times is 7 a correct answer to this puzzle? 0
How many times is 8 a correct answer to this puzzle? 0

[soulnet]

I'm going to guess 521001000, although if I read literally, it does not seem correct. Maybe "How many times is 0 in a correct answer to this puzzle?" is clearer? Or I misinterpreted this?

BTW, search for self describing sequence or Golomb's sequence or similar for LOTS of problems on this sort of thing.

Ninja'd.

[Galzria]

Here's a logic problem:


How many times is 0 a correct answer to this puzzle? 5
How many times is 1 a correct answer to this puzzle? 2
How many times is 2 a correct answer to this puzzle? 1
How many times is 3 a correct answer to this puzzle? 0
How many times is 4 a correct answer to this puzzle? 0
How many times is 5 a correct answer to this puzzle? 1
How many times is 6 a correct answer to this puzzle? 0
How many times is 7 a correct answer to this puzzle? 0
How many times is 8 a correct answer to this puzzle? 0

(The answer is unique.)

521001000?

Starting from "000000000" and going forward - although maybe I mixed up a step along the way and didn't go quite far enough? But I think I've got the general spirit of it down, if not the correct answer.

[Galzria]

Seems I was ninja'd by 3 people in the 5 minutes I wrote that up.

But if all 4 of us came to the same conclusion, I've got to believe it's correct.

[jotheonah]

Oh, now I get how it works it's a fun puzzle.

[jotheonah]

I just found this one on wikipedia:
http://en.wikipedia.org/wiki/Zebra_Puzzle

Have not worked it out yet, looks fun to solve

[Jimmmmm]

I just found this one on wikipedia:
http://en.wikipedia.org/wiki/Zebra_Puzzle

Have not worked it out yet, looks fun to solve

I started this this morning and finally have an answer (I did other stuff too!).

My solution, before checking:

The Norwegian drinks water, and the Japanese owns the zebra.

Checking... Hooray!

[DStu]

@infinite hats:

Again we have here that everybody guesses wrong in 1/2 of the cases.  This also implies that on average, there are infinitely many people guessing wrong.
Now it's still possible that this is the case when just finitely many people guessing wrong in every case. For example, you can have person 1 guessing wrong in always, person 2 and 3 guessing wrong in 1/2 the cases, 4-7 in 1/4 and so on, so that you have like 2ˆn person guessing wrong in 1/2ˆn of the cases.  This would always be finite,  but with infinite mean.

But I don't the how to do this, we had like 1/2ˆn in the riddle with the 4 hats, but there everybody sees everyone else hats, and they didn't had to guess...

I don't see any method how to guarantee that the guesses are coupled in this sense here, so that one person guessing wrong/right implies that one other person is also wrong/right.

[qmech]

Again we have here that everybody guesses wrong in 1/2 of the cases.  This also implies that on average, there are infinitely many people guessing wrong.

This is a nice comment that I haven't seen before.

[fractic]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

If my calculations are correct, skip the first 37 and then take the next one, which exceeds all prior suitors. I get 37.1% chance to find the best suitor in this fashion.

That is indeed correct. In general the princess should reject the first 1/e part of the suitors, where e=2.71..., Euler's number. Here's the proof:

Assume there are n suitors and that the princess will reject the first k of them and then pick the
first suitor that is better than all the previous ones. The chance she'll find the best is
P(princess finds best suitor) = \sum_i=1 to n P(princess chooses suitor i| suitor i is best) x P(suitor i is best)
= \sum_i=1 to k 0 x 1/n+\sum_i=k+1 to n P(best suitor before i was one of the first k) x 1/n
= \sum_i=k+1 to n k/(i-1) x 1/n = k/n x \sum_i=k+1 to n 1/(i-1) = k/n x (1/k + 1/k+1 ... +1/(n-1))

We can approximate this sum by log(n-1)-log(k-1) = log( (n-1)/(k-1) ) ~=~ log(n/k) = - log(k/n).
So the princes has -k/n x log(k/n) chance of finding the best suitor. The function f(x) = -x log(x) has a maximum at x = 1/e and this maximum is also 1/e.

[pacovf]

If any of you lack the capacity to solve problems involving infinitely countable hats (I know I do), here's one of my favourite puzzles (this one is by Raymond Smullyan; I had to retranslate the version I have, so sorry if the English is wonky):

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

I don't know if anyone will try to solve this one or not, but just in case, here's a hint that normally should get you to the answer:
The date is relevant.

[theory]

John's girlfriend lives at one end of town. His mother lives at the other. John gets off work at a random time between 5 p.m. and 6 p.m. He always visits either his girlfriend or his mother after work.  Mindful that he hasn't been spending enough time with his mother, he comes up with a new policy: he takes the first train that he sees when he leaves work.  Since both trains run exactly every ten minutes, he figures that this should be a good random way to visit both of them equally. 

A month later, Mom complains. She says that John has visited his girlfriend 27 out of 30 times this month.  John says it is just by chance, and that he has been following his policy of randomly getting on the first train he sees. 

Provide a logical explanation for this discrepancy, assuming that everyone is telling the truth and that the sample size is large enough. 

[Drab Emordnilap]

Clearly, the Mom train comes one minute before the Girlfriend train.

[Watno]

You mean after.

[Drab Emordnilap]

Yes, that's what I actually mean.

[pacovf]

Timetable: N, 5:09 | S, 5:10 | N, 5:19 | S, 5:20| N, 5:29 | S, 5:30 | N, 5:39 | S, 5:40 | N, 5:49 | S, 5:50 | N, 5:59 | S, 6:00 ; or something equivalent.

Gaah, ninja'd three times.

[Watno]

Though actually, that makes no sense, since there is no information about any corellation between the train he takes and who he visits.

[eHalcyon]

John's girlfriend lives at one end of town. His mother lives at the other. John gets off work at a random time between 5 p.m. and 6 p.m. He always visits either his girlfriend or his mother after work.  Mindful that he hasn't been spending enough time with his mother, he comes up with a new policy: he takes the first train that he sees when he leaves work.  Since both trains run exactly every ten minutes, he figures that this should be a good random way to visit both of them equally. 

A month later, Mom complains. She says that John has visited his girlfriend 27 out of 30 times this month.  John says it is just by chance, and that he has been following his policy of randomly getting on the first train he sees. 

Provide a logical explanation for this discrepancy, assuming that everyone is telling the truth and that the sample size is large enough.

WLOG, suppose that John's girlfriend lives in the east and his mom lives in the west.
This discrepancy may be explained if the train runs back and forth on a straight line and John works in the east as well:

Mom -----------------------John--Girlfriend

When John arrives at the station, it is more likely for the next train to be heading east.  Even though they both run every 10 minutes, it does not mean the trains arrive 5 minutes apart.  From John's station, trains will arrive from the west, run east for another station or two, then turn around and come back.  The window of time between arrivals is different.

My explanation here is probably not very clear, but you can look up the Elevator Paradox, which is the same idea going vertical.

[eHalcyon]

I suppose the 1 minute explanation is better because it matches up with the 27/30... I still like my explanation more.

[Watno]

I'm surprised I didn't know the english expression for WLOG before, I just knew the German OBDA

[Tables]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

[eHalcyon]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

Now try making 24 with just four zeros! You may use more complicated functions like trig functions, exponents, logarithms. Anything on a standard scientific calculator, excluding shortcut functions with other numbers like x^2.

[bozzball]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

Now try making 24 with just four zeros! You may use more complicated functions like trig functions, exponents, logarithms. Anything on a standard scientific calculator, excluding shortcut functions with other numbers like x^2.

((0!+0!)^(0!+0!))!

[Jimmmmm]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

Now try making 24 with just four zeros! You may use more complicated functions like trig functions, exponents, logarithms. Anything on a standard scientific calculator, excluding shortcut functions with other numbers like x^2.

((0!+0!)^(0!+0!))!

Or even just (0!+0!+0!+0!)!

[Ozle]

What?
Explain please

[Jimmmmm]

0! = 1. So (0!+0!+0!+0!)! = 4! = 4*3*2*1 = 24.

[Ozle]

0! = 1. So (0!+0!+0!+0!)! = 4! = 4*3*2*1 = 24.

Yeah, i assumed that meant 1, but why?

[theory]

http://en.wikipedia.org/wiki/Factorial#Definition

http://www.zero-factorial.com/whatis.html

It depends on how you define 0!, and it turns out that the most consistent, most logical, and most convenient (if not most immediately intuitive) definition of 0! is 1

[Grujah]

0! = 1. So (0!+0!+0!+0!)! = 4! = 4*3*2*1 = 24.

Yeah, i assumed that meant 1, but why?

Well, it just is.

I assume, cause for each n, you can n! = (n-1)! * n.  i.e. 5! = 4! * 5. So, to maintain 1! = 0! * 1, 0! needs to be 1.

[Drab Emordnilap]

Basically, x!, or "X Factorial", asks "Given x items, how many unique orders can they have, if put in a line?"

So, 2! = 2, AB or BA.

3! = 6, ABC ACB BAC BCA CAB CBA

1! is trivial, A.

How many arrangements can 0 objects have? One unique arrangement, in fact: ∅

Also,

4!/3! = 4
3!/2! = 3
2!/1! = 2

And we all know how mathematicians love patterns.

1!/0! = 1

Therefore, 1! = 0!

[Ozle]

Just because its true for one set of numbers, doesn't make it true for 0!

This seems a major assumption without any proof!
(Will read the wiki later though...)

This sounds like one of those things everybody agrees on and makes it a big joke on Ozle again!
Yeah, lets all pretend 0! = 1 to Ozle, hahaha
Its like that time they told me that the end of year prom was cancelled, or they didn't let people with glasses onto Busses for health and safety reasons. Or that time you could get shoes that fasten without laces!

Yeah, lets all laugh at Ozle!

[Drab Emordnilap]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

[Watno]

If you don't like it, do (cos(0)+cos(0)+cos(0)+cos(0))!
Anyway, how would you define a faculty?

[Jimmmmm]

0! = 1. So (0!+0!+0!+0!)! = 4! = 4*3*2*1 = 24.

Yeah, i assumed that meant 1, but why?

Convention. It's the most sensible and useful definition, so it's the one we use.

[DStu]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

(14-6)x3

[eHalcyon]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

(14-6)x3

I think combining 1 and 4 to make 14 is not allowed within the problem parameters.


This exercise can actually be played as a card game with a regular deck of cards.  I am terrible at this game.

[ConMan]

http://en.wikipedia.org/wiki/Factorial#Definition

http://www.zero-factorial.com/whatis.html

It depends on how you define 0!, and it turns out that the most consistent, most logical, and most convenient (if not most immediately intuitive) definition of 0! is 1

I define factorial as the Gamma function, translated by 1 and restricted to integers, from which 0! = 1 is an automatic consequence.

[Drab Emordnilap]

I define factorial as the Gamma function, translated by 1 and restricted to integers, from which 0! = 1 is an automatic consequence.

I define factorial as me yelling at numbers until they're the numbers I want them to be.

[dondon151]

This exercise can actually be played as a card game with a regular deck of cards.  I am terrible at this game.

The one thing that I can't do with this game is working with fractions.

[Tables]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

(14-6)x3

I specifically say numbers, not digits, to avoid this kind of thing. Still I didn't realise that way was also possible.

Also surprised eHalc got the solution so quickly, all things considered...

[eHalcyon]

Not so much a logic problem, but a fun problem anyway:

Using each of the numbers 1, 3, 4 and 6, each exactly once, as well as any number of +, -. x and ÷ as well as brackets, make the number 24.

I think there's only one solution, and it took me at least 40 minutes to find

6/(1-3/4)

(14-6)x3

I specifically say numbers, not digits, to avoid this kind of thing. Still I didn't realise that way was also possible.

Also surprised eHalc got the solution so quickly, all things considered...

I've seen the same type of problem before, where the trick is to use fractions in that manner.  And a friend asked that kind of problem of me only about a month ago, so it was kind of fresh in my memory.

[Axxle]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

0!/(-1)! =

[ConMan]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

0!/(-1)! =

Hence why factorial is defined only on the natural numbers, and the gamma function has essential singularities at the negative naturals.

[Axxle]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

0!/(-1)! =

Hence why factorial is defined only on the natural numbers

So why is it defined for zero?

edit: I guess 0 is a natural number in some circles

[ConMan]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

0!/(-1)! =

Hence why factorial is defined only on the natural numbers

So why is it defined for zero?

edit: I guess 0 is a natural number in some circles

Yeah, I think we've had this discussion on this board already (although I didn't chime in), but I count natural numbers as the set {0, 1, 2, ...}. So n! is defined for n = 0, 1, 2, ... only, whereas Gamma(x) is defined for all complex x except x = 0, -1, -2, ... But Gamma(n+1) = n! which is why there's a difference between where they work.

[DStu]

Just because its true for one set of numbers, doesn't make it true for 0!

1337!/1336! = 1337

58008!/58007! = 58008

3720!/3719! = 3720

0!/(-1)! =

Hence why factorial is defined only on the natural numbers

So why is it defined for zero?

edit: I guess 0 is a natural number in some circles

I don't think it is some ideological what is a natural number thing.
It is just that the factorial is probably most often used as "how many ways can you order a n element set" (including n chose k), and there the answer for 0 is 1. And you need to define 0! tO have the usual definnition dor n chose 0 and n chose n work.  And beside that mathematicians like to define things as broad as possible as long as there is some "natural" way to do it, and here it fits nicely into the recursive definition.

[Axxle]

Ok, that makes more sense.

[theory]

Back on topic: relevant SMBC:

[pacovf]

Avid reader, huh? That one's fresh.

[eHalcyon]

Don't forget the bonus:

[DStu]

I don't want to be impatient, but how does the puzzle with the infinite hats work?

[qmech]

I'll do the version where the people are labelled 1, 2, 3, ... and everybody knows which position they are in.  Generalising to other cases is still an interesting problem.  I repeat my warning that if you're a mathematics student you should resist the temptation to read the answer.

Define an equivalence relation on the set of hat colourings by saying that two colourings are equivalent if they differ in only finitely many places.  Choose a representative R(E) for each equivalence class E.  Everyone can see all but finitely many hats, so can determine which equivalence class E they are in.  Have everybody guess the colour their hat would be in the colouring R(E).  The actual colouring is equivalent to R(E), so only finitely many people will guess wrong.

For those who aren't familiar with them, equivalence relations aren't scary at all.  They're just a convenient way to describe breaking a set into pieces: two objects are in the same piece if and only if they are equivalent.

The possible generalisations are to the cases where people don't know which number they are, and where the places are indexed by Z instead of N (people can still only see in the "positive" direction).  I'm not claiming that all of these are doable.

[DStu]

Define an equivalence relation on the set of hat colourings by saying that two colourings are equivalent if they differ in only finitely many places.  Choose a representative R(E) for each equivalence class E.  Everyone can see all but finitely many hats, so can determine which equivalence class E they are in.  Have everybody guess the colour their hat would be in the colouring R(E).  The actual colouring is equivalent to R(E), so only finitely many people will guess wrong.

Hmm, that seems to simple to work.  But somehow...

[Asper]

How about a Puzzle without infinity, hats, or untimely death?

You have 12 bowls. All look the same. One is either heavier or lighter than the others, but the remaining ones weight the same.
All you have is a pair of scales, so you can compare any two sets of bowls on their weight. You may only do this 3 times, though.
Your task is to find out which bowl is different, and whether it's lighter or heavier than the others, or to prove this is impossible.

[Axxle]

How about a Puzzle without infinity, hats, or untimely death?

You have 12 bowls. All look the same. One is either heavier or lighter than the others, but the remaining ones weight the same.
All you have is a pair of scales, so you can compare any two sets of bowls on their weight. You may only do this 3 times, though.
Your task is to find out which bowl is different, and whether it's lighter or heavier than the others, or to prove this is impossible.

2^3 < 12
it's impossible. (I think I figured out a way to be accurate 66% of the time and have a 50/50 shot the last 33% of the time, but it's not 100%.

[DStu]

How about a Puzzle without infinity, hats, or untimely death?

Na, I don't like that.  How about:

You have 12 hats. All look the same. One is either heavier or lighter than the others, but the remaining ones weight the same.
All you have is a pair of scales, so you can compare any two sets of hats on their weight. You may only do this 3 times, though.
Your task is to find out which hat is different, and whether it's lighter or heavier than the others, or to prove this is impossible.

[Ozle]

Pretty sure it is doable.....

[DStu]

2^3 < 12
it's impossible. (I think I figured out a way to be accurate 66% of the time and have a 50/50 shot the last 33% of the time, but it's not 100%.

I'm not quite sure at the moment, maybe I only know the variante where you know if the one hat weights more or less, but the trick is that

3ˆ3 > 12

[Asper]

How about a Puzzle without infinity, hats, or untimely death?

You have 12 bowls. All look the same. One is either heavier or lighter than the others, but the remaining ones weight the same.
All you have is a pair of scales, so you can compare any two sets of bowls on their weight. You may only do this 3 times, though.
Your task is to find out which bowl is different, and whether it's lighter or heavier than the others, or to prove this is impossible.

2^3 < 12
it's impossible. (I think I figured out a way to be accurate 66% of the time and have a 50/50 shot the last 33% of the time, but it's not 100%.

Fun fact: My Math teacher tried to prove it's impossible when i was in school. Your proof is wrong.

[Asper]

How about a Puzzle without infinity, hats, or untimely death?

Na, I don't like that.  How about:

You have 12 hats. All look the same. One is either heavier or lighter than the others, but the remaining ones weight the same.
All you have is a pair of scales, so you can compare any two sets of hats on their weight. You may only do this 3 times, though.
Your task is to find out which hat is different, and whether it's lighter or heavier than the others, or to prove this is impossible.

Don't forget to mention the king will kill you if you can't do it.

[Ozle]

Yep, done it i think

[Asper]

Yep, done it i think

I'm curious to see your solution (preferably spoilered)

[eHalcyon]

I'm pretty sure I've solved this before.  Maybe it was a variant though.  I will try again.

[Ozle]

Yep, done it i think

I'm eager to see your solution (preferably spoilered)

Will do, pretty awkward to explain without a spreadsheet....

Involves weighing 4 v 4 balls

[Ozle]

Technically i remembered most of it rater than solved it

[Axxle]

Technically i remembered most of it rater than solved it

Are you sure then? I'm trying to work it out but the difficulty seems to be You don't know if the bowl-shaped hat is lighter or heavier.

[eHalcyon]

Technically i remembered most of it rater than solved it

Are you sure then? I'm trying to work it out but the difficulty seems to be You don't know if the bowl-shaped hat is lighter or heavier.

Yeah, I think you're right.  IIRC, it's very doable to find the counterfeit, but sometimes you can't determine whether it is heavier or lighter.

[eHalcyon]

Here is a partial answer for the easier scenario from initial weighing.  I've solved the other scenario in the past (caveat: can't remember if I was able to determine heavier or lighter) but I never remember it and it takes me a while to get it again.


Weigh 4 vs. 4
- if the two sides are the same, go to A
- if one side is heavier, go to B

A) The counterfeit is in the unweighed group of 4.  The other 8 are guaranteed real.  Weigh 3 of the potential counterfeits vs. 3 real.
- if the two sides are the same, go to AA
- if one side is heavier, go to AB

AA) The counterfeit is the one potential that you did not weigh.  Weigh it vs. 1 real to determine whether it is heavier or lighter.

AB) The counterfeit is in the group of 3 you just weighed and you know whether it is heavier or lighter.  Weigh 1 of them vs. another 1 of them.
- if the two sides are the same, the counterfeit is the one you did not weigh.
- if one side is heavier, you know which of the 2 is the counterfeit.

B) The counterfeit is among the 8 you weighed.  The other 4 are guaranteed real.

What now?

[Asper]

Here is a partial answer for the easier scenario from initial weighing.  I've solved the other scenario in the past (caveat: can't remember if I was able to determine heavier or lighter) but I never remember it and it takes me a while to get it again.


Weigh 4 vs. 4
- if the two sides are the same, go to A
- if one side is heavier, go to B

A) The counterfeit is in the unweighed group of 4.  The other 8 are guaranteed real.  Weigh 3 of the potential counterfeits vs. 3 real.
- if the two sides are the same, go to AA
- if one side is heavier, go to AB

AA) The counterfeit is the one potential that you did not weigh.  Weigh it vs. 1 real to determine whether it is heavier or lighter.

AB) The counterfeit is in the group of 3 you just weighed and you know whether it is heavier or lighter.  Weigh 1 of them vs. another 1 of them.
- if the two sides are the same, the counterfeit is the one you did not weigh.
- if one side is heavier, you know which of the 2 is the counterfeit.

B) The counterfeit is among the 8 you weighed.  The other 4 are guaranteed real.

What now?

If you would like to have that information, your solution so far is    right  .

[eHalcyon]

I know it is right so far.

I think I have the rest.  Just finalizing.

[DStu]

What now?

You have 4 potentially heavy (H) and 4 potentially light (L) hats. And four real (R)

You weight HHLL vs RRRL
a) equal: the C must be in the other HHL.  Weight HH, either one is heavier or it's the L.
b) HHLL is heavier.  Then it's HH from the right or L from the left, weight HH and see a)
c) HHLL is lighter.  Then it's LL, weight them.

[eHalcyon]

Here is what I had before:

Weigh 4 vs. 4
- if the two sides are the same, go to A
- if one side is heavier, go to B

A) The counterfeit is in the unweighed group of 4.  The other 8 are guaranteed real. 
Weigh 3 of the potential counterfeits vs. 3 real.
- if the two sides are the same, go to AA
- if one side is heavier, go to AB

AA) The counterfeit is the one potential that you did not weigh. 
Weigh it vs. 1 real to determine whether it is heavier or lighter.

AB) The counterfeit is in the group of 3 you just weighed and you now know whether it is heavier or lighter based on result A. 
Weigh 1 of the potentials vs. another 1 of the potentials.
- if the two sides are the same, the counterfeit is the one you did not weigh.
- if one side is heavier, you know which of the 2 is the counterfeit.

And here is the rest of it:

B) The counterfeit is among the 8 you weighed.  4 are "heavy" and 4 are "light" based on the initial result.  The other 4 are guaranteed real.
Weigh 2 "heavy" and 2 "light" (let this be side X) vs. 3 real and 1 "heavy" (let this be side Y).  Note that 2 "light" and 1 "heavy" are left out.
- if the two sides are the same, go to BA.
- if side X is heavier, go to BB.
- if side Y is heavier, go to BC.

BA) None of the ones you just weighed are counterfeit, so the counterfeit is either the single unweighed "heavy" or one of the two unweighed "light".
Weigh the two remaining "light" ones against each other.
- if they weigh the same, the unweighed "heavy" is the counterfeit.
- if one is lighter, that one is the counterfeit.

BB) The counterfeit is one of the two "heavy" you weighed on side X.  Weigh them against each other.  The one that is heavier is the counterfeit.

BC) The counterfeit is either the "heavy" you weighed on side Y or one of the two "light" you weighed on side X.  Weigh the two "light" ones against each other.
- if they weigh the same, the "heavy" is counterfeit.
- if one is lighter, that one is the counterfeit.

I don't think I made any mistakes, but no guarantees.


PPE: did I just get ninja'd in a much pithier solution?

[eHalcyon]

PPE: did I just get ninja'd in a much pithier solution?

Yeah I did.   I used an extra heavy instead of an extra light though!

[DStu]

PPE: did I just get ninja'd in a much pithier solution?

Don't mknow what "pithier" means, but it's the same solution (mod symmetries).

[eHalcyon]

PPE: did I just get ninja'd in a much pithier solution?

Don't mknow what "pithier" means, but it's the same solution (mod symmetries).

It means you were much more concise.

[Asper]

You are both right, of course. I'm curious DStu, did you remember or find out?

[DStu]

You are both right, of course. I'm curious DStu, did you remember or find out?

I dont know if i knew this variant at all or just the one where you knew if its heavier. Just renemvered splitting 4 4, and then just tried until it fits

[Asper]

You are both right, of course. I'm curious DStu, did you remember or find out?

I dont know if i knew this variant at all or just the one where you knew if its heavier. Just renemvered splitting 4 4, and then just tried until it fits

Cool. I recall i needed an entire day back then at school

[Avin]

If any of you lack the capacity to solve problems involving infinitely countable hats (I know I do), here's one of my favourite puzzles (this one is by Raymond Smullyan; I had to retranslate the version I have, so sorry if the English is wonky):

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

I don't know if anyone will try to solve this one or not, but just in case, here's a hint that normally should get you to the answer:
The date is relevant.

Oh interesting! Building from Jack Rudd's result then that Helen's brother is Mr. White:

The second bullet point basically just says "Mr. White's sister, Helen, who is married to her husband, got married on her January birthday."
The first bullet point says that Helen's husband was born in August, and they are 26 weeks apart in age.

Note that August 1st is exactly 26 weeks after January 31st, on a non-leap year. So Helen and her husband who were born on the same year, were not born on a leap year. John however, was born in 1868 according to point 5, which is a leap year, so John isn't Helen's husband.

Using that information, if Helen is Mrs. Brown, then we have Helen Brown née White, which means that the other two women must be Marguerite White née Black, and Beatrice Black née White. Since John isn't married to Helen, he must be Mr. White, leaving Arthur as Mr. Black. But this means Arthur's sister is Beatrice, which can't be the case since Arthur's sister must be taller than Beatrice.

So Beatrice must be Mrs. Brown.

[pacovf]

Oh interesting! Building from Jack Rudd's result then that Helen's brother is Mr. White:

The second bullet point basically just says "Mr. White's sister, Helen, who is married to her husband, got married on her January birthday."
The first bullet point says that Helen's husband was born in August, and they are 26 weeks apart in age.

Note that August 1st is exactly 26 weeks after January 31st, on a non-leap year. So Helen and her husband who were born on the same year, were not born on a leap year. John however, was born in 1868 according to point 5, which is a leap year, so John isn't Helen's husband.

Using that information, if Helen is Mrs. Brown, then we have Helen Brown née White, which means that the other two women must be Marguerite White née Black, and Beatrice Black née White. Since John isn't married to Helen, he must be Mr. White, leaving Arthur as Mr. Black. But this means Arthur's sister is Beatrice, which can't be the case since Arthur's sister must be taller than Beatrice.

So Beatrice must be Mrs. Brown.

Yes, that's the answer.

Props to you, good sir/lady! I wasn't able to solve it by myself when I first read it.

EDIT: Actually, John was born somewhere between 12th November 1967 and 11th November 1968, but it doesn't change your conclusion, since if he was Helen's husband, then he would be born during August 1968.

[jotheonah]

Oh interesting! Building from Jack Rudd's result then that Helen's brother is Mr. White:

Sorry, how did we get that?

[jotheonah]

that's actually a very cool puzzle. it depends on deduction hidden in seemingly irrelevant details.

[pacovf]

Oh interesting! Building from Jack Rudd's result then that Helen's brother is Mr. White:

Sorry, how did we get that?

He demonstrated that back in page 7.

[jotheonah]

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

I've got some of the way, but I can't seem to get further off the top of my head.


OK, assuming that Arthur, John and William are the men, and Beatrice, Helen and Marguerite the women, what do we have?

Suppose the sister of Mr White is Beatrice. Then Mr White cannot be Arthur (because Arthur's sister isn't Beatrice), nor can he be William (because William is William Black), so he is John. Thus the men are Arthur Brown, William Black and John White. Also, Beatrice is not married to Helen's brother (because Mr White's sister is married to the brother-in-law of Helen's brother), so must be married to Marguerite's brother. Thus Marguerite is married to Helen's brother and Helen to Beatrice's brother - but this would make Helen Mrs White, when we already know Marguerite is Mrs White.

Therefore the sister of Mr White is Helen. (This fits in with her date of birth - 26 weeks before a date in August is nearly always a date in January.) Now who is Mr White? Suppose he's John. In that case, John is the brother of Helen, Arthur the brother of Marguerite and William the brother of Beatrice. This would in turn imply that John is married to Marguerite, Arthur to Beatrice and William to Helen. In which case the women are Marguerite White, Helen Black and therefore Beatrice Brown.

Alternatively, Mr White could be Arthur. In which case our men are Arthur White, John Brown and William Black. Arthur married Marguerite and his sister is Helen, so the man who married Beatrice has Marguerite as a sister and the man who married Helen has Beatrice as a sister.

Quote tag is our friend here.