[FOM] What is a "non-constructive proof"?

[Timothy Y. Chow]

Joe Shipman wrote:

> (1) A theorem that certain equations have finitely many solutions, with 
> no bound given that would allow one to exhaustively search for them
> (2) A theorem that a certain equation has a solution, with no bound 
> given, but a guarantee that searching will eventually find one
> (3) A counting argument that an object with certain properties of a 
> certain size must exist, which comes with an implicit exponential bound 
> on the search but no efficient construction.

For (1), I can't think of any examples offhand that I would consider to be 
at the undergraduate level.

For (2) and (3), I'm not sure if these exactly meet your desiderata, but 
you could consider:

A. A strategy-stealing argument for a game such as Hex proves that there 
is a first-player win, but yields no efficient algorithm for finding a 
winning move.

B. A primality test can prove that a composite number is not prime but 
without giving an efficient algorithm for finding a factor.

C. A probabilistic argument can show that Ramsey graphs exist (graphs on n 
vertices with neither a clique nor an independent set of size 2 log_2 n) 
without giving an efficient algorithm for constructing them.

See also this MathOverflow question:

https://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma

Tim