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
But are there any practical applications, or is this a climb the "nerd mountain" type of thing?
Accentuate the positive, don't waste your mod points on the negative.
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
sure, if you just leave a single (well written) program running by itself windows is fine. Just don't try to do 2 things at once.
- You are on a famous game show and being presented with three doors, behind one of which there is a fantastic prize, and the other two lesser prizes or sand or something.
- You choose one of the doors.
- The host opens one of the remaining doors to demonstrate that it does not contain the fantastic prize, and offers you the opportunity to switch your choice.
Do you? Mathematically speaking, I've always been told that you should, because your first choice was a 1 in 3 shot but after the door has been opened you are being given a 1 in 2 opportunity.However, I just wrote a quick demonstration program, and found out that this isn't the case, and as you've probably expected it really is 1 in 3 no matter which way you go. You win this one, high school math teacher.
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!
Exactly. Bash MS all you want, but just remember that the next big worm to go around could use all those CPU hours in a row (at idle priority even).
uptime is nothing to brag about, unless you're talking about your penis.
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.
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?)
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?"
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
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
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.
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.
moron. there's a bug in your app.
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.
My workhorse XP box was up for 1.5 years until that damn power outage killed my UPS.
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.
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.
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
Sir Paul McCartney did make a Magical Mystery Tour
Only a third of the time then will Monty have the choice between two "no prize" doors, and thus only a third of the time would you win if you stuck with your initial choice. Its Monty's constrained behaviour that helps you out here; don't fall into the trap of thinking he is acting at random.
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.
I guess you didn't put many patches on it then.
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.
"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.
If this isn't right I'd love to see how. As it demonstrates what I have always thought.
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.
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.
So do we assume there is still and elegant proof out there?
>Yeah I realize occams razor isn't a always applicable if the only solution is tedious. But everything does seem to tend toward simplicity.
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
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."
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.
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
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.
"corresponding to 138.25 days of computation at 1 GHz"
This is a completely useless metric. An Athlon requires less CPU cycles than a P4 to do the same amount of work. Did they use a 2GHz Athlon?
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
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.
I don't think fark has much moral authority to criticize. That place makes Slashdot look like a National Academy of Sciences meeting.
-1 (Not Paying Attention) for me :)
Jeremy
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.
> surely a distributed client running on many PCs would be a godsend for solving major maths problems
It is. Here are the mathematics problems being solved or studied by distributed computing right now:
http://www.aspenleaf.com/distributed/ap-math.html
It doesn't matter whether the host HAS to open a door. But (in the correct, original statement of the problem), the host DID open a door, which had nothing behind it. That's all you need to know in order to conclude that it would be advantageous to switch.
I used to do a knight's tour as a part of a memory demonstration - how I earned my way through college. I would have someone pick any spot on the chessboard to start with, then I would tell them the moves to make to do a magic tour, and I could not see the board. It was impressive as hell. It was all mnemonics.
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.
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?"
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 :-)
It's not too hard. Each of the 64 squares is an image which is tied to the number of the square.
1=t or d, 2=n, 3=m, 4=r, 5=l, 6=ch or sh, 7=k, 8=f or v, 9=p or b, 0=s
square 39 is an image tied to the word 'map'.
The image connected to the 'map' tells you the number of the next square to jump to. The more absurd the way the images are tied together the easier it is to remember what comes next. You're just telling a story. Whatever square they put you on you start the story there.
A 7 year-old could be taught to do it. Mnemonics - in this case converting numbers which are meaningless into images which are unique in the way that they can be visualized in the mind, then the other image is turned back into the next image and connected to the image representing the next number, and so on, ad infinitum.
I have compiled every possible outcome of the 3 doors game, and posted the file on this website: http://68.113.6.222/proof.txt . Read this and tell me what you think.
Remember: Although some possible games may appear to be, in effect, the same, I have written every possible sequence of physical events that would constitute a legal game.
As a helpful illustration, consider this:
At the moment I begin to play the game, parallel universes are created. In each universe, one possible game is played out. According to the proof, in exactly half of those universes, I walk away a winner.
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.
... about what a mathematical proof is. If you can prove that your brute force algorithm will enumerate all possible possibilities, and determine if any satisfy a condition then a run of your algorithm and it's output along with your proof of the correctness of your algorithm IS a mathematical proof.
> This is a "standard" problem in many computer science texts!
The stated problem is not to find a knight's tour on an 8x8 chessboard - it's to find a magic knight's tour on an 8x8 chessboard. If you read the article, you'll learn what a magic knight's tour is. It turn's out that there's no such thing as a magic knight's tour on an 8x8 chessboard, so the program had to enumerate and check all possible knight's tours in order to prove this.
> My solution took a few seconds as opposed to 150 days - and that was back when pII 400's were the fastest thing around.
There are 8,121,130,233,753,702,400 different knight's tours on an 8x8 chessboard. So in 138.25 days their program checked over 6.8E11 tours per second. That makes your solution look a bit pathetic, doesn't it?
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.