Let f(n) = 3n+1 if n is odd and n/2 if n is even. Let f(1) = 1. Assume we start with some number n and repeatedly take the f of the current number. Prove that no matter what the initial number is we eventually reach 1.
It can be also obtained from Wikipedia. This problem is worth at least $500 US dollars. Refer to this page for some results of computational verification. I also wrote a very simple program to verify this conjecture.
This is an an open problem for the moment, and it seems to be given on an graduate school entrance exam. To find a function g (n) such that f(n) = O(g(n)) is then an open problem, too.
It's very interesting. By the way, I found "Jones' conjecture", posted by Chuan-Min Lee. I hope that someday I will post an interesting and important open problem or a conjecture, too.