How to prove existence of solutions without constructing one? For some problems, it is difficult to get an explicit solution. But it is very good if we can prove there do exist some solutions though we can't find them. Is it possible to prove existence of solutions without constructing one? Can you show some examples? Many thanks.

Edit: Thanks everyone. Of course, it is the best if we can find one or all solutions to a problem. But it is not always easy. Then a non-constructive proof may also be very meaningful. Here is an example. In 1991, it was proved that a multiple layer perceptron neural network is a universal function approximator. But the proof is not constructive. However, it is of great importance for at least control community as people can try to use neural network to approximate any nonlinear systems without worrying about the theoretical foundation. What I am interested is whether there are any general methods for non-constructive existence proof.
 A: A very common technique is by counting and comparing cardinalities. For example, one can prove that transcendental numbers must exist by noting that there is a countable number of algebraic numbers (since there is a countable number of polynomials), but the reals are uncountable by Cantor's argument. This shows that most numbers are transcendental without producing a single one of them.
A: The Intermediate Value Theorem is a nice tool to prove that solutions to many type of equations exists, without being able to solve them.
It is used for example to show that any polynomial of odd degree with real coefficients has a real solution (which is a critical step in the proof of Fundamental Theorem of Algebra), or to prove that equations of the type:
$$x=\cos(x)$$
have solutions.
A: Proofs by contradiction often work in these cases. For instance, if you were to assume that $\sin(3x)$=$x^3-\pi$ has no solutions, then $\sin(3x)-x^3+\pi$ is never zero. Thus, the reciprocal of this function is defined for all real numbers, which you may then be able to prove is impossible giving you a contradiction.
The intermediate value theorem also helps when dealing with continuous functions.  For the example above, it is enough to find $x_1$ and $x_2$ such that $\sin(3x_1)-x_1^3+\pi>0$ and $\sin(3x_2)-x_2^3+\pi<0$. (Take $x_1$ and $x_2$ to be 0 and 2 respectively for example).  This implies that there is a solution to the original equation lying between 0 and 2.
A: The http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem states that there exists arbitrarily long arithmetic progressions in the primes, but does not provide a method to construct them.
A: The probabilistic method can sometimes be used to prove the existence of a structure with certain properties. You put a probability measure on the set of all structures, that is, define "random structure" in a meaningful way. Then if your properties hold with non-zero probability, you have existence! 
The Wikipedia link above gives two concrete examples from combinatorics.  
A: I believe that the contradiction is the only possible method to prove an existence without constructing a method to find the solution. That's why proofs by contradiction are called "non-constructive".
On the other hand, it's not always good to know the existence of a solution without knowing how to obtain it. A nice example is the following theorem: if $x_n\leq x_{n+1}$ and $x_{n}\leq a$ for all $x\geq 0$ then $\exists\lim\limits_{n\to\infty}x_n = x\leq a$. It's a nice theorem but if you would like to calculate bounds on $x-x_n$ it tells nothing to you how to do it.
A: Here is a typical example of a non-constructive existence proof:
We want to prove that there exists a rational number $x^y$ such that both $x$ and $y$ are irrational. A way to do this is first to let $x=y=\sqrt 2$ (because we know that $\sqrt 2$ is irrational). If $\sqrt 2 ^{\sqrt 2}$ is rational, we have have a rational number on the desired form. On the other hand, if $\sqrt 2 ^{\sqrt 2}$ is irrational, let $x=\sqrt 2 ^{\sqrt 2}$ and $y=\sqrt 2$. Then $x^y=(\sqrt 2 ^{\sqrt 2})^{\sqrt 2} = \sqrt 2^2 = 2$, which is obviously rational. 
We have proven that there exists a rational number $x^y$ such that both $x$ and $y$ are irrational. Either with $x=y=\sqrt 2$ or $x=\sqrt 2 ^{\sqrt 2}, y= \sqrt 2$, but we don't know which.
Edit:
Trying to generalize this idea. Suppose you want to prove a proposition. Find a set of cases such that only one of the cases has to be true for the proposition to be true. A constructive proof would be to find a specific case that is true. For a non-constructive proof, it is enough show that it is not possible that all the cases are false. 
A: The game of Hex gives a good example.  First one can prove it cannot draw, so it must be either a first or second player win.  Assume it is a second player win.  Let the first player make a random move, then follow the second player strategy.  If the strategy requires a move where the random move is, take another random move.  As an extra move can only be an asset, the first player can win, contradicting our second player win assumption.  This gives no information on what the strategy is.
A: The Implicit Function Theorem is another example of such a technique.  There are plenty of examples of the Implicit Function Theorem in action, although some of the concrete examples seem a bit artificial.
