How do people come up with difficult math Olympiad questions?

The problems that appear in difficult math competitions such as the IMO or the Putnam exam are usually very difficult and require some ingenuity to solve. They also usually don't look like they can be solved by simply knowing more advanced theory and the such.

How do people typically come up with these problems? Do they arise naturally from advanced mathematics (the somewhat infamous 'grasshopper problem' from the 2009 IMO comes to mind - to my not exactly knowledgeable mind this problem looks like it popped out of basically nowhere)? What is the perspective that mathematicians take when seemingly "inventing" these problems with no theoretical motivation to them whatsoever?

When I am working on my research, or on MO/math.SE questions, I often find myself thinking in a way which reminds me of the feel of solving Olympiad problems. If I then solve the problem, I try to find a very special case of my problem which is still challenging, and can be stated and solved using only material on the Olympiad curriculum. I then e-mail Kiran Kedlaya and say "Hey Kiran, do you think this would be a good Olympiad problem?" If he thinks so, he proposes it to the USAMO committe.

I wrote Problem 2 on the 2010 USAMO in this way; it is Theorem 3.2 of this paper specialized to the case that $W_0$ is the group $S_n$. The fact that the "total number of moves" referred to in the theorem is at most $\binom{n}{3}$ is computed in Section 5.2.

I think I send about one problem a year; but most of them get rejected.

UPDATE 2014 Problem B4 of the 2014 Putnam was mine. Let $F(x,y,z) = \sum F_{ijk} x^i y^j z^k$ be a homogenous polynomial of degree $n$ with positive real coefficients. We say that $F$ is hyperbolic with respect to the positive orthant if, for all $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2) \in \mathbb{R}_{> 0}^3$, the polynomial $f(t) = F(tu_1+u_2,tv_1+v_2,tw_1+w_2)$ has $n$ negative real roots.

In this paper, I show that there are constants $V_1$ and $V_2$ (dependent on $n$) so that,

(1) if $F$ is hyperbolic with respect to the positive orthant, then $F_{i(j+1)(k+1)} F_{(i+1)j(k+1)} > V_1 F_{i(j+1)(k+1)} F_{(i+2)jk}$ and the same for all permutations of the indices

(2) if $F_{i(j+1)(k+1)} F_{(i+1)j(k+1)} > V_2 F_{i(j+1)(k+1)} F_{(i+2)jk}$ and the same for all permutations of the indices, then $F$ is hyperbolic with respect to the positive orthant.

The proof is nonconstructive; I also (Theorem 20) give an explicit value of $V_1$. I was thinking about whether I could give a concrete value for $V_2$. The problem was too hard, so I thought instead about homogenous polynomials in two variables, which is the same as inhomogenous polynomials in one variable. At this point, I was basically looking for a converse to Newton's inequality: I wanted a constant $C$ so that, if $a_k^2 > C a_{k-1} a_{k+1}$, then all the roots of $\sum_{k=0}^n a_k z^k$ are real. The result in one variable wasn't worth publishing, but I figured I could make a nice problem by choosing a particular polynomial and asking people to prove the roots were real.

UPDATE 2020 Problem 6 of the 2020 USOMO was mine. It is the key computation from this MO answer, specialized to the case that the matrix $X$ has rank one, so $X_{ij} = x_i y_j$. The rank one case turned out not to be easier than the general case, which is why it doesn't show up in that MO thread, but it is one of the things I thought about when working on that answer, and I noticed at the time that it looked like a strengthening of the rearrangement inequality.

If you ask me, I suppose the problems don't get invented - rather, I think they arise as word-problem forms of well-known theorems/results etc.

That is to say, they are not made for the competitions as such - they existed before. For example, regarding the grasshopper problem, it may be that it was known that points could be chosen in any order without having to choose any point $p$ such that $p\in M$, and they just added the jumps and the grasshopper.

That's my 2 cents.