How do you prove a proof? Sometimes, you don’tLucidio Studio, Inc./Getty Images
A mathematician opens her office door to find a small fire. Without panicking, she looks around the room and spots a fire extinguisher. “Ah, a solution exists!” she says, before closing the door and continuing on with her day. Simply knowing it is possible to extinguish the fire is proof enough that the problem can be solved – why bother to actually go through the motions to do it? This old joke sums up how a lot of modern mathematics gets done, thanks to a sneaky tactic for problem-solving: the non-constructive proof.
It is a tricky idea to get your head around, so here’s a mostly non-mathematical example. Say there are 367 people in a room – what are the chances that two of them share a birthday? The answer is 100 per cent, because (assuming we account for leap years) there are only 366 possible birthdays, and each person must have a birthday, so at least two people must have the same birthday. This is an example of what mathematicians call the “pigeonhole principle” – the people are the pigeons, the holes are the birthdays – and it’s a classic way of approaching non-constructive proofs. We know that two people must share a birthday, even if we have no idea who out of the 367 people they are.
