I'm looking for a list of problems such that
a) any undergraduate student who took multivariable calculus and linear algebra can understand the statements, (Edit: the definition of understanding here is that they can verify a few small cases by themselves )
b) but are still open or very hard (say took at least 5 years to solve),
Edit: c) and first proposed in the 20th century or later.
Edit : my motivation is to encourage students to addict to solving mathematical problems.
I know that there are many such problems in number theory and combinatorics, for trivial example, Fermat's last theorem. I'll be more interested in other fields, but less famous problems in number theory or combinatorics would be also welcome. For example,
1) The $n!$ conjecture can be stated in an elementary language, but had been notoriously hard. See section 2.2 in Haiman's paper http://arxiv.org/abs/math.AG/0010246 .
2) Let $r$ be any positive integer, and let $x_1, x_2$ be indeterminates. Consider the sequence $\{x_n\}$ defined by the recursive relation $$x_{n+1} =(x_n^r +1)/x_{n-1}$$
for any integer n. Prove that $x_n$ is of the form $P/Q$, where $P$ is a polynomial of $x_1$ and $x_2$ with non-negative coefficients, and Q is a monomial. This problem appeared as a special case of a conjecture by Fomin and Zelevinsky in the context of cluster algebras around 2001. They proved that $x_n$ can be written as $\frac{(\text{polynomial})}{(\text{monomial})}$. Proofs of positivity are recently obtained by Nakajima ( http://arxiv.org/abs/0905.0002 ) and Qin ( http://arxiv.org/abs/1004.4171 ).
3) Nagata conjecture : Let $r$ be a positive integer $\geq 10$, but not a square. Consider $r$ random points on the plane $R^2$. Let $m$ be any positive number. Prove that the degrees of plane curves passing through each of the $r$ points at least $m$ times are greater than $m\sqrt{r}$. See "Masayoshi Nagata, On the 14-th problem of Hilbert. Amer. J. Math. 81 (1959) 766–772". This is still wide open.
I'll be grateful for any more examples.
Best Answer
This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of $2$ and powers of $3$. (Or so I think I've been told, I'm afraid I'm going on memory here.)
Let's let $\|n\|$ denote the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. For instance, $\|11\|=8$, because $11=(1+1)(1+1+1+1+1)+1$, and there's no shorter way. This is sequence A005245.
Then we can ask: For $n>0$, is $\|2^n\|=2n$? Since it is known that for $m>0$, $\|3^m\|=3m$, we can ask more generally: For n, m not both zero, is $\|2^n 3^m\|=2n+3m$? Attempting to throw in powers of 5 will not work; $\|5\|=5$, but $\|5^6\|=29<30$. (Possibly it could hold that $\|a^n\|=n\|a\|$ for some yet higher choices of a, but I don't see any reason that those should be any easier, though I suppose they might lack the same lower bound on hardness.)
Jānis Iraids has checked by computer that this is true for $2^n 3^m\le 10^{12}$ (in particular, for $2^n$ with $n\le39$), and Joshua Zelinsky and I have shown that so long as $n\le 21$, it is true for all $m$. (Fixed powers of $2$ and arbitrary powers of $3$ are much easier than arbitrary powers of $2$!) In fact, using an algorithmic version of the method in the linked preprint, I have computed that so long as $n\le 41$, it is true for all $m$, though I'm afraid it will be some time before I get to writing that up...
I don't think anything better than that is currently known.