Brain teasers, puzzles and the like...

EddieDean

So, once a year my extended family and I all go down to my uncle's house in Bath to celebrate Christmas a month early.

Without fail, at least once per gathering someone brings up a puzzle or brain tease or whatever, and we spend an hour or so trying to solve it.

So, I open to the floor a request: Share with me your best brain teasers, such that this early-Christmas will be fun.

A couple of rules:
1) Please, spoiler ALL solutions. Give people a chance to work puzzles out on their own first. Mark solutions in spoilers as SOLUTIONS, and any clues in spoilers as CLUES.
2) Give some kind of identifier for your puzzle as it's name. Whenever you refer to someone else's, refer to it in bold and by that identifier. This'll make it easier to follow the conversations about certain puzzles.
3) Please try to avoid riddles and wordplay. I'm more interested in puzzles which might take a bit of to-and-fro, some discussion and pen and paper to work out. Picture-based ones are good too. I'll provide some examples.

I'll start you off with one that I've had a previous year, which we still revisit as people still get confused. This'll probably cause a load of arguing in this thread too, but hey:
Three-door gameshow puzzle:
So, you're in a gameshow. You have three doors in front of you, behind which one has a prize and two have nothing. You are asked to select one door, but you do not get to see what's behind it yet. Then, the host will open one door which has nothing behind it (of the two which remain), leaving one with the prize, and one with nothing. Your initial selection remains, and you are asked if you want to change your selection to the other door, before the door is opened and your prize (or not) is revealed.
The question is: Do you stay, or change? Why? What are the odds?
I'll leave the solution to that one until people've had a chance to think about it.

Missing square in a triangle puzzle:

Both of these triangles are made up of the exact same shapes, just reconfigured. So where does that gap in the lower one come from?

3, 2, 1.. GO!

gundam470

Oh boy, did you have to bring up the Monty Hall problem?

Richy

What happened to spoilering solutions? :P

A classic one: the infinite hotel. You can dress it up as you want to make it a nice story for your family, but the basic point is: you have a hotel with an infinite number of rooms, all occupied, and you want to fit in more people. How do you do it?

You ask each person in each room to move to the room with the double of their current room number. That way, every odd-numbered room will be free.

So It Goes

gundam470 wrote: »

Oh boy, did you have to bring up the Monty Hall problem?

Yeah everyone knows the answer to that one.

Polity

SO EXCITED

Thread promises.

My contribution: If you drill a hole directly through a sphere, leaving a ring of six inches' width, what is the remaining volume?

Yes, there is enough information.

36 π. The radius of the sphere is irrelevant. Consider the extreme case: a sphere of radius 3 inches, which will have a six-inch deep hole of infinitesimal (effectively zero) width. The volume then is the volume of the sphere, or (4/3)π r^3. Pi looks goofy

Feral

I see your Monty Hall problem and raise you an airplane on a conveyor belt.

Gosling

Your triangle problem solution...

The diagonal of the square. A bunch of teeny tiny slivers at the top of Triangle 1 get lumped together into one whole square in Triangle 2.

garroad_ran

I just heard this one today.

Take a chessboard or checkered board of 5x5.

You are to place five white queens and three black queens on this board such that no queen can attack one of the opposite color in a single move.

I can post the solution if anyone really wants me to, but it would involve drawing and uploading a picture, which is a bit of a hassle for me since I have to switch computers to do so. I'll post the solution if anyone asks for it.

Raiden333

There is an island that is considered to be paradise. All the inhibitants of the island are Perfect Logicians, and every knows of every that they are Perfect Logicans.

Exactly 100 of these persons have blue eyes, 100 have brown eyes, and 1 has green eyes. The inhibitants do not know what his/her color eyes is. Everyone is constantly aware of everyone elses eye color but no person knows that there are 100 blue eyed, 100 brown eyed, and 1 green eyed person on the island.

If a person finds out his/her own eye color she/he must leave the island at midnight of the day she/he finds out! There are no mirrors or reflections of any kind on the island. Also, nobody on the island ever speaks except the Guru, who is the person with the green eyes, (she does not know her eye color and if she found out she would have to leave the island at midnight). The Guru says one sentence every fifty years. One day the Guru arrives and tells everyone on the island the following: “I SEE SOMEONE WITH BLUE EYES.”

Who (if anyone) leaves the island and when?

I'll be back to clean up when you're all done killing each other in 5 pages when the arguments heat up.

Donkey Kong

The triangle one is great because

people are so bad at judging exact angles. Our brains snap to the nearest ideal far too easily. The angle of the left tips of the blue and red triangles are not the same, meaning the triangle's hypotenuse is effectively bowed inward on the first shape and outward on the second. That's enough to account for the change in area. Don't believe me? Hold a piece of paper up to your screen and check the straightness of the longest side. Just slightly off, right?

The prize door puzzle kills people because it goes against our intuitions about fairness and probability.

In as casual of an explanation as I can muster, when you made your first selection, there was a 1/3 chance you were right. With a wrong answer removed, there is now a 1/2 chance you were right. But because the rules stipulate the door you chose cannot be eliminated, your odds actually stay at 1/3 if you keep your door. If you were to switch doors, you then take advantage of the improved odds. The other door has a higher chance of holding the prize because it withstood that elimination, unlike your initial pick.

Nerissa

EddieDean wrote: »

Missing square in a triangle puzzle:

Both of these triangles are made up of the exact same shapes, just reconfigured. So where does that gap in the lower one come from?

3, 2, 1.. GO!

solution

The angled side of the complete supposed "triangle" isn't actually straight. The slope of the side in the red triangle isn't the same as the slope of the side in the light blue one.

So, it is concave in the original triangle (providing more empty space than is apparent by about a half-square worth of area) and convex in the second one (providing less empty space than is apparent by about a half-square worth of area) -- the difference in the areas accounts for the empty square.

Feral

The best way to understand the Monty Hall problem is to actually do it.

Get a deck of cards, pull out two Jokers and an Ace. The Jokers are the empty doors and the Ace is the prize door. Do it 30 times, changing doors every time. Then do it 30 times, sticking with the same door every time.

Element Brian

Wait, so can we answer the game show question then or not?

So It Goes

Feral wrote: »

The best way to understand the Monty Hall problem is to actually do it.

Get a deck of cards, pull out two Jokers and an Ace. The Jokers are the empty doors and the Ace is the prize door. Do it 30 times, changing doors every time. Then do it 30 times, sticking with the same door every time.

All I need to remember is the answer and that at one point I understood why it was the right answer :P

Feral

So It Goes wrote: »

Feral wrote: »

The best way to understand the Monty Hall problem is to actually do it.

Get a deck of cards, pull out two Jokers and an Ace. The Jokers are the empty doors and the Ace is the prize door. Do it 30 times, changing doors every time. Then do it 30 times, sticking with the same door every time.

All I need to remember is the answer and that at one point I understood why it was the right answer :P

well yeah that too

Nerissa

Donkey Kong wrote: »

The triangle one is great because

people are so bad at judging exact angles. Our brains snap to the nearest ideal far too easily. The angle of the left tips of the blue and red triangles are not the same, meaning the triangle's hypotenuse is effectively bowed inward on the first shape and outward on the second. That's enough to account for the change in area. Don't believe me? Hold a piece of paper up to your screen and check the straightness of the longest side. Just slightly off, right?

another way to see this, using just the picture

count the rise / run on each triangle (red & blue) -- don't even bother dividing them out, just note that they are not equivalent fractions

Element Brian

The most important thing to understand about the Game show problem is that the host was always going to choose one of the other doors. No matter what, there was going to be a second round, and you were going to be given the choice to change, even if you chose the goat in the beginning. Assuming the Host is fair, say you choose door 1 which has a goat, he eliminates door 2 which also has a goat, because he DID NOT decide to eliminate door 3, with the car, then that door already withstood a round of elimination raising the odds of it holding the car to 66.6%

Polity

To your chessboard problem: I'll see you five and three and raise you:

Eight queens of the same color, none of them able to attack any other.

It's simple if you follow a knight-move pattern around and switch the last queen around with one other so it can't attack the first diagonally.

EddieDean

Element Brian wrote: »

Wait, so can we answer the game show question then or not?

Absolutely. Feel free to post your own solutions! I had no idea it was so well known, but do go ahead!

So It Goes

I like the Puzzlers on Car Talk.

http://www.cartalk.com/content/puzzler/2009.html

Gosling

Raiden333 wrote: »

There is an island that is considered to be paradise. All the inhibitants of the island are Perfect Logicians, and every knows of every that they are Perfect Logicans.

Exactly 100 of these persons have blue eyes, 100 have brown eyes, and 1 has green eyes. The inhibitants do not know what his/her color eyes is. Everyone is constantly aware of everyone elses eye color but no person knows that there are 100 blue eyed, 100 brown eyed, and 1 green eyed person on the island.

If a person finds out his/her own eye color she/he must leave the island at midnight of the day she/he finds out! There are no mirrors or reflections of any kind on the island. Also, nobody on the island ever speaks except the Guru, who is the person with the green eyes, (she does not know her eye color and if she found out she would have to leave the island at midnight). The Guru says one sentence every fifty years. One day the Guru arrives and tells everyone on the island the following: “I SEE SOMEONE WITH BLUE EYES.”

Who (if anyone) leaves the island and when?

I'll be back to clean up when you're all done killing each other in 5 pages when the arguments heat up.

I have a feeling that the island's going to wind up empty, but for the life of me I have no idea how.

garroad_ran

Polity, I wish you'd posted the solution in a different spoiler than the question

Feral

The island puzzle is easier (and better) when it's more succinctly phrased. Here's XKCD's version.

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. 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), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves."

Raiden333

That puzzle's always been one of my favorites, as it was how I was taught a certain flavor of logical proofs.

Aroduc

Here's a fun one that usually causes a big argument.

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?


===========

And a more solid one... 1,000 pirates meet up to divide their booty. They're all ranked from 1 to 1,000 in order. Being democratic pirates, they decide to take a vote. If the vote passes they'll split the treasure equally between all remaining pirates. If the vote fails, they'll kill the lowest ranked pirate and then vote again. Since they're greedy pirates, they'll vote to maximize their share of the treasure without regard to killing their shipmates.

How many pirates will end up splitting the booty?

Polity

Polity, I wish you'd posted the solution in a different spoiler than the question

I'm sorry! I changed it, though I suppose it's a little late for your own personal spoilage.

As a consolation:

One is three
and three is five
and five is four
and four is cosmic.

This puzzle is incredibly easier in text than how I usually ask it, spoken aloud. It usually takes a few minutes that way, whereas I can't imagine it'll be much of a challenge at all on a computer screen.

Oh, and you don't have to start at one. It works with any number of any length. Neat, right?

Gosling

Oh, I think I have the eye color solution.

For 99 nights, nobody leaves. On night 100, all the blues leave en masse.

Each day everyone watches one specific blue-eye to see if they leave. When they don't, okay, the guru's not talking about that guy, so I'll watch this other one over here.

On Day 100, if you're a blue-eye, you've now looked at all the other blue-eyes and nobody's left, so the guru must have been referring to you. You go bye-bye.

If you're a brown-eye or the Guru, on Day 100 you still have one more blue-eye to look at, so when they all go on Day 100, you know you're not it.

Quid

Feral wrote: »

The island puzzle is easier (and better) when it's more succinctly phrased. Here's XKCD's version.

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. 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), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves."

Oh.

All the blues, I'd guess on the next night.

Edit: Or is it what Gosling has?

Starcross

Aroduc wrote: »

Here's a fun one that usually causes a big argument.

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?


===========

And a more solid one... 1,000 pirates meet up to divide their booty. They're all ranked from 1 to 1,000 in order. Being democratic pirates, they decide to take a vote. If the vote passes they'll split the treasure equally between all remaining pirates. If the vote fails, they'll kill the lowest ranked pirate and then vote again. Since they're greedy pirates, they'll vote to maximize their share of the treasure without regard to killing their shipmates.

How many pirates will end up splitting the booty?

What happens if the vote is tied?

Donkey Kong

Aroduc wrote: »

Here's a fun one that usually causes a big argument.

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?

If $50 is the larger amount, you end up with $25. -$25
If $50 is the smaller amount, you end up with $100. +$50

The problem is clear cut. The only questions is HOLY SHIT AN ALIEN!

Capture it. Set for life.

Feral

Gosling wrote: »

Oh, I think I have the eye color solution.

For 99 nights, nobody leaves. On night 100, all the blues leave en masse.

Each day everyone watches one specific blue-eye to see if they leave. When they don't, okay, the guru's not talking about that guy, so I'll watch this other one over here.

On Day 100, if you're a blue-eye, you've now looked at all the other blue-eyes and nobody's left, so the guru must have been referring to you. You go bye-bye.

If you're a brown-eye or the Guru, on Day 100 you still have one more blue-eye to look at, so when they all go on Day 100, you know you're not it.

Yep.

Aroduc

Starcross wrote: »

Aroduc wrote: »

Here's a fun one that usually causes a big argument.

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?


===========

And a more solid one... 1,000 pirates meet up to divide their booty. They're all ranked from 1 to 1,000 in order. Being democratic pirates, they decide to take a vote. If the vote passes they'll split the treasure equally between all remaining pirates. If the vote fails, they'll kill the lowest ranked pirate and then vote again. Since they're greedy pirates, they'll vote to maximize their share of the treasure without regard to killing their shipmates.

How many pirates will end up splitting the booty?

What happens if the vote is tied?

Ah, sorry, they split it then.

Raiden333

Feral wrote: »

Gosling wrote: »

Oh, I think I have the eye color solution.

For 99 nights, nobody leaves. On night 100, all the blues leave en masse.

Each day everyone watches one specific blue-eye to see if they leave. When they don't, okay, the guru's not talking about that guy, so I'll watch this other one over here.

On Day 100, if you're a blue-eye, you've now looked at all the other blue-eyes and nobody's left, so the guru must have been referring to you. You go bye-bye.

If you're a brown-eye or the Guru, on Day 100 you still have one more blue-eye to look at, so when they all go on Day 100, you know you're not it.

Yep.

Correct. Logical Induction.

Quid

Damn it all!

Polity

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?

Take the switch. You have a 50% chance of $100 and a 50% chance of $25. Probability time: P(0.5)[100] + P(0.5)[25] = 62.5 > P(1)[50] = 50

I think. It's been a while since Statistics.

And a more solid one... 1,000 pirates meet up to divide their booty. They're all ranked from 1 to 1,000 in order. Being democratic pirates, they decide to take a vote. If the vote passes they'll split the treasure equally between all remaining pirates. If the vote fails, they'll kill the lowest ranked pirate and then vote again. Since they're greedy pirates, they'll vote to maximize their share of the treasure without regard to killing their shipmates.

How many pirates will end up splitting the booty?

I'm going to say either two or one, depending on tie rules. The top half will always vote against in order to increase their share, dropping off the poor bottom sap each time until you've reduced to where the one on the bottom makes up enough votes by himself to stop the vote.

Starcross

Donkey Kong wrote: »

Aroduc wrote: »

Here's a fun one that usually causes a big argument.

An alien walks up to you one day and offers you two suitcases. You choose one and open it, and it contains $50. He then tells you that one of the suitcases has twice the money as the other, and that you can switch to the other one if you want. What's the best course of action?

If $50 is the larger amount, you end up with $25. -$25
If $50 is the smaller amount, you end up with $100. +$50

The problem is clear cut. The only questions is HOLY SHIT AN ALIEN!

Capture it. Set for life.

Ok. Assume that you get given the case and are asked if you want to switch before opening it. You realise you have half a chance of doubling your money and half a chance of halving it, leading to an expected profit. So you switch. Then the alien asks if you'd like to switch back. You have half a chance of doubling your money and half a chance of halving it by doing this, leading to an expected profit. So you should switch back.

No matter which suitcase you have, according to your reasoning, it is right to switch to the other.

Quid

Two makes sense.

EddieDean

Wow, thread's already forging ahead. I'm definitely going to use the eyes puzzle, that was fantastic.

Starcross

Polity wrote: »

And a more solid one... 1,000 pirates meet up to divide their booty. They're all ranked from 1 to 1,000 in order. Being democratic pirates, they decide to take a vote. If the vote passes they'll split the treasure equally between all remaining pirates. If the vote fails, they'll kill the lowest ranked pirate and then vote again. Since they're greedy pirates, they'll vote to maximize their share of the treasure without regard to killing their shipmates.

How many pirates will end up splitting the booty?

I'm going to say either two or one, depending on tie rules. The top half will always vote against in order to increase their share, dropping off the poor bottom sap each time until you've reduced to where the one on the bottom makes up enough votes by himself to stop the vote.

Pirate 1 knows that if it comes down to just him and pirate 2, he is getting nothing. (Pirate 2 suggests a 100% to him 0% to pirate 1 split. The vote is tied so they take the split. Therefore anyone can get pirate 1's vote by offering him 1 doubloon (or whatever denomination the treasure is in.

Edit:

Similarly, 2 knows that if it gets down to 3, 2, and 1 then 3 will give 1 a single doubloon (ensuring his loyalty) and take the rest for himself. We can therefore buy 2's loyalty with one doubloon.

I think I have the ordering wrong (ie when I say pirate 1, I mean pirate 1000)

Gosling

Who's divvying up the treasure? Is it a group effort or does one specific person do it? Because I think I might have that one too.

500 pirates get something. Ranks 2-500 get one piece of gold and the captain gets the rest. The captain's happy, he gets a bunch of gold. The others know that one piece is the most they'll get because the captain will just vote himself their shares if he's not happy. Ranks 501-999 will vote no. Rank 1,000 is just going to be happy not to get killed.

501 yeas, 499 nays.

Aroduc

You guys are really off on the pirates so far... and giving answers to a different pirate riddle. :P They divide it up evenly once the vote passes, no matter what rank they are.

Hint:

Dead pirates get 0. They know this and will vote according to that. Now what happens when there are 3 pirates? Or four pirates? Five?

===========

Oh yes, and another one that is always fun to torment programmers with...

Take a grid of size 20x20 and remove the corners at (1,1) and (20,20), ie two opposite corners. 398 squares left.

Now, if you're given with a set of tetraminos (tetris pieces) minus the 'T' shaped pieces, plus a single 2x1 piece, design a way to find a solution using the tetrominos and single domino to cover the board.

Or if you want easy mode

Use nothing but 2x1 pieces.