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
I hear Hogwarts will be selling these once the last book is finished and they run out of money.
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!
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.
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.
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?)
Not necessarily. As the article points out, there is a proof for certain sizes of chessboard, but it doesn't extend down to 8x8. Not all mathematical proofs are quite as neat as we might like them to be in terms of how they apply to other variants on the same problem.
++ Say to Elrond "Hello.".
Elrond says "No.". Elrond gives you some lunch.
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.
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.
...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.
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.
Four color theorem.
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
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.
That's the four-color theorem, where the only known proofs use a computer to find irreducable sets.
:-) There are several nice proofs that take care of the majority of cases, just none that cover every case.
Note that there isn't actually a proof that there is no proof, we just haven't found one.
Twenties Retirement