Here's an open problem that is not hard to understand (high school math is sufficient), but whose solution would be one of the most important advances in mathematics in the last 100 years, easily:
Let H_n = 1 + 1/2 + 1/3 + ... + 1/n
So, H_1 = 1, H_2 = 1 + 1/2, and so on.
Let divsum(n) = the sum of the divisors of n
For example, divsum(10) = 1 + 2 + 5 + 10 = 18, and divsum(8) = 1 + 2 + 4 + 8 = 15.
Here's the problem:
Prove that for n > 1,
divsum(n) < H_n + exp(H_n)*log(H_n)
The questions are answered in the article. The equivalence is not supposed to be obvious even to other number theorists. Most of the article is devoted to explaining "why" it works since the actual proof is two paragraphs.
Don't know what you're talking about. The article is about unproved theorems. They are described as being simple or obvious, but there's nothing obvious about
Prove that for n > 1,
divsum(n) < H_n + exp(H_n)log(H_n)
See the entire field of number theory for something that didn't have applications when it was conceived. Gauss, Euler and the other early number theorists were essentially just amusing themselves with stuff like the phi function. Then cryptography became a serious open problem, and boom.
Interestingly enough this is most often the case with pure mathemetics: their proofs are pursued purely in the interest of understanding & attaining them - the implications & applications of which are sometimes unrealized for decades (a great example is Evariste Galois: his number theory and symmetry/group work was decades-later applied by physicists to define many of the laws physics appear to obey - check out the wiki).
Or a certain obscure piece of algebra discovered by one G. Boole.
(Edit: During his time, Boole's results were practically unknown except to other logicians, and certainly nobody expected to find any practical use for them. It wasn't until the 1930s when Claude Shannon realized that the algebra that now carries Boole's name could be used to analyze digital electric cirquits.)
A novel proof involves making novel connections, rigorously showing how different parts of mathematics can be made to work together in ways that haven't been thought of. When you look at it that way it's not hard to imagine the value in solving puzzles like this, even if it's impossible to know the specifics ahead of time (which are by nature unknown).
For the first problem, he goes to the trouble of defining "graph" and "tree", as though his audience has no math background, but doesn't bother defining "labeled". For those wondering WTF an "unlabeled tree" is: http://mathworld.wolfram.com/LabeledGraph.html
I'm reminded of two other "embarrassing" open problems.
A perfect number is a number whose divisors sum to return the original number. Thus, 6 is a perfect number since 1 + 2 + 3 = 6. 28 is also a perfect number since 1 + 2 + 4 + 7 + 14 = 28. But 8 is not a perfect number since 1 + 2 + 4 = 7.
1. Are there an infinite number of perfect numbers?
A slight nitpick. Your definition should be a number whose proper divisors sum to the original number. Or it should be whose divisors sum to twice the original number.
A slight typo in the author's bit (which is fascinating), the Collatz sequence doesn't terminate in a series of 1's. By its definition, once 1 is reached, the series repeats {1,4,2,1,4....}. Thus, the number of steps required to reach 1 is called the "stopping time" of the sequence. See the Wikipedia article on the Collatz conjecture for some great visualizations of low seed value termination trajectories for the Collatz sequence:
If we consider labelled trees then this question has any easy solution: there are labelled trees on n vertices. Counting the total number of graphs on n vertices is even easier. However, no closed form solution is known for unlabelled trees and this problem has been open for well over a century.
Hmm, any node can be a root node which is tricky, but not show stopper. A root node can have 1 to N-1 branches not so bad. You can order them by some sort of weight with each leaf being (depth * 2N)^N so they are strictly ordered, still looking good. But, how do you count mirror images. AKA a simple star with a center point and N edges just counts as 1.
Here's the problem:
It turns out that this is equivalent to the Riemann hypothesis. Their equivalence is shown here: http://arxiv.org/pdf/math/0008177v2