Non-constructive proofs for non-mathematicians

Question

I’m looking for simple, nonmathematical examples of non-constructive proofs. My imagination doesn’t seem up to the challenge.

Here’s one example based on the intermediate value theorem.

Suppose you’re handed two ends of a rope and you want to determine if the rope is cut anywhere. You can examine the entire length of rope to locate a cut if there is one, or you can do the following.

Have a friend locate a telescoping box (you can’t see inside it) into which she places the rope with one end sticking out of both sides. Pull on the two ends of the rope so that the box telescopes apart as you and your friend pull on opposite ends. If at some point you can pull no further, it represents a proof that the rope has no cuts. The case where the pulling seems to go on and on can either be handled as a probabilistic proof of a cut, or it can be made deterministic by guaranteeing a maximum length on the rope in question.

Any different ideas?

Answer 1

There is a nice little story in Chapter 7 of the 2015 book Computation, Proof, Machine by Gilles Dowek. It tells the story of an explorer traveling on the Orient Express from Paris trying to find "the last station the train calls at on French territory". Here is the explorer's reasoning:

Yet it is not hard to prove that there exists a station at which the Orient Express stops that is in France and is such that the next station is no longer in France. For either Utopia is in France, and then is the train's last stop there, or it is not, in which case Strasbourg is the train's last stop on French soil.

Shortly after, the author explains:

This reasoning, however, doesn't help the explorer, who does not just want to know whether there exists a station where the mystery woman awaits him, but also which one it is. What good is mathematics if it can't get him to his rendezvous?

Finally, the author explains the point of the story:

That night, on board the Orient Express, the explorer becomes aware of an idea that also hit the mathematicians of the early twentieth century: some proofs, such as the proof we have just outlined, demonstrate the existence of an object satisfying a certain property without specifying what that object is. These proofs must be distinguished from those that demonstrate the existence of an object satisfying a certain property and give an example of such an object.

Answer 2

An issue with turning this into a probablistic proof is that we need a prior distribution for the rope length (and there isn't a natural one to choose for all of $\mathbb{R}^+$).

But suppose the rope's length has probability density function proportional to $\frac{1}{n^2}$, or some other particular one. Then I think this would be a fine example. Since this is for non-mathematicians, maybe we can say something like this: it's only half as likely that the rope is a meter longer.

Here's another simple one based on a question from yesterday: Candy costs a dollar and soda costs a dollar. I sent Billy to the store with a dollar and he came home with candy and soda. Now he's in trouble because he shoplifted something.

Answer 3

Here's one that's still, technically, mathematical, but still very easy to grasp for a layman:

If there are 367* different people in a room, two of them must have the same birthday, for if everyone had different birthdays, then there would be at least 367 days in a year. This proof, of course, doesn't tell you who share the birthdays, or what their birthdays are. More or less anything that similarly uses the pigeon hole principle will be non-constructive.

*Chosen to avoid leap year cleverness.