Brain Teasers and Maths Puzzles

[Zyx]

Okay, I think I see where you are going... Each of the two blue-eyeds would look at each other and assume that the Guru is referring to the other guy. Then, after the first night passes and neither of them has left, they will both realize that the other guy didn't leave because they made the same assumption. Then, both of them will leave on the second night.

Correct.

That works fine for two blue-eyeds, but I don't see how that can be extended to 100 blue-eyeds.

Easily. What happens if there are three blue-eyed guys?

It doesn't matter how many nights pass; each night, no one will leave, each blue-eyed person will always see 99 other blue-eyed people, and they will always continually assume that no one left because, with so many blue-eyed people around

Just like with the two blue-eyed person case, it does matter how many nights pass. The Guru does give additional information that the people did not have beforehand, once again, consider the case of the two blue-eyed guys. Remember that they do not know that the only options for eye colors are brown, blue and green. It is us only who know that there are 100 blue-eyed, 100 brown-eyed and 1 green eyed and 0 any other eye colors.

Sorry, Zyx. I still don't see how I can reach an answer from this.

You're so close.

[Tormuse]

(Is it safe to assume there's no trickery along the lines of individuals with one brown eye and one blue eye?)

That works fine for two blue-eyeds, but I don't see how that can be extended to 100 blue-eyeds.

Easily. What happens if there are three blue-eyed guys?

...

Oookaaay... I think I see what you're saying... and you just broke my brain...

If I'm understanding you correctly, then basically, what you're saying is that if there are three blue-eyed guys, then each blue-eyed guy will see two blue-eyed guys and each of them will consider the scenario that I described in my last post. If two nights pass, and neither of the other two blue-eyeds leaves, then each of the blue-eyed guys will come to the conclusion that there must actually be three blue-eyeds and that he himself is the third one. Then, all three of them will leave on the third night... This formula would then, theoretically, be extended for each further blue-eyed guy. If there were four, then all four would leave on the fourth night; if there were five, they'd all leave on the fifth night, and so on, up until the present case in which there are 100 people who will all depart together on the 100th night.

Is that really the answer?!? If it is, then I have an issue with it because I can already see a number of glaring logical flaws...

First of all, the whole premise of them having a 100 day countdown hinges on the fact that all of them would have the same start date for the countdown. Presumably, the start date for the countdown is supposed to be the day the Guru speaks, but there's no logical reason for it...

The Guru does give additional information that the people did not have beforehand...

No, she doesn't. Before she spoke, everyone on the island already knew that there were lots of blue-eyed people. After she spoke, they still knew the same thing. She didn't provide any additional information. This means that the day that she speaks is completely arbitrary and has no connection to the 100 day countdown that I outlined above. If these people really are perfect logicians, then they would know that there's no reason to start their countdown on that day, and so they wouldn't start it. Since no countdown takes place, no one leaves the island. Right?

...

Unless...

...

What if they all recognized the countdown concept years ago? What if everybody already left?

Hmm...

Okay, new theory!

What if the countdown started a while ago, long before the Guru spoke? (maybe the day they came to the island? Or maybe there was a specific day that they all simultaneously gained perfect logical ability?) Since there are an equal number of brown-eyed and blue-eyed people, they would have two simultaneous 100 day countdowns, and all 200 of them would leave on the 100th night. The only problem I see with this theory is... who is the Guru talking to, then? If everyone has already left, then how can she see someone with blue eyes?

...

@%^$&$&$

I think I'm gonna go play some mindless video games for a while before I overload my brain. Am I close to the answer, Zyx?

EDIT: Also, I feel sorry for the Guru. No matter what happens, she will always be left behind, because there's no way for her to deduce her own eye colour.

[Zyx]

Is that really the answer?!? If it is, then I have an issue with it because I can already see a number of glaring logical flaws...

That really is the answer. The solution is described here, even though it's pretty much the same as my hints.

Before you email me to argue or question: This solution is correct. My explanation may not be the clearest, and it's very difficult to wrap your head around (at least, it was for me), but the facts of it are accurate. I've talked the problem over with many logic/math professors, worked through it with students, and analyzed from a number of different angles. The answer is correct and proven, even if my explanations aren't as clear as they could be.

The Guru does give additional information that the people did not have beforehand...

No, she doesn't. Before she spoke, everyone on the island already knew that there were lots of blue-eyed people. After she spoke, they still knew the same thing. She didn't provide any additional information.

Oh, she does add information. Consider again the case of just two blue-eyed people. From day to day, both of them see 100 brown-eyed people, 1 blue-eyed guy and the Guru. Just based on this information, they cannot deduce their own eye color. Pick any date as a hypothetical countdown start, and after a night, the only thing the other guy can think is that "That other blue eyed guy didn't leave, so he hasn't figured out his eye color." It's only after the Guru spoke, that both of them can look at each other and think "That's the guy the Guru spoke of! If he can't see any blue-eyed people, he'll leave tonight. If he can see someone else, then... well... I have blue eyes as well!"

In any case, or even when all the blue-eyed guys have left, the brown-eyed people can't deduce their eye color.

EDIT: Also, I feel sorry for the Guru. No matter what happens, she will always be left behind, because there's no way for her to deduce her own eye colour.

Oh, the brown-eyed people are there with her. Unless she tells them that there is a brown-eyed guy among them.

[Tormuse]

I've read over the solution. I've also read over the first two posts of this thread that addresses the most common objections to the solution. I still disagree with the solution. I don't feel that the thread addresses my complaint about it.

Basically, what they're saying is that before the Guru spoke, each individual knew everyone else's eye colour, but didn't know that everyone else knew, and he didn't know that everyone else knew that everyone else knew, and he didn't know that everyone knew that everyone knew that... etc. ad infinitum... (In other words, it wasn't common knowledge) But after the Guru spoke, then everyone knew that everyone knew that... etc... And that's what started the countdown, because it became common knowledge.

Okay, I understand that, but it is easily countered by looking at two key statements in the first paragraph of the original puzzle:

"Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves)..." and "...Everyone on the island knows all the rules in this paragraph."

It says right there that "everyone knows" that people can see each other's eye colour. That means it's already common knowledge that blue eyes exist. That invalidates the statement that the Guru introduced new information to them. All the arguments of recursive logical inferences are irrelevant because the original puzzle states, "Everyone... knows..." I don't know how else you can interpret the phrase "everyone knows" except to mean that it is already common knowledge before the Guru speaks.





I have a lot of respect for Randall Munroe (the author of the puzzle) and I have a lot of respect for logic, but no matter how many logicians or mathematicians agree on this solution, it still seems logically flawed to me...

And now, I'm suddenly conscious of how obsessive I must seem right now. I humbly apologize to everyone for filling this thread with walls of text.





Umm... Maybe I should suggest a new puzzle... You have 12 marbles that have an identical appearance and all of them weigh the same except for one, which is either slightly heavier or slightly lighter than the rest. (You don't know which) You also have a balance scale. (I'm sure you know where this is going, but trust me, this one is trickier than the puzzle posted earlier in this thread) How can you determine which is the differently weighted marble (and whether it is heavier or lighter) in only three weighings?

[Zyx]

I've read over the solution. I've also read over the first two posts of this thread that addresses the most common objections to the solution. I still disagree with the solution.

This is what I enjoy most about this (and many other puzzles). The debate about the solution.

[Tormuse]

Okay, I'm glad you enjoy it. (I was worried that I was creating too much tedious reading) When I have more time, I'll read over more of the thread and share my conclusions.

EDIT: Also, I'll welcome any attempts at the puzzle I just posted above.

[eMTe]

Yours and Zyx's posts were too long for me to read, so dont worry, I didnt suffer reading them. But I think the guru puzzle is fine, Id just love to see a version that I wont have to reread five times only to find that I still dont understand it.

Now to the marbles.

Let's number the balls from 1 to 12.

I take balls 1,2,3,4,5,6 and put them on one scale (A) and I put balls 7,8,9,10,11,12 on second scale (B). For the purpose of this explanation I decided that ball number 10 is heavier than the rest, but this fact is officially unknown to me of course.

So I weigh both groups of balls and group B appears to be heavier. Then I switch randomly chosen three balls with three balls from other group.

Now, if I switch balls 1,2,3 with balls 7,8,9 nothing will change - scale B is still heavier, so I know that the ball I am looking for is either 10,11 or 12. If I switch balls 1,2,3 with 10,11,12 result is the same - I know that one of the balls 10,11,12 is heavier than the rest, because now scale A is heavier and balls which made it heavier must be 10,11 or 12.

I remove all balls except 10,11,12 and add one of the balls that are of normal weight, for example ball 1. I divide balls into two groups again, for example 1,10 and 11,12. Here things break, because third weighing will work only if ball 10 is the one I am looking for. But if I divide balls into 1,11 and 10,12 it wont work, because I will be left with scale B holding balls of which each one can be THE one.

At least I proved that my brain cells are working.

EDIT:

Me stupid. I dont add ball 1 or any other in step 3. I simply take two of the balls 10,11,12 and weigh them. If both weigh the same I know that the third one is heavier than the rest, if one is heavier...well.

D'oh!

[Pater Alf]

Now, if I switch balls 1,2,3 with balls 7,8,9 nothing will change - scale B is still heavier, so I know that the ball I am looking for is either 10,11 or 12.

But woudn't that conclusion only be correct if you already know that one marble is heavier than the rest? As long as you don't know, it could also mean that one of the marbles 4,5,6 is lighter (at least if I don't think completely wrong).

[Tormuse]

Pater Alf is correct.

Sorry, eMTe, your logic and reasoning were sound, (and your brain cells worked very well) but you missed one of the conditions of the puzzle: You don't know whether the odd ball is lighter or heavier. As Pater Alf said, in your suggested solution, after the second weighing, either 10, 11, or 12 is heavier, *or* 4, 5, or 6 is lighter. You don't know which. (I told you this one is harder!)

Try again; you were doing well!

[Zyx]

Hmm... what about first just weighting four and four balls. If the scale is balanced, the ball we are looking for is one of the four we didn't weigh. If the scale is not balanced, it's one of the eight. I think this is a quick to way eliminate at least some balls on the first weighing.

[eMTe]

This was my first, natural, approach, but there's no way you can eliminate 7 balls out of 8 in two weighings. Before 3rd weighing you must narrow your choice to 3 balls. Either that or this puzzle is tricky.

[Tormuse]

I first heard this puzzle about ten years ago and I have to confess that I'm having trouble remembering how to recreate the solution I came up with back then. The best that I can come up with at the moment gives me the full solution 11 out of 12 times, and the 12th time, I can deduce which one is the odd one, but not whether it's lighter or heavier. So, it's not perfect, but it is definitely always possible to find the odd ball in three weighings.

@Zyx, that was one of the things I considered in one of the early iterations of my solution. It's easy to eliminate a bunch of the balls with the first weighing. You're on the right track; just keep thinking about it.

[eMTe]

Are you sure the puzzle can be solved in 3 steps? Now, when I look at final step (3 balls) it got to me that one weighing isnt enough, because if you take two different balls you still dont know whether one is heavier or the other one lighter. So you need two weighings. TWO weighings for only 3 balls! And there are 12 balls in total!

[Tormuse]

There's definitely a solution. I just did a search and confirmed that there is a working, logical full solution that works for all possibilities. (I almost had it on my own; oh well...)

You're absolutely right that you can't tell whether the odd ball is heavier or lighter with the first weighing, but there is a way of rearranging the balls so you can narrow them down quickly with the second and third weighings. Think about it this way: Every time you weigh the balls, there are three possibilities... The scale will balance, the scale will tilt toward side A, or the scale will tilt toward side B. For each of the three weighings, you have to arrange the balls so that no matter what happens, you gain some information that narrows down the possibilities.

[Zyx]

I think I solved it, but I'm in the middle of a meeting so I don't have time to write out here. I believe the first weighting is with eight balls, four on each side of the scale?

[Tormuse]

That's right. I won't say any more until you get a chance to give the whole thing.

[Zyx]

Lunch time.

First weighting, you have four balls on each side of the scale. There are two possibilities,
Branch 1. The scale is balanced, meaning the ball we're after is in the four we didn't weigh
Branch 2. The scale is not balanced, meaning the ball is one of the eight on the scale.

Branch 1, second weighing we have one unknown ball (?) and one known normal (X) ball on the other side and two unknown balls on the other hand. There are two possibilities. We leave the fourth unknown ball aside.
Branch 1.1. The scale is balanced, meaning the ball we're after is the one we didn't weigh. And we can easily see wheter it is heavier or lighter by weighing it with any of the 7 balls we know are normal.
Branch 1.2. The scale is not balanced, meaing the fourth ball is normal. We have either two maybe-heavier (H) and one maybe-lighter (L) or the other way around.

Branch 1.2. The third weighing is HL on the other side and XX on the otherside. The third ball (H or L) is left aside. There are three possibilities.
Branch 1.2.1. The scale is balanced, so the ball we left aside is the odd one and what we thought it might be.
Branch 1.2.2. The HL side is heavier, so the H ball is the odd, heavier ball.
Branch 1.2.3. The HL side is lighter, so the L ball is the odd, lighter ball.

Branch 2. Second weighing, we put two L balls aside (we could as well put the H ones, then everything is just mirrored) and weigh XHHL on both sides of scale. There are three possibilities.
Branch 2.1. The scale is balanced, meaning one of the L balls we left aside is the ball we're after, and it's lighter. We weigh either one against a known normal ball and if it balances, it's the other ball, and if not, it's the one we weighed.
Branch 2.2 and 2.3. The scale is not balanced. We pick the two H balls from the heavier side and the on L ball from the ligher side. Neither of the H balls on the lighter side can be heavy and the L ball on the heavy side can't be lighter. The ball we left aside has to be a normal ball. So, now we have only two H balls and one L ball left and we can use the same weighting as in Branch 1.2 to find out the ball we're after.

Edit: There's no reason to use known normal balls (X) in Branch 2 weighing. I just forgot them from my earlier iteration.

[Pater Alf]

Seems to be an interesting meeting if you have time to solve such kind of puzzles while you're in it...

But the solution seems to be correct as far as I can see.

[Zyx]

Seems to be an interesting meeting if you have time to solve such kind of puzzles while you're in it...

Yep. I would have died of boredom without this puzzle, a piece of paper and a pencil.

[Tormuse]

Well done, Zyx!

The coolest part of this is it's slightly different from the solution I came up with! (And I just looked and they're both different from the solution on the website!)

The different bit from what I came up with: For Branch 1.2, if there are 2H and 1L, I would put an H on each side. If they balance, the one left over is the odd one and it's lighter. If they don't balance, the heavier side has the odd one and it's heavier. (H's and L's are reversed if it was 2L and 1H)