Slashdot Mirror
No Magic In A Knight's Tour
morgothan writes "As reported in an article on Math World the solution, or rather lack of solution has been found to the over one hundred fifty year old math problem of how many numbers of magic tours a knight can make on a standard 8x8 chessboard. It turn out that there exist one hundred forty distinct semimagic tours, but no magic tour. The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz, the project was completed on August 5, 2003 in which every possible enumeration was tried out. The author of the software that finally solved the problem has also put up a webpage in which he further explains the problem and his method of solving it." Thanks to Mig for pointing out a great background page on Chessbase.com.
is right here
Maybe if the Knight REALLY wanted to take a Magic Tour he'd consult a Wizard instead of a Computer...
No wonder he didnt only got a Semimagic tour, damn you Travelocity! Damn you to hell!
This is my sig. Its pathetic.
The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz
I bet the horse was tired after hopping around so much.
The unofficial
Now we're going to examine how many routes there are through all the bars in Amsterdam, and see if there are any "magic" routes that will let us complete the circuit without falling drunk in a bed of tulips.
Sheesh, evil *and* a jerk. -- Jade
A project like this just cries out for distributed computing - if it can be done for Seti and cracking the X-Box key (or rather trying to), surely a distributed client running on many PCs would be a godsend for solving major maths problems.
Whatever happened to the classic style of problem-solving, whereby an actual proof was deduced, rather than simply employing brute-force to "count them all?" I mean, don't get me wrong, I'm glad that we finally have an answer to this pressing question (which I'm sure 95% of us had never heard of prior to reading this article), but does anyone else feel that these "brute-force" solutions are kind of cheating?
Like woodworking? Build your own picture frames.
I hear Hogwarts will be selling these once the last book is finished and they run out of money.
Check this out...
#define true 7361
#define false 28456
how long until
> The webpage mentions that the program is windows based and doesn't save state. That means that all of those CPU hours came in a row (at idle priority even). Bash MS all you want, but Windows isn't as unstable and problematic as all of your anti-MS zealots would like to believe.
61.40 CPU-days spread between 10 people's computers, and you think that indicates enough uptime to brag about? Puh-leeze.
Sheesh, evil *and* a jerk. -- Jade
There is an interesting [related] article on chessbase here about knight's tours. On the main chessbase page, they reference the main article involving magic tours.
Be excellent to each other. And... PARTY ON, DUDES!
uptime is nothing to brag about, unless you're talking about your penis.
Probably not, but this problem and the way to achieve the magical tour have been going around for quite a few centuries, with some of the brightest minds trying to work on it. So even if it doesn't have practical applications it's still important.
Don't try to fix me. I'm not broken.
actually, it's 1 in 2 because in this hypothetical situation, one door is always opened that is not the prize, so you never have a 1 in 3.
You're mistaken, although you are in good company, no less a mathematician than Paul Erdos made the same error.
Post your code if you still think switching makes no difference.
Magic knight's not touring? What am I gonna do with these damn tickets...
I'm just a lowly database programmer, so I have no clue about high end programs like this. Is it a common practice for time intensive processes to not have any sort of save file?
Shadow
I thought this was something about Cheesebase when I first saw it.
Don't blame Durga. I voted for Centauri.
It's hardly impressive. No modern operating system randomly crashes for no reason at all (Windows 95 and the others that did crash after the counter wrapped were not modern operating systems). Windows isn't doing anything here, apart from memory allocation and a few highly predictable tasks.
It's bad handling of errors in third party apps and drivers that usually kills Windows.
You're wrong...but don't feel bad. Lots of people make this mistake. Assuming the 'host' always opens one of the remaining doors and the remaining door never has a prize behind it, you should always switch. Why? On your first pick you have a 1 in 3 chance of getting the prize. If you always switch, your chance of getting the prize becomes 2 in 3. Prize -> Goat Goat1 -> Prize Goat2 -> Prize Thus, you win. or, to put it another way... Imagine there are 1000 doors and after picking a single door (1/1000 chance of getting the prize) the host opens all but 1 door. Would you switch? Of course! At that point there's a 9999/1000 chance you will win!
If it turns out 1/3 to 1/3 no matter if you switch, then your program sometimes opens the door with the big prize in it, I guess.
It really works like this:
Assuming you picked door A, then there are three possible situations:
-The prize is behind door A
-The prize is behind door B
-The prize is behind door C
So if you stick to the door you just picked, then you have a 1/3 chance of winning.
Now obviously there's a 2/3 chance that the prize is behind one of the two other doors. And the host is basically giving you the information
"IF the prize is behind one of the two remaining doors, then it is behind THIS one" by opening an empty door.
So switch, it will give you a 2/3 chance of winning.
And yes, I had to write a program, too, before I actually believed it.
So even if it doesn't have practical applications it's still important.
:-)
:-/
Why?
Oh yes, we don't have to spend some of the brightest minds have to work on a useless problem anymore. But I'm sure they'll find another one.
Brute forcing to get a proof is better than no proof at all, but brute forcing a special case is even more acceptable.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Imagine that you always stick with your first choice. Therefore, you've got to select the right door in the first place to win, hence your chance of winning by always sticking is 1 in 3.
Now imagine that you always switch. If you picked the right door to start with, you're screwed as you will always lose by switching. However, if you pick one of the two wrong doors then the host must to open the other wrong door, leaving just the right door remaining. So if you picked a wrong door in the first place, you are guaranteed to win by switching. Your chance of selecting a wrong door initially is 2 in 3 and therefore your chance of winning by always switching is 2 in 3.
1/3 + 2/3 = 1, hence all possibilites are accounted for and it is proved that by switching you twice as much chance of winning than by sticking.
That might be true, but it is still no excuse.
The operating system should be fault tolerant and not fail when a foreign(read: third party) application does some unexpected behavior.
Jeremy
Nope, but they got through about six coconuts.
"Still no cure for cancer."
Without trying to be too much of a Troll, can someone explain to me as a mathematical lay man as to why this problem has any significance? Given that a chess board is an arbitrary 8x8 set of constraints, is there anything that can be learned and applied to the real world (or even theoretical mathematics?) through solving this problem?
Also, I was under the impression that the objective of mathematical puzzles like this would be to find a simple, elegant proof. Does a brute-force calculation approach carry as much weight?
John Maynard Keynes: "When the facts change, I change my mind. What do you do?"
This sort of problem doesn't always have obvious uses, but uses tend to be found in some of the most bizzare applications. Or more usually code breaking/making.
There was a very interesting series on BBC radio4 (http://www.bbc.co.uk/radio4/science/) called five number and another five numbers which can be streamed from the above link which talks about this sort of thing.
The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz
Yeah, and I came to work in 12.34 horsepower-hours, corresponding to 666.13 hours of driving at 5K RPM. I mean, damn, I understand when my mom utters movie-level technobabble, but this?
They never said how many time they ran the program. It could have crashed twenty times previously for all we know.
-----
Sorry, I'm only a 1336 h4x0r.
I just wrote a quick demonstration program to find them...
"How to Do Nothing," kids activities, back in print!
The story uses CPU-hours "at 1GHz" as a unit of measurement.
Guys, please, this is SlashDot. A 1GHz G5 is not the same as a 1GHz Duron is not the same as a 1GHz P3. What sort of 1GHz chip is being referred to here?
Honey, I shrunk the Cygwin
\ 1 2 3
A y n n
B n y n
C n n y
The top row is the door number, the letters are the three cases, y means 'yes' (location of prize), n means 'no'. Suppose you chose door #1. In case A he'll show you door 2 or 3, in case B he'll show you #3, in case C he'll show #2. Only in Case A will you win by sticking with it. Case B and C you'll win by switching. That's 2/3 chance of winning by switching. Same thing regardless of what choice of door you made first.
You're right, the evidence has no mathematical beauty. Still, it's good to know what you're trying to do when you start writing a proof.
Here's what I have to say about mathematicians (since I have a bachelors in mathematics): Most people would invent paint to cover a wall they have that's bare. Mathematicians would invent paint with no intended purpose, then later discover it could be used on a wall.
Mathematicians frequently create for the sake of creation, rather than for any specific purpose.
--RJ
who also said
"never buy of the horse that is overridden as it will fetch less at the clackers"
consider coffee a lubricant that helps one penetrate the coding zone
Are you sure you read the correct parent post to mine? He is wrong, and you are as well, although your statement disagrees with his.
Suppose there are doors A, B and C. Let's say you pick door A originally, and the host then shows door B to be empty. Given this information, there is a one in three chance that the prize lies behind door A, and a two in three chance the prize lies behind door C.
Google for 'Monty Hall' for proofs of this.
It seems to me that more and more math problems are being approached in a brute-force, computerized way. While this is certainly a legitimate way of finding answers to a problem, aren't we missing the point of these problems by using it? It's not like anyone was really waiting on the answer to that problem. It's such a lazy disappointing answer to an exciting mathematical question: "Are there any magic knight tours on an 8x8 chessboard?" "Nah, I tried 'em all out, see." Are we seeing the death of "clever" mathematics where a simple elegant solution is found, correlating known theorems in novel ways that enhance our collective understanding of the way math works?
Now before you object, I am aware of really nifty, clever mathematical breakthroughs in recent memory. The recent polynomial-time primity test comes to mind. But what is the point of "research" and "inquiry" if we only care about the answers to the problem, and not the reason why? What is the point of finding the next Optimal Golomb Ruler" if we can't find a pattern relating one to the next? What would we really do with a magic knight's tour anyway, besides reading a clever and insightful proof of it's (non)existance?
Even a computerized proof would be interesting, if a method for proof-solving on computers were possible. And yes, it is possible to write proof-solving software that is at least as good as a human mathematician without upsetting Mr. Godel. But this brute-force type proofing is just plain dull!
-3Suns
~~~~
The Revolution will be Slashdotted
Put my mind at rest.. I've been worrying about this for years.
Many years ago I saw some guy doing a kinght's tour blindfolded on tv. I thought that was amazing, he must have calculated every move after he was given the starting square. But now it seems so simple, you just need to know a magic knight's tour by heart and that's it! (Ok, memorizing that is still pretty amazing by my standards :)
Haha. "Magic Knight" does indeed sound like the name of some awful medieval-tinged New Age band from 1988. Or perhaps "Band" is used loosely, and it is really one guy with a synth.
Found in some remainder bin somewhere: their debut album: "Enchanted Castle", and maybe even a copy of "Mystic Joust".
Don't blame Durga. I voted for Centauri.
...Assuming the 'host' always opens one of the remaining doors and the remaining door never has a prize behind it...
A note to all the people writing code to solve this, the key to this problem is that Monty intentionally chooses a door that has no prize behind it. No doubt, some of you are interpreting this problem as, "Monty chooses another door at random, and we're only examining the cases where he chooses the door with no prize". If that is your interpretation, then switching doesn't matter, but the traditional Monty Hall Problem assumes Monty knows what's behind the doors and chooses accordingly.
to switch or not to switch.
You pick queue 1. Queue 2 closes. Switching to Queue 3 is not going to help you. Unless the checkout operator in Queue 1 is an L-Plate operator.
So lemme see (I was always crap at probablility).
First you have a choice of three doors. So your chance of winning is 1/3 on door number 1.
Door number two is eliminated, leaving door number three with 2/3 probability against it.
But imagine, now you are only offered two doors to start with. Fifty fifty chance of winning. 1/2 chance. but you have to combine that with the original probability?
Ie the 1/3 and 2/3 probability no longer applies? Or does it. Ie you knew in advance that one empty door would be eliminated and you'd get an option of switching. So you could group your choices into 1/2 (for the door you picked) and 1/2 for the doors combined from which one will be eliminated? That's like saying 2/3 = 1/2. Which bugs my head no end.
Leastways, if the host always opens an empty door, it changes the 1/3 per door probability, to 1/2s. If the host can actually open the door with the prize (and you miss out), but he opens an empty door, then definitely the switch is on.
? Does it work on that who wants to be a millionaire thing, where you select an answer, get two eliminated (one of which could be what you hypothetically selected), is it better, supposing your original choice didn't get eliminated, to switch? (Assuming four options, two options eliminated and you have no clue which option is correct).
-- it must be true, it's on the internet.
Thing is though, is this actually an answer with any real point, proving an answer via a simple brute force method is far less interesting(and I would say far less useful) than a mathematical proof.
For me it is sort of like saying if I hurt my hand with a hammer it damn well hurts rather than investing the underlying reason.
yeah, a lot of the things that turn out to be of amazing practical use to non mathematicians happened to come out of the peculiar obsessions of various mathematicians, mersenne primes are mighty handy things to know about but were once just one of the many mathematical curiosities that mathematicians poked around at when they had too much time on their hands (and they also seem to defy pretty proofs and rely on brute force number crunching to discover or not discover if there is actually a limit to them, which is why finite though large problems like the magic tours are good candidates for brute forceing, since you can just get it solved and over with)and most of the discoveries that we owe to pythagorus come more from his weird mystical thinking about the nature of number than from any desire on his part to develop patentable techniques for industry.
multiple modes of inquiry are a good thing, if we judged everything from standards of immediate practical application we'd miss out on a lot of the good and practical things that number crunching for the sake of number crunching and pondering for the sake of pondering have given us.
I don't believe this.
To me it is obvious that after opening one of the doors the chance of winning is 1/2 no matter what door you choose.
It is just the same as if you were presented with a completely new set of doors (2 of them), of which one had a a prize behind it.
Chance has no way of knowing that there were three doors just a minute before, and that fact is completely irrelevant to the problem posed.
Will code a sig generator for food
Why does there have to be an practical application for something to be important? This is the Slashdot community, which is News for Nerds. Stuff that matters.
I don't know about you, but I get tired of hearing the plain old news. Most of it is kinda depressing, and hearing stories like this makes you realize how many interesting people there are out there. Sorry, but if I could moderate, your post would be troll. And as for the "nerd mountain", I think you are in the wrong place then.
Every Super Villan uses Linux.
I am trying not to be too negative here, but why should everything have to have a significance to the real world? The world doesn't benefit from me solving a crossword puzzle. It's just me, wanting to know the solution to the puzzle.
In the same way, people have been puzzled by the magical knight's tour problem for 150 years. And someone finally has solved the problem. It might not provide a cure for cancer, but at least it entertained a few people for some time.
Maybe something as insignificant as that should not be published, but on the other hand, I found it interesting to know that that problem got solved, so I don't complain that it has been published.
Also, I was under the impression that the objective of mathematical puzzles like this would be to find a simple, elegant proof. Does a brute-force calculation approach carry as much weight?
Perhaps not. But nobody sais that you can't go looking for an elegant proof just because the problem has been solved. There is also some merit in finding he easiest or most elegant solution, not just in finding the first one.
Where are you getting this from? He must be wrong just because you believe differently? Think about this:
You pick door A. Then the host opens door C. You say: "always switch to door B." Ok, well how about this: assume, at the same time, there was a guy who had started out by picking door B. Should he switch to door A now? By your logic, he should. But that means that both A AND B are "better" choices than each other, at the same time . . . doesn't make sense, does it. By your logic that's how things are, and they don't make sense. Maybe your logic is wrong . . .
Personally, I would have thought that the end result was winning 50% of the time, since one of the two is open. That's what seems to make sense to me. Two doors remaining, one with a prize behind it. (The parent post about having a 9999/1000 (though he means 999/1000) chance after 998 doors have been opened is ridiculous; the logic is incredibly flawed.)
Anyways, that's what I think.
A knights tour involves moving the knight onto every square of the chessboard without repeating a square (being a knight, it is of course allowed to jump over squares it has previously landed on).
:).
A magic square is a square grid, with each grid position numbered, such that the horizontals, verticals, and diagonals all add to the same number (you can also ask for all the broken diagonals to add to this number, but this doesn't have to hold in a basic magic square).
If we number the knight's initial position 1, and increment with every jump, then a knights tour gives us a numbered n by n square (8 by 8 in the case of a normal chessboard).
The question: are there any knights tours which give us a magic square after we perform this numbering operation?
The answer: no, although there are many tours which give us a 'semi-magic' square (where the horizonals and verticals, but not the diagonals, give us the same sum).
The point: although magic squares have a variety of surprising uses, there seems to be no 'point' to the magic knights tour question other than another line in the book of 'solved minor problems' -- but if it's enough to write a paper on, then you can bet you'll be able to find a graduate student to do it
-- Help Digitise the Public Domain at DP.
False. Chance, in this case, is controlled by the game show host. He does know there are three doors, and which one has the prize.
That said, the 1/3-2/3 thing is only applicable if two things are true: That the host must open a door, and that the door must be empty. If those are not true (which they weren't in the original show) then the whole analysis flys out the window.
Best explanation today is in a post above.
'Sensible' is a curse word.
Is this a /. first? Well I won't let it happen. Hey, screw the magical knight tour, how about solving 9x9 Go?
-Libertarian secular transhumanist
...the logic is incredibly flawed.
For someone who writes things like "I would have thought" and "That's what seems to make sense" I don't think you are in a position to posture on logic. In what way, exactly, is that poster's logic flawed?
Sir Paul McCartney did make a Magical Mystery Tour
Where are you getting this from? He must be wrong just because you believe differently?...
.
Er.. no. Maths divides things into 'correct' and 'not correct' (unless you want to get into formalistic stuff). He is wrong, not because of opinion, but because there is a valid proof that he is wrong.
You pick door A. Then the host opens door C. You say: "always switch to door B." Ok, well how about this: assume, at the same time, there was a guy who had started out by picking door B. Should he switch to door A now? By your logic, he should. But that means that both A AND B are "better" choices than each other, at the same time . . . doesn't make sense, does it. By your logic that's how things are, and they don't make sense. Maybe your logic is wrong . .
Yes, they are both better choices. That is not the same thing as saying they are both the correct choice, i.e. that the prize is behind each, just that based on the information available to the contestant, they have more chance of success if they switch door.
Try this analogy. The contestant picks a door, and is then told he can either open that door or all the other doors. Obviously you would choose to open the other two doors. The only difference between this and the standard Monty Hall problem is that in the standard case the host opens one of the other doors for you.
This is the single most understandable explanation of that whole door-switching-pseudo-paradoxon that i've ever read. Dear Mr. Coward, you are my hero.
Free as in mason.
61.5 days uptime isn't something to brag about, it's a medical condition.
I'm old enough to remember when discussions on Slashdot were well informed.
/Mikael
Greylisting is to SMTP as NAT is to IPv4
\ 1 2 3 - pick - shown
S y n n -- 1 -- 2
T y n n -- 1 -- 3
U n y n -- 1 -- 3
V n n y -- 1 -- 2
There are two cases where you win by changing.This makes it 1/2, if I am wrong, why?
Apologies for the ugly formatting, but I don't know how to get /. to accept some whitespace :-(
Your program must have been flawed. You should definitely always take the other door. Think of it this way. Suppose you chose a door. And, instead of opening one, Monty says "Ok, here's a new deal. You can either keep your door, or trade it for both the other doors." What would you do? If you took both the other doors, how suprised would you be to find that one of the doors was a loser? That's exactly the deal he is making with you, except he's just showing you the losing door earlier.
- "That's just the kind of fuzzy-headed liberal thinking that leads to being eaten."
I don't buy it. When Monty Hall opens the door, he changes the problem. A simple brute-force technique will show you that your odds of winning are 50-50:
P = Prize behind this door; N = No prize behind this door; Bold = The door you initially picked; Italics = The door Monty Hall reveals; K = Keep your original door; S = Switch doors; W = You win with this strategy; L = You lose with this strategy.
1 2 3 K S
P N N W L
P N N W L
P N N L W
P N N L W
N P N L W
N P N W L
N P N W L
N P N L W
N N P L W
N N P L W
N N P W L
N N P W L
6 wins, 6 losses no matter what your strategy.
The point is that the host knows where the prize is, and that he is giving away a lot of info by opening one door. It would be useless to switch if he opened the door at random and could possible find the prize himself.
so you should switch. As simple as that
And, your demo prg must be wrong. Remember that the host should use his knowledge and always open and empty door, never the correct one
That's what I mean. It wasn't defending MS, but criticising it.
Crashing when an app crashes means an OS is faulty. My point is that an OS staying up when it's running a single application which doesn't crash is not evidence that the OS is stable. The post I responded to suggested it was.
Think of it this way...
If you pick the correct door the first time (1/3 chance), and he shows you another door, and you switch, you lose.
If you don't pick the right door the first time (2/3 chance), he shows you another loser, and you switch, you win.
So, with the strategy to switch after he shows you another loser, you will win 2/3 of the time.
"the over one hundred fifty year old math problem"
How does this sound or look even remotely correct enough to submit to your peers? Atleast look like you're trying, people...
And if anybody had tried to open so much as a single additional application on their desktop while it was calculating?
bad sig...no donut.
That only applies for a series of matches. If you only have one chance, switching does not give you any advantage, because each of the 2 closed doors has the same probability of containing the prize. Look a it this way (you have only one shot):
You have 3 doors
* X X
A B C
The prize is on door A (the *), you pick door A and the host opens the door C:
* X
A B
You already picked door A, and regardless of the probabilities in the past step, this is a new problem, and you are reduced to a 1/2 probability. The probability of the 2nd state is independent of any state. So if you keep your decision or you switch is exactly the same.
Only with several chances you can, statistically, assert that switching increases the possibilities, but if you only have one shot, it does not matter.
Life isn't like a box of chocolates. It's more like a jar of jalapenos. What you do today, might burn your ass tomorrow.
If this isn't right I'd love to see how. As it demonstrates what I have always thought.
Why is case S or T 1/2 as likely?
:(
Maybe it's me but I'm looking at this from a completely different perspective.
You have two doors. One has the prize. One doesn't. You've already picked door A. What's the chances of you winning the prize if you change and pick door B. All the host of the show has done is remove one door from your list of choices.
Either this problem is very very easy or I'm very very stupid.
Pinky: "What are we going to do tomorrow night Brain?"
Brain: "I would tell you Pinky but this 120 char limi
I've been seeing a lot of comments disappointed with brute-force problem-solving--but I am all for it. Here's why:
In my job, I do fine structural analysis and computational fluid dynamics for aerospace design. Aerospace engineering is rapidly reaching the point where simplified, elegant models are inadequate to the real-world structures they are meant to mimic. For instance, the Navier-Stokes equations, a set of second-order partial differential equations which describe fluid flow, are not susceptible to analytical solution in any but the most simplified cases, and as things like airfoils, turbine blades, and computers grow more refined, their properties require much hairier math to describe. Turbulent flow around a wing or turbine blade has no elegant solution, but a brute-force computational model can yield a solution that allows us to design a lighter wing, and thus a more fuel-efficient plane, or a stronger turbine fan, and a more efficient generator. Or, to cite an example near and dear to many slashdotter hearts, as we can better model the heat transfer inside a microprocessor, we can better devise ways to cool it, and thus build a faster, more stable computer. (And then, we can solve more iterations on it, and build an even faster computer...and then we can solve more iterations... ^_~)
There is an intense intellectual satisfaction to a 20 or 100 line proof (I still remember the triumph of my high school proof that a triangle's interior angles sum to 180), but for a lot of things, there simply exist no such proofs. As we tackle more and more mathematical problems, those with relatively simple proofs will quickly be solved and set aside, and we will move on to messier things. For instance, the proof of Fermat's Theorem runs to several hundred pages of dense elliptic curve math. It was an aesthetic disappointment for those hoping for a simpler solution, but it was a triumph for the field of mathematics as a whole.
There is a whole 'nother world of proofs involved in brute-force solutions. Estimated time to solution, order of error--elegant mathematical tools are still necessary, but they are increasingly used to delineate regions of uncertainty as the complete picture becomes messier. The closer mathematical models get to the real world, the more complex and beautiful, but the less elegant, they become. I do not think that the field of mathematics will stop producing elegant proofs, but I do think they will have less and less to do with the world we live in and more and more to do with hypothetical mathematical constructs, whose usefulness will then filter down in the form of special cases to more prosaic disciplines, like science and engineering. This diminishes neither science nor engineering, and adds to the knowledge available in all fields.
-Carolyn
Like Daddy always said: if you can't dazzle 'em with brilliance, baffle 'em with bullshit.
Consider it another way. You have a 1/3 chance of getting it right on the first pick. That's means there's a 2/3 change it's one of the other doors. You know it's not the one he showed, which means the 2/3 chance must be for the remaining door.
There's also a bunch of online simulations for this that show it's 2/3 to switch. For instance, here.
It might not be as interesting, but it can definitely be useful.
As discussed in Simon Singh's excellend Fermat's Enigma, the research done by many other people may be built upon the assumption that a particular mathematical statement is either true or false. Until a proof is presented -- either by brute force or more elegant means -- it us unknown whether the "ediface" built on the assumption will stand or fall.
Since pure mathematics underlies a great deal of applied research, having mathematical statements proven true or false can tell us whether or not it's worth our time and resources to follow a particular line of reasoning.
As for the importance of pure research, I think you'll find that a huge number of people in this world are counting on some pretty miraculous discoveries being just around the corner, because based on what we know and know how to do today, we've got some serious problems on the way. Only pure research might enable us to luckily stumble across the right leads. After all, if we knew where to look, we'd already have arrived at the answers.
The operating system should be fault tolerant and not fail when a foreign(read: third party) application does some unexpected behavior.
For the most part, modern windows does not crash and burn when a third party userland application does stuff. There are certainly the occasional bug and wierd corner cases, but those are to be expected in any software system that was not designed to be proven correct.
However, if a driver has bugs there really isn't much the OS can do. A driver is sitting there in kernel space, and if it starts writing to random locations in memory or other funkiness it will bring down the box; this is true in most every operating system. Microsoft can not really be blamed for bad third party drivers when they misbehave.
While making a table of all possibilities is generally a good idea, you have to watch out that all the cases you are mapping out are equally likely. If you look at your table again, you initially pick the right door 50% of the time. That can't be quite right...
1 2 3 K S
P N N W L
P N N W L
P N N L W
P N N L W
(picking the right door 2 times out of 4?)
You are probably confused because in that case the host has two doors he can open, so he will open each of them 50% of the time. If you compensate for that by weighting these lines with a factor of 0.5, than you'll come out at the right 1/3 against 2/3 probability.
But probably the best way to get a feeling for this problem and how weird probability can be would be to find someone to play the host for you and just try it ;)
See the novel "The Curious Incident of the Dog in the Night-Time" by Mark Haddon, for a solution & a quick read from the point of view of an autistic savant. It, by the way, presents the opposing point of view on the Monty Hall problem.
Yes, but the table you draw lists those cases equally with your initial choice, but that is false. Monly's revelation is a seperate event. You're giving what is simply a subchoice the same weight as the main choices.
Let's assume, for the same of simplicity, that you always pick door number one. Since the first choice is completely random, this doesn't affect the final odds -- and it reduces the number of cases we need to look at fromo 15 to 5.
Now, to determine your overall probability of winning with a police of (not?) switching, we multiply the probability of each of the main cases by its probability of generating a win for you.
Therefore, in the Monty Hall problem, a policy of switching when offered the choice results in a 66% probability of win for you, while not switching results in a 33% probability for a win -- meaning that it is in your benefit to switch.
"Evil company X is threatening to restrict our rights! Let's all get together to stop--OOOH! SHINEY!!!" -- AC
This problem annoys the hell out of me because as stated the correct solution is to stick with your original choice, which agrees with intuition. Smarty pants math geeks will argue that you should switch since this wins 2/3 times while sticking with same door wins 1/3.
This is wrong since it is never stated that the host HAS to open a door and give you a chance to switch. What if he only opens a [wrong] door when he feels like it ? In this situation, you should NEVER switch [assuming the host does not want you to win] since the optimal strategy for the host would be to only open a door and give you a chance to switch if your original choice was correct.
So, this problem is used as a way for Maths geeks to show off that they are cleverer than everyone else because people's intuition tells normal people that there is no benefit in switching, and in fact, they're right.
I have NEVER seen a description of this problem where it is stated that the host always opens a door after the initial choice, so the "correct" answer is always wrong. I know of a couple of other questions of this type where the accepted answer is wrong - anybody else like to mention some ?
http://rareformnewmedia.com/
I would think that anyone who didn't want to restart an entire project like this would save state. You can never tell when there are going to be power problems, virus/worm problems, or even a stupid user that decided they needed that machine and crashed it.
Checkpointing is your friend.
Jeremy Baumgartner
I for one would find you hitting your hand with a hammer much more interesting then watching you work it out on pen and paper. ;)
I like my women how I like my sugar.. granulated.
It doesn't matter what happened on the show. This is a math problem, so the conditions stated are formal ones: The situation exists exactly as described, and there are no unstated variables or outside influences.
The problem states that the host opens one of the doors you didn't pick, and that there's no prize there. This ALWAYS happens, because this is a math problem, not a game show based in reality. Since it ALWAYS happens, the host-picked door (which is always empty) actually doesn't have any bearing on the problem. You can safely eliminate it from consideration. It's there, as a previous poster correctly stated, to confuse you. It seems to have been a big success.
In fact, you have and have always had a 50/50 chance, and it doesn't matter which door you choose.
Then you have never seen a correct statement of the problem, and the people you have heard it from are indeed idiots trying to look smart. A true Math geek would understand the importance of accurately stating the problem:
There are three doors. Behind one is a million dollars. Behind the other two there are goats. You pick one door. Monty opens one of the other doors to reveal a goat, and offers you the option of switching your choice to the remaining door. Assuming the location of the million dollars is random, and this pattern is always followed, should you switch?
That is the problem to which the correct answer is "Yes, you should switch." If the fundamentals of the problem are stated differently, the answer may be different.
Note that even if they state the problem correctly, they're not actually cleverer than anyone else, since they probably heard the answer along with the problem. If the person telling you about this is a true Math geek though, they probably aren't trying to look clever. They just think this problem is really cool and worth talking about specifically because their intuition fails it just like everyone elses.
Anyone interested in a great read involving chess, magic squares, knight's tours, acoustics, fibonnaci numbers, the French revolution and the 1970's programming scene, check out The Eight by Katherine Neville. Just finished it for the third time, and discovered the the last two years of my daily /. education helped me to appreciate and enjoy it even more. I apologize in advance for the amazon link; it was the only site that gave a decent balance of reviews.
However, try and think about what this problem really is mathematically, rather than in terms of chess or magic squares. A knight's tour requires the knight to visit every square on the board exactly once. Replace "squares" with "nodes," and "board" with "graph," and what we have here is the problem of finding a Hamiltonian path with some interesting constraints.
And that's where this problem gets interesting- finding a Hamiltonian path on a graph is known to be NP-complete, a designation which carries with it all sorts of baggage, including some of the million-dollar sort. The fact that the question of whether magic knight's tours exist on an standard 8x8 board required 60+ CPU-days to answer speaks volumes about the complexity of the problem, and demands answers as to how this complexity comes about, and why there is no solution with the given constraints. Far from being just a silly mathematical curiosity, this is a problem that presents a lot of potential applications with regards to algorithms, complexity, and computability. Also, if you can find an algorithm that finds Hamiltonian paths in polynomial time, you get the aforementioned free money.
So yes, the problem of finding a magic tour seems worthless if you only consider the problem literally in terms of a chessboard and magic squares, instead of as a model for other complex problems in mathematics, science, and engineering. But by the same token, how interesting and useful would the Traveling Salesman Problem be if it were only applied to traveling salesmen?
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
Apparently (judging my what Google turned up) I am mistaken ... but as yet unconvinced. I'll have to do something about that.
At least I'm not trying to get a job at Microsoft.
This is the best way of thinking about this problem.
What everyone seems to have missed is the *initial chance* at picking the *wrong* door.
The key is this : If you initially pick the wrong door, you MUST win if you switch, since Monty ONLY EVER SHOWS YOU AN EMPTY DOOR, and the only other choice is the winner.
Therefore the chance of a win (if switching) is identical to your chance of picking a loser initially (2/3).
If you never switch, your chance of winning is only 1/3 - since you never change your mind from your initial pure chance guess.
Prior Restraint (179698) said:
The error that you've made in this analysis can be summed up in the first two lines of your table. In the case where the player chooses the correct door, it is irrelevant which door Monty choses, so they are not two separate cases as you have shown. Monty could always pick the lower-numbered door and not change the problem.
Why not run a simulation if you don't believe?
#!/bin/shrand2 () {
dd if=/dev/urandom bs=1 count=1 2>/dev/null |
tr '\0-\177' "${1#?}" | tr '\200-\377' "${1%?}"
}
rand3 () {
two="${1#?}"
unset rand
while [ -z "$rand" ]
do
rand=`dd if=/dev/urandom bs=1 count=1 2>/dev/null |
tr '\0-\124' "${1%??}" | tr '\125-\251' "${two%?}" |
tr '\252-\376' "${1#??}" | tr -d '\377'` done
echo "$rand"
}
echo "runs prize choice monty other stay switch"
while
do
prize=`rand3 123`
choice=`rand3 123`
monty=`echo "123" | sed -e "s/$prize//" -e "s/$choice//"`
if [ "${#monty}" != 1 ]
then monty=`rand2 "$monty"`
fi
other=`echo "123" | sed -e "s/$monty//" -e "s/$choice//"`
[ "$prize" = "$choice" ] && stay=$(( $stay + 1 ))
[ "$other" = "$prize" ] && switch=$(( $switch + 1))
runs=$(( $runs + 1 ))
echo "$runs $prize $choice $monty $other $stay $switch"
done
That's a really good explanation but I'm having a hard time considering the third door as part of the equation. You are given the chance to win or not win a prize. (And to have a psychological ride thanks to fear and uncertainty)
Eg.
Host says pick between door 1 and door 2.
Host says 'Are you sure? Do you want to switch?'
The way I see it, the third door is irrelevant. You are always making the following choices:
1) Pick from a winning or non-winning door.
2) Choose to keep the same choice as above or choose another.
The fact that the host opens 1000 doors and let's you choose to change them doesn't increase your chances if, ultimately, you are left with two doors. It only matters you are ever not left with two doors.
Eg.
Choose from four doors: I choose A.
Well, door D doesn't have the prize.
Choose from three doors: I choose A.
Aha! A does not have the prize. You lose.
It seems like the Gambler's Fallacy at work here. Ultimately it only boils down to the FINAL choice you make when the win-loss decision is made. The rest has no bearing (other than, again, psychological) on the final decision.
So, thanks for the helpful Matrix. I'll be stubborn and consider the problem a 50-50 chance. And you should usually go with your first instinct anyway.
sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it.
sooo... they ran a distributed client on all the computers on a reasonably-sized engineering campus and came up with a answer in how many hours? In 97 there were 465 PCs on UMR's campus (more computers than women enrolled at the college), and I'd imagine they're probably all 1+ ghz by now (considering 1ghz PCs have been out for nearly 4 years now) and they may have more PCs by now.
my karma will be here long after I'm gone
You pick a door. You have a 2 in 3 chance of getting a loser. A bad door is removed, since 2 out of 3 times you have a loser, 2 out of 3 times a switch gives you a winning door. 1 out of 3 times a switch will result in a lose. The key is monty knows which doors are empty and after your initial choice if you were correct he will never open your door, but you only had a 1/3 chance of being correct, so 2/3 of the times he will provide a situation where switching is better.
--
WHO ATE MY BREAKFAST PANTS?
Your probabilities are screwed.
Although there are nine outcomes, obviously they are not equally probable. Monty cannot open the door that you picked, nor can he open a door with a prize behind it. Therefore, most of these have a probability of zero.
True BUT your logic is flawed in that they're all either 0 or equally probable. S is just as likely to happen as T or W or Y. Let's show all possible routes given a choice of door 1:
\ 1 2 3 - shown
R y n n - 1
S y n n - 2
T y n n - 3
U n y n - 1
V n y n - 2
W n y n - 3
X n n y - 1
Y n n y - 2
Z n n y - 3
Since we're listing all possible situations, each route has a probability of 1/9. Agreed?
Now lets remove the incidents where Monty cannot open the door picked or the door with the prize:
\ 1 2 3 - shown
S y n n - 2
T y n n - 3
W n y n - 3
Y n n y - 2
Now we're listing all possible situations considering Monty's information. Thus each route has equal probability. 1/4.
Hence if you stick with your door (route S or T) then you have 1/2 chance of being right. If you change (route W or Y) then you also have 1/2 a chance of being right.
Alternatively look at it this way.
If Monty shows you what's behind one door, then the prize is behind one of 2 doors... hence you've got a 1 in 2 chance of being right no matter what door you choose.
Pinky: "What are we going to do tomorrow night Brain?"
Brain: "I would tell you Pinky but this 120 char limi
Changing your choice makes no difference!
You don't know what door the prize is behind, the game show host revealing one of the doors (That doesnt have the prize) doesnt change the fact that your choice still has the same chance as any other door (except the one revealed).
Everyone that disagrees with me is a paid shill
Look, it doesn't matter what the host was thinking when he opened the door. The probabilities don't change depending on whether he wished to open a door with a prize or not. If it so happened that he opened the door with the prize, then your choice would be really easy. But he didn't. You just need to look at the conditional probabilities. The conditional probability that the prize is in the other door, given that he's opened a door with no prize, means that you should switch. That's why mathematicians state the problem the way they do.
With great power comes great fan noise.
ok, look. you're all being thrown off because you don't realize that one wrong door virtually doesn't exist. A wrong door will be eliminated each time. Your chance of landing on the right door from the start is 1 in 2 even though there are 3 doors because one of the incorrect doors, will be eliminated. It doesn't matter whether you switch or not, the odds are 1 in 2 to start, and 1 in 2 after the third door is gone. If there are 100 doors, and 98 of them are removed after you choose one that is wrong, and you are then offered to choose again, your odds are still 1 in 2. It comes down to you having one right and one wrong possibility in this scenario, from start to finish. 1 in 3 NEVER exists.
If all else fails, just count. Call the doors A, B, and C, and have the contestant choose door A. Case 1: there's a prize behind the door. Monty can open door B or door C: two possibilities. Case 2: there isn't a prize behind door A. In that case the prize is either behind door B, and Monty opens door C, or it's behind door C and Monty opens door B. Also 2 cases. Probability that prize is behind door A: 1/2.
For pity's sake, kids, this isn't quantum mechanics with some sort of spooky action at a distance which somehow magically moves the prize in a way that you can predict (although some real-world game shows sometimes appear to work that way;). It's elementary counting, so if you end up with a counter-intuitive result, the chances are that you haven't understood what you're doing.
(Whether God plays game shows with the universe is left as an exercise for the humor-impaired, who will post to /. and get moderated +1 funny by other humor-impaired denizens and +1 insightful by those who regard /. as being little more than a game show itself these days.)
When they did the proof of the 4 color theorem, one mathematician said (IIRC) that a proof should be elegant and small, and that a brute force proof is like a phone book.
To make laws that man cannot, and will not obey, serves to bring all law into contempt.
--E.C. Stanton
Oh, bother. I'm an idiot.
Yep, it seems so obvious now. I'll just sit in the back here and let the grownups do all the talking.
Your math seems sound, but you forget that there is a human aspect in deciding which door is opened.
Your probability calculations are usaeless when you throw the cunning of another human mind into the mix.
Now, instead of asking yourself "what is the probability", you ask yourself "hey, does the guy who removed the door know the probability, trying to trip me up?"
Unfortunately, the probability of that depends entirely on the person, and is thus probably best represented as 50/50. Maybe the person is leading you on to force a switch, or maybe it really is the prize door.
So your chance of willing, thanks to the person involved in the loop, is still 50/50.
Man is the animal that laughs.
And occasionally whores for Karma.
-1 (Not Paying Attention) for me :)
Jeremy
Since it ALWAYS happens, the host-picked door (which is always empty) actually doesn't have any bearing on the problem. You can safely eliminate it from consideration.
WRONG. Your choice had a 1/3 chance of being right because there were 3 doors to begin with, among which you chose randomly. Therefore all 3 of those doors are important to the problem, because they specify the conditions in which your first choice is made. Just because the host removes doors doesn't suddenly change the probability of your *initial* choice.
To make it more clear: say there are 1,000,000 doors. Choose one randomly. Not a very good chance of being correct, right? (1/1,000,000). Now the host opens all the doors but yours and one other, showing that they are empty. Would you now go and say that your initial choice has a 50% chance of being right?
If you would, then you're a fool. Because the other door has a 99.9999% chance of being the correct one. Think about it -- your original choice is still your original choice, made out of a million doors. The *other* door is basically the host saying "well, if you chose the wrong door, then *this* is definitely the correct one." Since the chance of you having chosen the wrong door at first is 999,999/1,000,000, then that means the chance that the other door is correct is 999,999/1,000,000 as well.
This logic works for 3 doors, as well, but for some reason doesn't seem as intuitive.
The following sentence is true. The preceding sentence was false.
No, you couldn't. You could have never picked the door without the prize that Monty was going to open. Monty knows there are two doors with no prize. So he picks one of them: 50% of the time its the door without the prize that you didn't choose.
This is a question of precision and accuracy. You know going into the game that there are precisely two doors with no prize. You just don't know with accuracy until after the prize is revealed.
Think of it this way: You never have a first guess because, regardless of which door you choose, Monty will always have a second empty door to try and distract you.
The more I think about this, the more it sounds like Gambler's fallacy to me. When you ultimately choose between two doors (regardless of the fact that you had already chosen one of the doors) you have a 1 in 2 chance of picking the right door.
sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it.
Argh! There goes any chance of me working with probabilities ever again!!
Finally worked it out. I'm off to sulk.
Pinky: "What are we going to do tomorrow night Brain?"
Brain: "I would tell you Pinky but this 120 char limi
Holy crap. It's amazing seeing people like you stoop to insults to try to defend something that has been proven mathematically false many times over.
You see only that he opens a door without a prize. You can't tell whether he had a choice between 2 doors (you picked right) or his move was forced (you picked wrong and there's only one other non-prize door). It's not a case of Monty "not really giving you any information" (whine, whine, life is so unfair). Monty is simply giving you no information.
OK, let's take "information" out of the discussion right now. Information is defined by how probabilities are changed by certain actions. So, deriving probabilities from "amount of information" is circular. Let's look directly at the probabilities.
If all else fails, just count. Call the doors A, B, and C, and have the contestant choose door A. Case 1: there's a prize behind the door. Monty can open door B or door C: two possibilities. Case 2: there isn't a prize behind door A. In that case the prize is either behind door B, and Monty opens door C, or it's behind door C and Monty opens door B. Also 2 cases. Probability that prize is behind door A: 1/2.
Counting is a good idea, and you do it well. But you neglect to the apply some very basic probability theory to what you've counted.
Case 1 -- yes, the host has a choice of which door he can open. But what you are neglecting is that Case 1 itself -- ie, that the door you chose was the correct one -- has a probability of 1/3.
Case 2 itself, likewise, has a probability of 2/3.
Reiterating: in your initial choice, you have a 1/3 chance of choosing the correct door, and a 2/3 chance of being wrong. Case 1, 1/3. Case 2, 2/3.
If you don't agree with me at this point, I suggest you stop spewing your crap and just get out of the conversation.
Alright, now when case 1 occurs, the host has a 50/50 choice of which other door to open. Therefore, in the grand scheme of all outcomes, him opening the first door has a probability of 50% * 1/3 = 1/6, and him opening the 2nd door also has a probability of 1/6.
Now, in case 2, he can only open the door that doesn't have the prize. Within case 2, there's a 50% chance of the prize being behind either door. Therefore, among all possible outcomes, him opening the first door has a probability of 50% * 2/3 = 1/3. Same with the second door.
Let's reiterate:
Case 1 -- host opens first empty door, 1/6
Case 1 -- host opens 2nd empty door, 1/6
Case 2 -- host opens first door, 1/3
Case 2 -- host opens second door, 1/3
So, as you can see, you certainly counted correctly. Congratulations. But you neglected the elementary fact that The probabilities for each of these events is not equal.
The probability that the prize is behind the door you picked is still 1/3, and the probability that the prize is not behind the door you picked (and is therefore necessarily behind the other closed door) is 2/3.
If you still don't believe me, I suggest you go read the rest of this thread. There are several very good explanations. Or go find that java applet that performs the experiment for you, and shows that if you switch, you win 2/3 of the time.
If all else fails, go back and take your elementary probability theory class again, and don't cheat off the guy sitting next to you this time!
The following sentence is true. The preceding sentence was false.
I explain it by saying that despite the fact you are not the first person in this thread to say that real-world tests have been performed, no reference to a well thought out trials scenario has been presented. So far, all these real-world tests are hearsay.
And I can also explain it by saying that mathematical errors can lead to "prove" something that is incorrect.
sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it.
The AC is right. Choosing from three doors in the first situation and then choosing from two doors after Monty shows you the empty door are dependent events. If they were independent (the prize gets assigned to one of the doors after you chose), then your analysis would be correct.
You talk about 1000 doors, but take it to the extreme. Pick a set of lottery numbers (1 in X million), then have someone listen to the drawing and then offer you two sets: your set and another set, one of which is the winning combination. Are you honestly saying that it's a 50/50 chance?
I gotta call BS on this... if you are shown one empty door, the odds that either of the remaining doors has the prize is 1/2. If you choose after being shown an empty door, you chances are 1/2, no matter which door you choose, even if it's the one you saw before. You're not "choosing" again if you always switch. If you want I can hack up something to simulate a few thousand cases - that doesn't prove anything, but it's a good demonstration.
...cancer remains uncured.
Perhaps you fail to realize that brute-force and enumerating every possible circumstance is a proof. I think that whatever he did sufficiently proved whatever it is that he was trying to prove (from the website, they can't even seem to agree on what a "magic tour" is). However, you are correct that it wasn't particularly graceful or impressive.
Don't worry, though, he'll probably reverse-engineer a tidy proof within two months or so. Sometimes it only requires the answer to figure out the solution.
Here's yet another explanation. Suppose you choose door #1 (you can do this for #2 and #3 yourself). There are four possible outcomes (format is case letter followed by choice-shown-actual):
W 1-2-1
X 1-2-3
Y 1-3-1
Z 1-3-2
But notice W and Y have the actual prize behind #1. Since the odds of it being behind any door is 1/3, W+Y = 1/3. Since W & Y are just as likely, they're each 1/6. So, the odds are: W(1/6), X(1/3), Y(1/6), Z(1/3).
If you think all four should have equal probability, think about this: He hasn't shown you a door yet. Two of the cases have it behind #1. Do you think by selecting #1 that you actually make it 1/2 chance that it really is behind #1 even before he shows you anything, and 1/4 chance of being behind #2 or #3?
So now he shows you a door. If he shows you #2, it could be either W or X. Notice X has twice the probability of W. Likewise, if he shows you #3, it could be either Y or Z. Again, Z has twice that of Y. Both X and Z are cases you should switch your choice, and give you twice the probability of winning.
If you have 100 doors, and one is correct, this would mean that the 'keep' door 99 times out of 100 is an incorrect one? While you have only two choises, the choises themselves aren't balanced.
Sure - go ahead.
...
Just remember - the contestant picks first. Monty must pick a *different, empty* door.
So the chance you're right between two doors is 1/2, provided Monty doesn't give anything away by eliminating a door... But did he give anything away ?
He did, because he always has to open a losing door: one losing door is always eliminated. The probabilities of your initial choice being correct, and the remaining choices have to sum to equal one. Therefore, the probability of the remaining choices have to sum to equal one minus the probability of your initial choice. In this case (with three doors), they have to sum to equal 2/3. Say a door isn't opened. Then, you would have two to switch to (if you choose to switch - this would be like "changing your mind"), and your chance of picking the correct door would be 1/2 * 2/3. Well, that's 1/3, just like your initial choice. But if Monty has to open a door, then you'll only have one door to switch to. In this case (which is the Monty Hall problem), you'll pick the remaining door - so that'd be 1 * 2/3. And that's a probability of 2/3.
Imagine that there were a million doors. Also, after you have chosen your door; Monty opens all but one of the remaining doors, showing you that they are "losers." It's obvious that your first choice is wildly unlikely to have been right. And isn't it obvious that of the other 999,999 doors that you didn't choose; the one that he didn't open is wildly likely to be the one with the prize?
(quoted without permission from http://www.io.com/~kmellis/monty.html
hack up something that simulates EXACTLY what the monty hall problem suggests. You'll find that always switching yields success 2/3 of the time.
To put it another way, always staying yields success 1/3 of the time. When you first picked one of the doors, you had a 1/3 chance of being right. When Monty reveals a booby-prize door, there's NO WAY that your 1/3 chance becomes 1/2.
Ceci n'est pas une sig.
A note to all the people writing code to solve this, the key to this problem is that Monty intentionally chooses a door that has no prize behind it.
Interestingly enough, if Monty suddenly forgets which door has the prize and just chooses a door at random, it still results in a 2/3 chance of winning (assuming him opening the door with the prize is a win by default).
"Since we're listing all possible situations, each route has a probability of 1/9. Agreed?"
No, no! Not at all. Some of those are actually impossible to actually occur. If you pick door 1, Monty can't show you door 1. Hence, it has a possibility of 0/9, or just 0.
Each route does NOT have equal probability. Take a dice with 6 sides, and roll it. Lets say you look at two cases.
You roll a 6.
You roll anything else.
Obviously, the second case is more likely to occur . Can you now agree that different cases can have different probabilities?
Thanks, penguiN42.
Knight's tours... Sample space... Early morning...
<Monty mode="python not hall">
My brain hurts...
</Monty>
what are you smoking, buddy?
Not the same thing as you are, buddy.
When you open one door and you are presented with the chance to switch your selection, you have a new independent problem. No matter how you try and reduce the arguments using strong language, the fact is that the phisical action of blasting one door to ashes
1.- Has no effect whatsoever on the location of the prize. The prize will not switch places.
2.- When you are presented the choice of changing your mind, you are presented with a new problem, regardless of the ammount of doors that have been opened (or blasted) you still have in front of you two doors, each of one having the same probability of keeping the prize.
No matter what has been done, when you ask the player if she wants to change her selection, you are presenting a new problem, independent of previous incidents (blasting of doors). At that instant in time (you could argue that such things cant be measured) you have two doors with a 1/2 probability each.
Life isn't like a box of chocolates. It's more like a jar of jalapenos. What you do today, might burn your ass tomorrow.
Maybe a quick rewording of the problem that changes nothing will show you all the truth. Imagine for a moment that you have picked one door, and that Monty then gives you a choice of having both the other doors as your choice, or the door you initially picked. You would definitely switch right? 2/3 instead 1/3. That is precisely the same thing the other problem states, except that in my version he already opened one of the two for you. You definitely should switch, to take advantage of the 2/3 probability.
A man walks into a bar. The bartender says, "What is this, some kind of joke?"
I'm convinced now. One mistake I was making was failing to realize that Monty's choice of doors is already restricted by my first choice. I think that if he could also choose my door, I'd have only a 50/50 chance. Of course, that's still better than the 1 in 3 chance I start with, so I should still take the odds.
The way I thought of it was this: I have a 1 in 3 chance my first pick, then Monty shows me an empty door. If I stick with my first choice, nothing changes -- Monty's showing me one door is meaningless if I don't act on it, and it might as well not have happened. So my odds are still 1 in 3.
The interesting question is: What are Monty's choices? Only in the 1 in 3 chance that I've already chosen the prize door is Monty able to choose between two empty doors to show me. In the other 2 of 3 scenarios, he has no choice but to indicate the prize door by showing me the only remaining empty door.
This logic works for 3 doors, as well, but for some reason doesn't seem as intuitive.
Maybe because 999,999 / 1,000,000 (.999999) is a lot closer to 1 than either 1 / 2 (.5) or 2 / 3 (.6666...)
But, yes, the absurdity of the million-door scenario illustrates the solution, which I now see as the correct one.
yeah, so, i'm wrong. my bad.
It seems to me that rather than talking about mathematicians and non-mathematicians, you are talking about pure and applied mathematicians. Most people wouldn'y invent anything!
All of this has been addressed, at length, far too many times on usenet. Read the rec.puzzles archive entry.
Seems to me that this guy would have done better to take a few computer science courses before attempting this. My first iteration of the problem produced results similar to his - it could take billions of moves to calculate one solution. But by refining the algorithm so that squares with the highest number of "accessible" positions were tried first, I reduced the number of moves to solution from several billion tried to several thousand.
I guess it just goes to show that even though computer science started as a branch of mathematics, they have really become two discrete disciplines. A good computer scientist would not have needed 150 computer days to solve this problem; a good mathematician wouldn't have needed a computer. Sadly, the only thing his "solution" has shown is that he's neither good at mathematics, nor computer science.
I too used to think that I was smart, until I was exposed to college. As I worked through college, I found that many of my "bright ideas" had already been implemented by people who had come before me; I was simply unaware of the solution. Had this guy done a bit of research into computer science first, he would have saved himself the embarassment of spending 150 computer-days to solve a standard textbook problem.
The society for a thought-free internet welcomes you.
You'd think so, but I stumbled on an algorithm for it back in college (for a programming challenge on an Apple ][, no less) - start in one corner, pick a direction, and spiral around, always picking the outermost available spot. I didn't have any reason for thinking this would work, I just thought that was an interesting starting assumption.
Oops... yes, it does make sense, put that way... which is what my simulation shows, as well. So, now I look a bit silly, but I got more coding practice than I've had in weeks, so there's some good out of it. Maybe, just for laughs, I should release the code :-)
Actually, given a certain interpretation of the problem, the probability is 1/2... Let's consider the Canadian version of the TV show, where no one thinks to tell Monty which door the prize is behind, so sometimes (1/3 of the time, actually), he opens a door with the prize behind it, and you lose. Now, let's consider that when you were on the show, you got lucky, and the course of events was as follows: you chose, Monty opened a door and there was nothing behind it, and gave you the choice whether to switch or not. What's the probability that if you switch you'll win? It's exactly 1/2.
To prove this, assume WLOG that you chose door #1. Now, before Monty opens a door, there are six possibilities (designated by the door Monty opened and the door the prize is behind):
- 2-1
- 2-2
- 2-3
- 3-1
- 3-2
- 3-3
All are equally likely (again, because Monty doesn't know which door the prize is behind). So now he opens a door, and the prize isn't there. So this eliminates possibilities 2 and 6 from the above list, leaving only possibilities 1, 3, 4, and 5, all of which are still equally likely. Thus, you win half of the time and you lose half of the time.Note that if Monty does know which door the prize is behind, the six possibilities are not equally probable, and your chance of winning if you switch is 2/3.
One of the devious things about the Monty Hall problem is that it depends upon an implicit assumption that Monty knows which door the prize is behind. If he doesn't -- but the prize doesn't turn out to be behind the door he opens -- the probabilities change! Looking at the problem from the outside, without knowledge of what Monty knows and when he knows it, you can't tell exactly what the real probabilities are.
To within half a percent, pi seconds is a nanocentury. -- Tom Duff
Do you rely on works of fiction for all your mathematics? If so, we're all human batteries that defy the laws of thermodynamics..
Yeah, the version they run here, they can eliminate any of the four.
Usually the host asks you first, which you think are most likely, or what you are trying to decide between, and usually the two that you are trying to decide between are the two that remain.
Contestants have since become more cunning, and refuse to reveal what their favourites are.
Then of course the ones that get eliminated are the silly options. Leaving the similar or ambiguous answers. I can't bear the show with the sound on cos the talk is such drivel, and I can't watch it at all now, cos I got rid of the TV.
Now I waste my time on Slashdot.
-- it must be true, it's on the internet.
Not the same thing as you are, buddy.
Well maybe you should, because you're coming off as a real idiot.
1.- Has no effect whatsoever on the location of the prize. The prize will not switch places.
The fact that you can state this and not make the connection to why you are wrong is strong evidence of your stupidity. Think about it. You had a 1 in 3 chance of picking the right location. You state the prize does not switch places. Clearly there is a 2 in 3 chance that it is somewhere other than your initial selection.
No matter what has been done, when you ask the player if she wants to change her selection, you are presenting a new problem, independent of previous incidents (blasting of doors). At that instant in time (you could argue that such things cant be measured) you have two doors with a 1/2 probability each.
Here's one last chance to see the error of your way; I'll restate the problem to the point where it should be absurdly obvious. I have a deck of cards and I'll give you a prize if you happen to select the ace of spaces (AS). What are the odds of you getting it on your random pull from the deck? Having made your selection, I show you one of the other 51 cards that is not the AS. Then I show you another. And another. And so on until I have two cards and show you the one that is also not the AS. I then give you the opportunity to switch from the card you had selected initially to the one remaining card I am holding. What will you do?
If you say it doesn't matter, that it is a new problem, and that you still have a 50/50 chance of having the AS, I will not only keep you in my foes list for gross stupidity, I will also seek you out so that I might have a chance to gamble large sums of money with you.
Yeah Anonymous Coward finally drummed it into my thick skull. Actually I cracked the logic by thinking of it in the following terms:
;-)
"If the prize is behind the other two doors then Monty guarantees you win when you switch by opening the door without the prize. Thus you have 2/3 chance of winning if you switch."
Then I eventually worked out where I went wrong with the previous examples.
I was actually right in the claim that each route had a probability of 1/9 because I was looking at the probabilities as if Monty would open ANY door. THEN I removed the impossible situations but did not realise that it's the probability of S and T occuring must sum to 1/3 because that's the chance that the prize is behind door 1.
Now I remember why I hated probabilities.
Pinky: "What are we going to do tomorrow night Brain?"
Brain: "I would tell you Pinky but this 120 char limi
Actually, it makes your math look worse. According to you, this program evaluated 680 billion moves per second. Kind of interesting considering that the processor on which they ran the evaluation has a theoretical maximum of 4 billion instructions per second!
But that's not the point - brute force is always the least efficient solution.
so the program had to enumerate and check all possible knight's tours
Unless, of course, that the program's author could formally prove that the algorithm would eliminate non-magical tours before the evaluation began. The point of algorithm analysis is not merely to write a program which will enumerate and check every possible knight's tour, but rather, one that would eliminate non-magical tours as quickly as they could be proven non-magical.
The society for a thought-free internet welcomes you.
As long as you didn't steal any of it from SCO. :)
I'm just returning from a week of vacation and on reexamining the problem I see your point (dont know if this is going to be read anyways). Don't know WTF happened to me last week, but slashdot should offer the posibility of deleting embarrasing posts.
Anyways, in none of my posts I referred to you as an stupid, and the one who brought harsh language to the thread was you.
And regarding the large sums of money, feel free to place bets (worked as a poker croupie for four years)
Life isn't like a box of chocolates. It's more like a jar of jalapenos. What you do today, might burn your ass tomorrow.