Hi
Which well-known mathematical puzzles have not been solved yet? I look forward to your feedback. Feel free to mention obscure ones too.
davidmich
Given that you’ve called them “puzzles” rather than “problems,” I wonder if you think that they’re cute little puzzles that you might get lucky and solve in a long afternoon. They’re not. They’re the sort of problem that you’d generally need to get your Ph.D. in math and then spent several years of your free time working on to have a good chance at solving them. Often it takes a considerable background in math to be able to understand what the question is.
Thanks Indistinguishable. I wasn’t aware of a wikipedia site that kept tabs on math problems. Very helpful. Thank you.
davidmich
Ian Stewart’s Visions of Infinity: The Great Mathematical Problems is a must read on this subject.
He starts with the simplest concepts and then shows how each advance in mathematical understanding brought new answers to old problems along with a host of deeper problems involving newer math. As he gets closer to the present, he introduces more and more problems that have not yet been fully solved, although partial solutions point the way to complete understanding.
Merely stating the more recent problems in lay language becomes nearly impossible about halfway through the book. Even so, he makes it worth the while to stay with him till the end to get hints about the mathematical landscape in places you’ll never be able to traverse.
Although some of them give that impression. To the naïve, things like the Goldbach Conjecture or the Collatz Conjecture look sort of like cute little puzzles that one ought to be able to figure out just by thinking about them hard enough. (Fermat’s Last Theorem, too, if Fermat had been correct about having a valid proof that wouldn’t fit in the margin.)
On the other hand, there have been examples of problems that really were “cute little puzzles” with neat simple little solutions (that have long since been solved), that nevertheless spawned broader and deeper areas of important mathematics; the Konigsberg Bridge problem comes to mind.
Well, some of them you certainly could get lucky with. Take the P = NP question. While it’s very like P does not equal NP, all it would take to prove them equal is finding one NP-Complete problem that could always be solved deterministically in P time.
Finding this is incredibly, astoundingly unlikely (especially given that, as I said, we’re pretty sure that this isn’t possible) – but theoretically some yokel programmer could plop out a solution while writing a shitty Tetris app without even knowing they stumbled upon the greatest mathematical/computing discovery perhaps ever. In fact, it’s a case where – if such a solution exists – not knowing the problem may be a benefit (like the Niels Bohr story).
Of course, it’s far more likely that some professor or industrial researcher will someday prove P =/= NP with a boring 20 page proof incomprehensible to all but the most practiced theory of computation professionals, but there are certainly hard problems that could, conceivably, be solved accidentally in an afternoon with absolutely no formal understanding of the problem at hand.
An ancillary question: How do we know that these problems actually have answers?
Leopold Bloom thinks about how he may afford to pay for a country residence:
What rapid but insecure means to opulence might facilitate immediate purchase?
[…] A solution of the secular problem of the quadrature of the circle, government premium £1,000,000 sterling.
A lot of them fairly obviously have answers, simply by the way they’re worded. For others, “<x> is impossible to do” is a valid solution to the problem. Take the problem of writing an algorithm to determine whether an arbitrary computer program* will halt (meaning: not run forever). This is known as the “Halting Problem” and is the textbook example of the class of computing problems known as “non-computable”. This means that the answer to “write a computer program to determine whether another arbitrary program will eventually halt” is, in fact, that it’s impossible.
- A magical, theoretical, math-land computer. Obviously any real program will halt sooner or later because the laws of thermodynamics are a bitch.
We don’t. It’s thought that some of these problems are unprovable. Mathematicians know that any system of math complicated enough to be called a system must have problems that are unsolvable within that system. (See Gödel’s incompleteness theorems.)
But proving that they are not provable would be extremely valuable. Even besides the new and interesting math that would be required to do so, there are many problems that people know would be provable if only theorem x were true. If they know they can’t use theorem x, they could move over to try different approaches and not waste more time.
Stewart’s book goes into this in great detail, BTW.
Just writing the program isn’t enough, though; you’d have to prove that it correctly solved the problem for all instances in polynomial time, which is not necessarily particularly easy. (Indeed, we already know, for every formal proof system T, that if there’s any program T proves to solve NP-complete problems in polytime, then there’s a very particular such program which we already know how to write [the “Run, in dovetailed parallel, all programs which T thinks solves this problem” program]).
A better example of one you could get lucky with would be the Goldbach conjecture; just find a counter-example (which would be easily validated to be a counter-example), and you’re done. Of course, you’d be incredibly lucky to stumble upon such a thing…
Leopold Bloom should have read up on constructible numbers and the Lindemann-Weierstrass theorem. His other proposed methods of enrichment were all much more plausible.
Well, okay, you have me there. But even having such a program sitting there that actually works is such a humongous step towards solving it that proving it correct, while perhaps far more complex than just a formality, is still pretty close to “some yokel solved the problem” IMO.
As Exapno indicates, we don’t know that most of them have satisfying answers. It may be that there’s nothing interesting to definitively conclude about most of them (that there’s not even an interesting argument that they are undecidable in any interesting formal proof systems, nor even an argument in any interesting formal proof systems that there’s no interesting proof that they are undecidable in any interesting formal proof systems, nor even…). There’s just the hope that there does turn out to be something interesting to say…
Some open problems of a finite nature, though (e.g., does chess have a strategy for white to force a win, a strategy for black to force a win, or strategies for both sides to force a non-loss?), do definitely have answers insofar as it’s clear how to find such an answer by a finite brute-force search, but such a search is just extraordinarily intractable in its scale.
Yes, there’s one problem known as the “n-queens” problem. The most common being the 8 Queens Problem. It goes: in what configuration can you place 8 queens on an 8x8 chess board such that none may capture the other?
I’m fairly sure that we’re certain it can be done for any number of queens (greater than 3). The point is the “intractable” thing. I believe it’s been calculated that brute-forcing the 8 queens problem (let alone any number greater than 8) would take until well after the Earth becomes cosmic dust, and that’s on computers faster than any computer currently existing. (For n-queens there are algorithms that cut this time down considerably. I’m pretty sure there are solutions that will solve 8-queens in well under a couple seconds on my crappy laptop).
So some problems are solvable in theory, but unless a good method is found we’re stuck with “if we leave the computer running we can find out after we’re all dead”.
For instance, we found out that to have a unique solution the minimum number of Sudoku clues is 17. We did this by ruling out all cases where a puzzle has 16 clues, but even that would have taken forever so we had to devise a scheme to classify different 16-clue boards into “families” and test all the different families.
It still took about a year of computation time.
There’s an XKCD about it xkcd: Academia vs. Business
I’m also reminded of the amateur who did important work in the field of tesselation in her spare time Marjorie Rice - Wikipedia
It’s very simple to brute-force only 8 queens on an 8x8 chessboard; in fact, I recall a program for the Commodore 64 that could do it in about 10 minutes for a single solution.
You’re right. For some reason I recall 8 being unmanageable for brute-force. It’s 20 where it becomes hilariously impossible. (Still, O(n^2 C n) isn’t exactly a slouch, even for 8).
Edit: Though by brute force I mean “blind idiot brute force”, not “sort of brute force” where you restrict columns and then brute force that.
Does 0.999…=1? Nobody knows:confused: