# Which famous mathematical puzzles have not been solved yet?
**URL:** https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152
**Category:** Factual Questions
**Created:** [September 6, 2013, 5:39am UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152 "2013-09-06T05:39:35Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@davidmich](https://boards.straightdope.com/u/davidmich)
#### Post date: [September 6, 2013, 5:39am UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/1 "2013-09-06T05:39:35Z")
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
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [September 6, 2013, 5:47am UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/2 "2013-09-06T05:47:38Z")
[Wikipedia’s “List of unsolved problems in mathematics”](https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics)
---
### Author:  [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)
#### Post date: [September 6, 2013, 6:36am UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/3 "2013-09-06T06:36:22Z")
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.
---
### Author:  [@davidmich](https://boards.straightdope.com/u/davidmich)
#### Post date: [September 6, 2013, 8:20am UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/4 "2013-09-06T08:20:01Z")
Thanks Indistinguishable. I wasn’t aware of a wikipedia site that kept tabs on math problems. Very helpful. Thank you.
davidmich
---
### Author:  [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)
#### Post date: [September 6, 2013, 3:07pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/5 "2013-09-06T15:07:27Z")
Ian Stewart’s [Visions of Infinity: The Great Mathematical Problems](http://www.amazon.com/Visions-Infinity-Great-Mathematical-Problems/dp/0465022405/ref=sr_1_1?s=books&ie=UTF8&qid=1378479740&sr=1-1) 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.
---
### Author:  [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)
#### Post date: [September 6, 2013, 4:08pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/6 "2013-09-06T16:08:46Z")
> [@Wendell\_Wagner](#):
>
> 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.
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.
---
### Author:  [@Jragon](https://boards.straightdope.com/u/Jragon)
#### Post date: [September 6, 2013, 4:14pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/7 "2013-09-06T16:14:24Z")
> [@Wendell\_Wagner](#):
>
> 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.
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.
---
### Author:  [@Chefguy](https://boards.straightdope.com/u/Chefguy)
#### Post date: [September 6, 2013, 4:15pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/8 "2013-09-06T16:15:41Z")
An ancillary question: How do we know that these problems actually have answers?
---
### Author:  [@Leo\_Bloom](https://boards.straightdope.com/u/Leo_Bloom)
#### Post date: [September 6, 2013, 4:19pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/9 "2013-09-06T16:19:40Z")
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.
---
### Author:  [@Jragon](https://boards.straightdope.com/u/Jragon)
#### Post date: [September 6, 2013, 4:28pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/10 "2013-09-06T16:28:02Z")
> [@Chefguy](#):
>
> An ancillary question: How do we know that these problems actually have answers?
A lot of them fairly obviously have answers, simply by the way they’re worded. For others, “\ 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.
---
### Author:  [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)
#### Post date: [September 6, 2013, 4:33pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/11 "2013-09-06T16:33:04Z")
> [@Chefguy](#):
>
> An ancillary question: How do we know that these problems actually have answers?
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](http://en.wikipedia.org/wiki/G%C3%B6del%27s_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.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [September 6, 2013, 4:38pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/12 "2013-09-06T16:38:47Z")
> [@Jragon](#):
>
> 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).
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…
---
### Author:  [@MikeS](https://boards.straightdope.com/u/MikeS)
#### Post date: [September 6, 2013, 4:42pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/13 "2013-09-06T16:42:06Z")
> [@Leo\_Bloom](#):
>
> 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.
Leopold Bloom should have read up on [constructible numbers](http://en.wikipedia.org/wiki/Constructible_number) and the Lindemann-Weierstrass theorem. His other proposed methods of enrichment were all much more plausible.
---
### Author:  [@Jragon](https://boards.straightdope.com/u/Jragon)
#### Post date: [September 6, 2013, 4:42pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/14 "2013-09-06T16:42:52Z")
> [@Indistinguishable](#):
>
> 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]).
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.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [September 6, 2013, 4:45pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/15 "2013-09-06T16:45:24Z")
> [@Chefguy](#):
>
> An ancillary question: How do we know that these problems actually have answers?
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.
---
### Author:  [@Jragon](https://boards.straightdope.com/u/Jragon)
#### Post date: [September 6, 2013, 4:55pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/16 "2013-09-06T16:55:22Z")
> [@Indistinguishable](#):
>
> Some open problems of a very 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.
---
### Author:  [@Andy\_L](https://boards.straightdope.com/u/Andy_L)
#### Post date: [September 6, 2013, 4:57pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/17 "2013-09-06T16:57:48Z")
> [@Jragon](#):
>
> 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.
There’s an XKCD about it [xkcd: Academia vs. Business](http://xkcd.com/664/)
I’m also reminded of the amateur who did important work in the field of tesselation in her spare time [Marjorie Rice - Wikipedia](http://en.wikipedia.org/wiki/Marjorie_Rice)
---
### Author:  [@ricksummon](https://boards.straightdope.com/u/ricksummon)
#### Post date: [September 6, 2013, 5:26pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/18 "2013-09-06T17:26:22Z")
> [@Jragon](#):
>
> 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.
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.
---
### Author:  [@Jragon](https://boards.straightdope.com/u/Jragon)
#### Post date: [September 6, 2013, 5:28pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/19 "2013-09-06T17:28:08Z")
> [@ricksummon](#):
>
> 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.
---
### Author:  [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)
#### Post date: [September 6, 2013, 6:27pm UTC](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152/20 "2013-09-06T18:27:23Z")
Does 0.999…=1? Nobody knows:confused:
[Next page](https://boards.straightdope.com/t/which-famous-mathematical-puzzles-have-not-been-solved-yet/668152.md?page=2)