5 ms·

What are some other problems that appear deceptively simple, but are extremely difficult to solve?

yen223 9y ago
Fermat's last theorem is probably the most obvious one.
guruparan18 9y ago
From the past, we had Fermat's Last Theorem. Looking for ones that are not solved yet? How about "Collatz conjecture "? I think there are more complex ones, but yeah, not so simple to explain.
- ouid 9y ago
  from everything I've read, collatz has not merely resisted proof, but anything resembling progress. Erdos said that mathematics is not yet ready for such problems.
  - guruparan18 9y ago
    True. And there could be many more ridiculously simple problems with hard or no applications (at least for now) we may not be able to solve or progress at all. Math as we know and practice might still fall short. I, for one, be happy that simple to state but solved, Godel's Incompleteness theorem, about the imperfection of the tools, had set the things firmly on stone. Solving them or progress? May be I don't care, but these little problem, simple ones does encourage one to start thinking about solving problems, they make math accessible to masses.
  - zzazzdsa 9y ago
    Conway showed that the generalized Collatz conjecture (recurrences with arbitrary cases dependent on the modulus) is computationally undecidable (halting problem reduces to it). The choice of modulus doesn't even need to be that big to get this result, only ~6500 or so. As far as I know, this is the only substantial result in either direction for this problem.
  - deckar01 9y ago
    I suspect it is due to the lack of application for the solution. I analyzed the problem for a while and theorized ways to collaboratively contribute to the solution. I settled on submitting an integer sequence to OEIS. http://oeis.org/A261393 http://oeis.org/A261393
deleted 9y ago
[deleted]
chx 9y ago
Is there a number which can be written in base 2,3,4,5,6 using only 0 and 1? What's mind blowing here is that if you ask for base 2, 3, 4 the answers are trivial but for bases 2,3,4,5 somehow you get 82000 and we do not know whether there is another and for 6 it's unknown.
- mejin 9y ago
  Am I missing something? the number 1 is 1 in all of those bases and therefore can be written using 0 (0 times) and 1 (1 time).
  - klodolph 9y ago
    Sometimes mathematicians forget to say "non-trivial", that's what you're missing.
  - adenadel 9y ago
    Often in mathematics, we look for the nontrivial solutions to questions like this.
neilparikh 9y ago
Another one is Goldbach's Conjecture, which has been verified upto 4E18, but is still unproved.
tzs 9y ago
Let n be a positive integer. Let s(n) be the sum of all positive divisors of n. E.g., s(2) = 1 + 2, s(4) = 1 + 2 + 4, s(20) = 1 + 2 + 4 + 5 + 10 + 20. Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. Question: is it true that s(n) < H(n) + log(H(n)) exp(H(n)) for all n > 1? (log is natural logarithm) It turns out that this simple looking problem is equivalent to the Riemann Hypothesis, which is perhaps the most important unsolved problem in pure mathematics. Many of the best minds in mathematics have attempted it in the approximately 160 years since Riemann posed it. What equivalent means in this context is that if the Riemann Hypothesis is true, than the inequality above is also true, and if the inequality above is true, then the Riemann hypothesis is true.
- bmc7505 9y ago
  Maybe just me, but that problem does not look very simple at all. One reason OP's problem is appealing, is because the solution can be easily checked. The solution is a kind of "proof of work". You could never guess the solution without a deep understanding of the problem. But once found, the solution is immediately verifiable. For many problems one can easily guess the solution, without necessarily knowing the proof (like Fermat did). The answer is almost certainly negative, and a complete solution requires a very long and tedious proof that cannot be checked without a deep understanding of the field and many years of collective effort. I am specifically interested in problems which can be understood by a child, have hard solutions which cannot be easily guessed, but are easily verified (ex. factoring the product of two large primes). It seems like these problems would make good candidates for one-way-functions, like the diophantine equations and ECC. But elliptic curve cryptology is too difficult to describe to a child.
  - AstralStorm 9y ago
    Quite easy to explain given a few graphs. The explanation boils down on how hard is to accurately draw a curve of such an elliptic function at big x (P3) and then figure out which two other points intersect with a given line near. You can even show it on a big whiteboard. You can even show how easy out would be for a simple curve where the left part is an easy equation. The hard part is what makes an equation easy to solve. (And how some elliptic are broken.) It takes at least some high school math to hint at this.
DonbunEf7 9y ago
Can you find (possibly negative) integers x, y, and z, such that x ^ 3 + y ^ 3 + z ^ 3 == 33? If so, it's publication-worthy.
- skypather 9y ago
  what if I can prove there is no integer solution for it? Is it still publication-worthy?
  - chx 9y ago
    Even more so!
- bmc7505 9y ago
  Is the constant 33 important (ie. would it be any less significant if it were 42, or 74 instead) and if so, why?
  - lifthrasiir 9y ago
    I was replying that the constants in question include 33, 42 and 74... and realized that I'm late :-) In a more recent survey, though, it is now known that: > 74 = −284650292555885^3 + 66229832190556^3 + 283450105697727^3 [1] [2]. [1] https://arxiv.org/pdf/1604.07746v1.pdf https://arxiv.org/pdf/1604.07746v1.pdf [2] https://mathoverflow.net/a/223121 https://mathoverflow.net/a/223121
mrkgnao 9y ago
In general, number theory is notorious for containing many questions that are accessible to a layperson but whose proofs rely on arguments that are so difficult that even the basic idea of how the argument works takes many years of study. Fermat's last theorem is an example, because it can be shown to be equivalent to, among other things, a very deep statement about elliptic curves (yep, the same thing The Fine Answer is about!) that Andrew Wiles proved. https://en.wikipedia.org/wiki/Modularity_theorem https://en.wikipedia.org/wiki/Modularity_theorem
OscarCunningham 9y ago
Does n^pi = m have any nontrivial integer solutions? Does the fractional part of e^n tend to zero?
thearn4 9y ago
I would say the collatz conjecture is up there. It's been an entry point for many people into the computational side of mathematics. Take any positive whole number, n. If it is even, divide it by 2. (n = 2n) If it odd, multiply it by 3 and add one. (n = 3n + 1) Repeat. If n = 1, stop. Does this process always lead to 1? It seems to, but who knows. https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture
rogual 9y ago
On an infinite square grid where lines are 1 unit apart, if a circle of radius "r" is centered on an intersection, how many intersections lie within the circle? Answer in terms of "r".
tikhonj 9y ago
My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".) Here's one that's genuinely easy: x^3 + y^3 + z^3 = 29 The solution is x = 1, y = 1, z = 3 (or any permutation thereof). So how about this one? x^3 + y^3 + z^3 = 30 Play around a bit. Not so easy. But it does have a solution! Here it is: x = -283059965 y = -2218888517 z = 2220422932 And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem! This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.

Fermat's last theorem is probably the most obvious one.

From the past, we had Fermat's Last Theorem. Looking for ones that are not solved yet? How about "Collatz conjecture "? I think there are more complex ones, but yeah, not so simple to explain.

ouid 9y ago
from everything I've read, collatz has not merely resisted proof, but anything resembling progress. Erdos said that mathematics is not yet ready for such problems.
- guruparan18 9y ago
  True. And there could be many more ridiculously simple problems with hard or no applications (at least for now) we may not be able to solve or progress at all. Math as we know and practice might still fall short. I, for one, be happy that simple to state but solved, Godel's Incompleteness theorem, about the imperfection of the tools, had set the things firmly on stone. Solving them or progress? May be I don't care, but these little problem, simple ones does encourage one to start thinking about solving problems, they make math accessible to masses.
- zzazzdsa 9y ago
  Conway showed that the generalized Collatz conjecture (recurrences with arbitrary cases dependent on the modulus) is computationally undecidable (halting problem reduces to it). The choice of modulus doesn't even need to be that big to get this result, only ~6500 or so. As far as I know, this is the only substantial result in either direction for this problem.
- deckar01 9y ago
  I suspect it is due to the lack of application for the solution. I analyzed the problem for a while and theorized ways to collaboratively contribute to the solution. I settled on submitting an integer sequence to OEIS. http://oeis.org/A261393 http://oeis.org/A261393

deleted 9y ago

[deleted]

chx 9y ago

Is there a number which can be written in base 2,3,4,5,6 using only 0 and 1? What's mind blowing here is that if you ask for base 2, 3, 4 the answers are trivial but for bases 2,3,4,5 somehow you get 82000 and we do not know whether there is another and for 6 it's unknown.

mejin 9y ago
Am I missing something? the number 1 is 1 in all of those bases and therefore can be written using 0 (0 times) and 1 (1 time).
- klodolph 9y ago
  Sometimes mathematicians forget to say "non-trivial", that's what you're missing.
- adenadel 9y ago
  Often in mathematics, we look for the nontrivial solutions to questions like this.

neilparikh 9y ago

Another one is Goldbach's Conjecture, which has been verified upto 4E18, but is still unproved.

tzs 9y ago

Let n be a positive integer. Let s(n) be the sum of all positive divisors of n. E.g., s(2) = 1 + 2, s(4) = 1 + 2 + 4, s(20) = 1 + 2 + 4 + 5 + 10 + 20. Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. Question: is it true that s(n) < H(n) + log(H(n)) exp(H(n)) for all n > 1? (log is natural logarithm) It turns out that this simple looking problem is equivalent to the Riemann Hypothesis, which is perhaps the most important unsolved problem in pure mathematics. Many of the best minds in mathematics have attempted it in the approximately 160 years since Riemann posed it. What equivalent means in this context is that if the Riemann Hypothesis is true, than the inequality above is also true, and if the inequality above is true, then the Riemann hypothesis is true.

bmc7505 9y ago
Maybe just me, but that problem does not look very simple at all. One reason OP's problem is appealing, is because the solution can be easily checked. The solution is a kind of "proof of work". You could never guess the solution without a deep understanding of the problem. But once found, the solution is immediately verifiable. For many problems one can easily guess the solution, without necessarily knowing the proof (like Fermat did). The answer is almost certainly negative, and a complete solution requires a very long and tedious proof that cannot be checked without a deep understanding of the field and many years of collective effort. I am specifically interested in problems which can be understood by a child, have hard solutions which cannot be easily guessed, but are easily verified (ex. factoring the product of two large primes). It seems like these problems would make good candidates for one-way-functions, like the diophantine equations and ECC. But elliptic curve cryptology is too difficult to describe to a child.
- AstralStorm 9y ago
  Quite easy to explain given a few graphs. The explanation boils down on how hard is to accurately draw a curve of such an elliptic function at big x (P3) and then figure out which two other points intersect with a given line near. You can even show it on a big whiteboard. You can even show how easy out would be for a simple curve where the left part is an easy equation. The hard part is what makes an equation easy to solve. (And how some elliptic are broken.) It takes at least some high school math to hint at this.

DonbunEf7 9y ago

Can you find (possibly negative) integers x, y, and z, such that x ^ 3 + y ^ 3 + z ^ 3 == 33? If so, it's publication-worthy.

skypather 9y ago
what if I can prove there is no integer solution for it? Is it still publication-worthy?
- chx 9y ago
  Even more so!
bmc7505 9y ago
Is the constant 33 important (ie. would it be any less significant if it were 42, or 74 instead) and if so, why?
- lifthrasiir 9y ago
  I was replying that the constants in question include 33, 42 and 74... and realized that I'm late :-) In a more recent survey, though, it is now known that: > 74 = −284650292555885^3 + 66229832190556^3 + 283450105697727^3 [1] [2]. [1] https://arxiv.org/pdf/1604.07746v1.pdf https://arxiv.org/pdf/1604.07746v1.pdf [2] https://mathoverflow.net/a/223121 https://mathoverflow.net/a/223121

mrkgnao 9y ago

In general, number theory is notorious for containing many questions that are accessible to a layperson but whose proofs rely on arguments that are so difficult that even the basic idea of how the argument works takes many years of study. Fermat's last theorem is an example, because it can be shown to be equivalent to, among other things, a very deep statement about elliptic curves (yep, the same thing The Fine Answer is about!) that Andrew Wiles proved. https://en.wikipedia.org/wiki/Modularity_theorem https://en.wikipedia.org/wiki/Modularity_theorem

OscarCunningham 9y ago

Does n^pi = m have any nontrivial integer solutions? Does the fractional part of e^n tend to zero?

thearn4 9y ago

I would say the collatz conjecture is up there. It's been an entry point for many people into the computational side of mathematics. Take any positive whole number, n. If it is even, divide it by 2. (n = 2n) If it odd, multiply it by 3 and add one. (n = 3n + 1) Repeat. If n = 1, stop. Does this process always lead to 1? It seems to, but who knows. https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture

rogual 9y ago

On an infinite square grid where lines are 1 unit apart, if a circle of radius "r" is centered on an intersection, how many intersections lie within the circle? Answer in terms of "r".

tikhonj 9y ago

My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".) Here's one that's genuinely easy: x^3 + y^3 + z^3 = 29 The solution is x = 1, y = 1, z = 3 (or any permutation thereof). So how about this one? x^3 + y^3 + z^3 = 30 Play around a bit. Not so easy. But it does have a solution! Here it is: x = -283059965 y = -2218888517 z = 2220422932 And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem! This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.