Geek Brain Teasers

muce writes "A few days ago my cube mate entertained a lot of us engineers by presenting us with the famous Monty Hall problem. That problem sparked a day of strong debates, coding simulations, and ramped writing of equations on whiteboards. Since then we've been thirsting for more good geeky mathematical brain teasers to pass the time at work. Does anybody know of any good ones like the Monty Hall problem, or by chance is there a web page with a collection of them?"

Comments

geek brainteasers, oxymoronic? yeah, but...

[Anonymous Coward]

check out the puzzles faq (ftp from rtfm.mit.edu) lots of math puzzles, language puzzles, every sort of puzzle you could want.

if you and two friends go to a hotel, the hotel manager charges you thirty dollars, you split it three ways, ten bucks each, right? then you go to your room, the manager realizes it was only 25, so he sends a bellhop with five dollars to your room. The bellhop steals two bucks, giving you each a dollar back, reducing your expenditure to nine dollars each, nine times three is twenty-seven, plus the two that the bellboy stole is twenty-nine dollars, where's the missing dollar?

OK, switching is beter

[Chacham]

You'd think you had a 50/50 chance by knowing that you seem to have a choice between two doors. Because, should a second person come along not knowing of your choice, and choose between the two doors, his chances would have to be 50/50.

Let's ask the question another way. Monty asks you to choose a door with no chance to switch. Your chances are 1/3. Even if he opens one of the wrong doors before he tells you if you won or lost, you cannot change, and therefore your chances are 1/3.

Again, but this time Monty asks you to *remove* a door. In other words, you win if the door is *not* the one that you pick. Your chances are 2/3. Even if Monty opens up a losing door before he tells you the winner.

Should you choose to stay or switch *before* you choose any doors, these two cases are stay and switch respectively, showing the odds are 1/3 for staying and 2/3 for switching.

The thing that boggles the mind, is if someone else chose his chances are 50/50. Yes, this is true. But had he known the previous situation, his chances are the same as yours.

It still seems not to make sense since how does opening the door affect your decision. So here is what helped me. When you make your first choice, you have a 1/3 chance of getting the car. So, in 1/3 of the cases, Monty can choose either of the other two doors to open, as they are both losers. In 2/3 of the cases (that is, when you choose a goat door) the door that monty open is chosen by your choice. That is, he can't choose your choice to open, nor can he open the one with the car. Thus, in 2/3 of the cases you *affected* the opening and cancellation of one of the doors. Thus bring it into the equation and allowing it to raise the cahnces of the other door.

---
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;

Another puzzle.

[Chacham]

I posted this lat time Ask /. had a puzzle of boring Sunday a while back.

Three smart kids are on a beach and all have mud on their foreheads. An old man comes over to them and asks for each of them to look at *both* their friends, and should one *or* both of their friends have mud on their foreheads, they should raise their hands. All three kids look at both of their friends, and seeing mud on both of their friends heads, they raise their hands.

The old man then offers a dollar to anyone who can answer his next question, and prove it. He asks if any of the kids know that they do, or do not, have mud on their foreheads, and if they can prove it. The kids look at each other and are bewildered for a bit. Suddenly, one of them screaches, "Oh!" and raises his hand. He then explains to the old man how he must have mud on his forehead and explains his reasoning. As his reasoning was excellent, the old man gives him the dollar.

What was the boy's reasoning?

---
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;

Re:Another puzzle.

[webrunner]

If boy 1 saw that boy 2 was clean and boy 3 was muddy, and boy 3 had his hand up, that means that one of himself or boy 2 has mud. Since boy 2 was clean (he could see that) he must be muddy.
----

Its "Three Card Monte"

[acroyear]

Well, not quite, but tts an old problem, a stastical brain teaser, that (if you watch your James Burke) is partly responsible for the application of statistics to the French census durin the Napoleanic era.

The original is "how many [black|red] cards are there in three face down cards; does the number seem to "change" when one of the cards is revealed?" The problem is from the 16th century (about the time of the application of color to what became the "standard" deck), and the solution came in the 18th century...with no computers involved. The solution uses basic probability mathematics that's still taught as-is in today's Prob&Stats classes for Math and CS Majors.

three travelers at the hotel

[dutky]

Three travelers stop at a hotel for the evening. The manager offers the travelers a single room at a cost of $30, to which the travelers agree, each paying the manager $10.

Later that evening the manager realizes that he has over charged the travelers for their room: the price should have been $25 rather than $30. The manager calls the bellhop over, giving him $5 and instructing him to take the money up to three travelers as a refund. On his way up to the travelers' room the bellhop considers that there is no even way to divide $5 between three people, and decides, in the interest of civility, to keep $2 for himself as a tip, giving the travelers' only a $3 refund

When the bellhop gets to the room, he gives the travelers their $3, which they divide equally amoung themselvs, $1 per person, and everyone is happy. Here, however, is the problem: Each traveler has now paid $9 ($10-$1=$9), meaning that they have paid a total of $27 (3*$9=$27) for the room. Add in the $2 that the bellhop kept as a tip and we have $29 ($27+$2=$29). But the three travelers originally paid $30! Where is the missing dollar?

Re:three travelers at the hotel

[dutky]

Exactly true. When I first heard this puzzle I was told that the solution had to do with the order of mathematical operations and precedence, but I have also had the solution explained to me in terms of standard accounting practice. (something about not counting both debits and credits in the same group, but I'm no accountant so I don't remember the details) The real trick is in the telling. This didn't become clear to me, however, till I had to write the problem down, and I found that you had to carefully avoid any mention of the price after the refund (or the price claimed by the bellhop, to obscure his petty theft).

The simplest way I have found to explain the error is to say that you should only count actual dollars that people in the problem are holding: $3 (in the travelers' hands) + $2 (in the bellhop's pocket) + $25 (in the manager's till) = $30 (originally paid for the room).

Still, most people, when they first hear the puzzle, are quite flummoxed and have a very hard time explaining exactly what the error is.

Re:This isn't a brain teaser..

[Rev Snow]

Try this variation and see if you change your mind:

Monty shows you 1000 doors and asks you to pick the one you think hides a car. You pick door 94. Then Monty opens 998 doors. At each door, he checks the number on the door against a little scrap of paper he has. When Monty is done opening doors, he has revealed 998 goats, and left your selection, door 94, and one other door, door 672, closed.

Monty reminds you that one of the two remaining closed doors hides the 999th goat, and the other hides a brand new car! You can keep your original choice, or change your choice to door 672.

Should you switch?

If yes, how is this different from the three door case?

Re:This isn't a brain teaser..

[Xenu]

Don't feed the trolls.

Re:ok ... the solution ...

[Pseudonym]

Let's assume without loss of generality that you pick the first digit. That rules out cases 4 to 7. Knowing there's at least a 1 rules out case 0. The cases left are 001, 010 and 011. Therefore the odds that there are two 1's is 1/3.

Get it now?

This picture explains why it is NOT 50/50

[UnknownSoldier]

There were some pretty heated discussions here a while ago, until we wrote down all the possible outcomes. It was a relief to find a mathematician agreed:

http://math.ucsd.edu/~crypto/Monty/montybg.html

This isn't a brain teaser..

[technos]

Arguments and code simulations? Why? Are your co-workers mentally weak? This is an open and shut case of logical analysis.

At first glance, there are three doors, two goats, and one car. However, this is misleading.

In any run of the problem, one of the unchosen doors is shown to be a goat. You cannot choose that door, and both it and its associated goat never enter into the statistical problem.

The actual problem has only two doors, one goat, one car. Plain old 50/50 chance. There is no gain to be had by changing doors.

Well, unless the door is hung a bit high and you can see goat legs under the door you have chosen.

Re:This isn't a brain teaser..

[technos]

Heh.. I was expecting a standard magicians lead routine. Hadn't seen that as a 'online' version. How many people would remember more than one card, so what danger is there in not changing them all? :)

I'd seen the real world equivalent. Took me one try to beat it, and only because I cheated. (Cards you have just laid out in front of you in intentionally spilled beer on do NOT suddenly become dry and fresh. You can always smell the beer)

Take the five changed cards, and invert them on the bottom of the deck. If you know how to tab them into a cut, I'd shuffle a time or two and make them arrive at the bottom. Pick through the deck for them, in front of the patsy. Have the pick made, then tell them to shuffle the six and place them back on top of the deck, removing any chance the order will ring a bell with the patsy. Tell them to think about it, while you grab the deck and deal the changed cards to them after a quick inversion.

Oh, and three socks.

Re:This isn't a brain teaser..

[technos]

[sigh] I see how there were arguments now.. :)

If I think about it that way, it's still a 1/2 problem since the second goat is a known quantity.

Think about it like this. You are presented with three doors, one open displaying a goat, *before* you make your choice. (When the door is opened is meaningless, as it always displays a goat) You cannot choose the open door, obviously, so there are only 2 to choose from.

Re:This isn't a brain teaser..

[technos]

Goddamnit.

You're right, I'm wrong.

[/me bashes his head against the table.]

I hearby apologize to everyone I flamed. I was wrong. For lack of a better programming language at my disposal, here's an Office macro that proves not only am I an idiot, I'd only get the car half as much as Rev Snow.

Sub goat_problem()
Dim chosen As Integer
Dim you As Integer
Dim looper As Integer
Dim swi As Integer
Dim norm As Integer
For looper = 1 To 20000 Step 1
chosen = Int((Rnd() * 3) + 1)
you = Int((Rnd() * 3) + 1)
If (chosen = you) Then norm = norm + 1
If (Not (chosen = you)) Then swi = swi + 1
Next looper
looper = MsgBox("goat " & swi & " " & "notgoat " & norm & " " & swi / norm, vbOKOnly, "goat?")
End Sub

Re:This isn't a brain teaser..

[webrunner]

The way I like to think of it is that hte switch is like asking: "Do you want that door, or do you want EITHER OF THE OTHER TWO DOORS" - which means the 2/3 seem much more correct.
----

Re:This isn't a brain teaser..

[jon_adair]

Let's look at a simplified version of the possibilities. We'll only consider the case where the prize is behind door #1.

You pick door 1, Monty opens door 2, you stay, you win.
You pick door 1, Monty opens door 2, you switch to door 3, you lose.
You pick door 1, Monty opens door 3, you stay, you win.
You pick door 1, Monty opens door 3, you switch to door 2, you lose.
You pick door 2, Monty opens door 3, you stay, you lose.
You pick door 2, Monty opens door 3, you switch to door 1, you win.
You pick door 3, Monty opens door 2, you stay, you lose.
You pick door 3, Monty opens door 2, you switch to door 1, you win.

(Note that there are 4 additional cases where Monty would open door 1, but he can't since the prize is there. I suspect that this is where some people make their mistake.)

Now, out of those 8 cases, you win 4 times or 50%. In the cases you stay with your original door, you win 2 out of 4 (50%). If you always switch, you win 2 out of 4 (50%).

If you expanded this to all 3 prize locations, you would get 12 out of 24, 6 out 12, and 6 out of 12, or 50% chance no matter what your strategy was.

I think most people make the mistake of not fully considering the case where you pick the prize door in the first place. There are two possible branches from there since Monty can open either incorrect door. If you don't take that into account, then you end up thinking that you only win 1 of 3 by staying but win 2 of 3 by switching.

Like we said, the first door choice really doesn't count for anything. The only choice that matters is the final door you chose. Since you're picking between 2 doors and 1 has the prize, that leads to a simple 50% probability.

Re:This isn't a brain teaser..

[jon_adair]

After sleeping on this, I changed my mind. Count me in the "it's better to switch" camp instead of the "50-50" camp.

In the 8 cases I listed, you can drop the first two. When you select the correct door at first, it doesn't matter which door Monty opens. He has two choices that are equivalent from your point of view (between two doors, each of which doesn't have a prize behind it). His choice doesn't impact the probability of you finding the prize.

Re:This isn't a brain teaser..

[HiNote]

Your example holds, if you assume you pick correctly on the first guess 50% of the time, which is a flawed assumption (unless the game show is rigged, of course)

Try looking at it this way: Monty knows which door the prize is behind. If your first pick is a door with no prize behind it, he can choose to open either of the other doors. If your first pick isn't the door with the prize behind it, he has to open the other door with no prize -- he doesn't have a choice. At the point where you pick a door (say door 1) and Monty is about to open a door there are three possibilities

Possibility 1: Prize is behind door 1: 50% chance Monty will open either

Possibility 2: Prize is behind door 2: 100% chance Monty will open door door 3. 0% chance Monty will open door 2

Possibility 3: Prize is behind door 3: 0% chance Monty will open door 3. 100% chance Monty will open door 2.

Each possibility has a 33% chance of happening. With Possibility 1, if you stay, you win and if you switch, you lose. With Possibility 2, if you stay, you lose and if you switch, you win. With Possibility 3, if you stay, you lose and if you switch, you win. Therefore the probability of switching and winning is 2/3.

Re:monty hall variant

[technos]

Heh.. Why worry about it, when the answer can easily be gained through social engineering at no cost?

'Man, three kids.. How do you handle the sibling rivalry?' should produce at least one childs name and the gender of the other two. If it doesn't, eg, you get a result like 'Oh, it is/is not terribly bad.' you have to go fishing again. If you had siblings, or have at two children of the same sex, try the empathy ploy. Detail how when you/your children had to share a room, the infighting was worse, and ask if keeping them seperated could be the reason/solution.

Leading, generic talk can get you anywhere.

Re:monty hall variant

[technos]

Nope. A decreased chance. Seeing a girl's bedroom is as good as seeing the girl. There are a myriad of excuses to have the hockey schedule on the fridge, from 'My wife picks up the neighbor's kid when she picks the girls from ballet' to 'My twelve year old, Daphne, was so good they moved her into boys AAA Pee-Wee this year.'.

Car Talk puzzlers

[Lish]

The website for the Car Talk NPR radio program has all of their past puzzlers, some of which are car-related but most are not. They range from the completely obvious to the completely impossible. The Monty Hall puzzler is among them. They're available either as RealAudio or as html (transcripts of the radio segments). Definitely go check them out.

Coding brain teaser

[OmegaDan]

a few years back in a CS class I was assigned the sadistic task "write a program in C++ whose output is its own source code"

I never figured it out but apparently it is possible.

Answer.

[ClayJar]

handA = (mudB or mudC);
handB = (mudA or mudC);

Since mudA and mudB are both true, the value of mudC is indeterminate. An individual, therefore, would not know the value of mudC (his own forehead muddiness), solely from handA, handB, mudA, and mudB. However, when the kid saw that at least one of the others was sufferring from the indeterminacy of his own forehead muddiness, the only reason is that that kid is also seeing the same problem of two hands and two muddy foreheads. Seeing this, the kid pronounced that his forehead must certainly also be muddy. QED.

Re:ok ... the solution ...

[bellings]

No, try again. You have a binary number of 3 digits. You are have two pieces of information:

1. You choose one digit randomly, and are told it is a 0.
2. You are told that there is at least one 1.

Notice that the two pieces of information are not of the same "quality". Now, what are the odds that there are two 0's? What are the odds that there are two 1's?

Marylin vos Savant

[jon_adair]

As a side note, at one time I heard an explanation of her world record IQ that makes me discount her as the world record holder.

Supposedly IQ scores depend on the sample size taking the test. If a relatively small number of people take the test, even scoring a perfect score can only rate an IQ a few points above the average.

So the story I heard is that the test she set the record on was one of the most widely given standardized IQ tests. I believe she is solidly in the "baby boomer" set and I think this was a school test given years and years ago.

Since no test since then has been given to more people, even a perfect score on every IQ test since then wouldn't result in breaking her record.

Of course, that's just the information I heard. It could be wrong, but it does sound plausable.

monty hall variant

[s20451]

Here's a variant on the Monty Hall problem that I got from a computer science prof, which illustrates arguments regarding Bayesian inference.

Your friend invites you to his house. You know a priori that he has three children, but you have no information on their genders.

While looking for the bathroom, you accidentally stumble into one of the children's rooms, and find that it is obviously a girl's room.

While in the kitchen, you see a schedule for a boys' hockey team.

So, you know that there is at least one boy and one girl. The question is: what is the probability that there are two boys and one girl?

I am obfuscating the answer so as to let you think about it first: floor(log(7.39))/floor(10^(0.779))