On Nonconstructive Proofs that there is a Solution

How finding explicit strategies can mean biting off more than you can chew.

This is based on my answer to “Once I read a description to a numerical methods course and it says ‘often in math, it is possible to prove the existence of a solution to a problem but it isn’t possible to ‘find it’. What does that mean? Can anyone give me a good example of this?” from 2024, but it has been edited and expanded.

---

There’s an old joke:

An engineer, a physicist, and a mathematician are staying in a hotel. During the night, there is a small fire in each of their rooms.

The engineer wakes up, sees the fire, pours water into a bucket, and dump it over the fire, putting it out. Satisfied, he goes back to bed.

The physicist wakes up, sees the fire, and rushes over to his desk. After quickly going through a few pages of calculations, he pour a precise amount of water into a glass and uses it to extinguish the fire. Satisfied, he goes back to bed.

The mathematician wakes up, sees the fire, and rushes over to his desk. After quickly going through a few pages of calculations, he exclaims “There is a solution!” Satisfied, he goes back to bed.

Mathematics allows for a possibility that you seldom see in other subjects: it can be possible to prove definitively that a problem does have a solution, without ever producing any hints about what that solution is. Indeed, finding this solution might be a much, much harder task.

Deciphering Black Magic in Mathematics

In my post above, I talked about Zagier’s proof of Fermat’s sum of two squares theorem, which proves that for any prime p=1+4n, you can find integers x,y such that x²+y²=p. However, the proof tells you nothing about what x and y are. Thus, we’ve shown that a solution exists, but we know nothing about what it is.

But there are other (more involved) proofs of the same theorem that do provide efficient algorithms for computing x and y. My goal here is to give an easy-to-understand example where there is a reasonably simple proof that a solution exists, but it is unknown what this solution might be in general.

So, without further ado, let’s talk about the game Chomp.

You have a rectangular chocolate bar made up of smaller squares. The top left corner is poisoned. Two players take turns biting off pieces of the chocolate bar; whoever eats the top left corner loses (due to being dead).

The rules for biting off a piece are as follows: you choose a square of the bar and then you bite it off and everything to the right and below it. The following is a perfectly good move.

This could be followed up by a bite like the one below.

Who wins?

There are only finitely many possible moves. There is no possible way to tie. There is no randomness involved. Therefore, there must exist a winning strategy for either the first player or the second player—it cannot be otherwise, as a consequence of Zermelo’s theorem. (If you are unfamiliar with Zermelo’s theorem, don’t worry: I’ll give a proof of it at the end. It’s fairly straightforward.)

In fact, we can say that—if they are playing perfectly—the first player should always win Chomp.

Why? Well, suppose that it is the second player who has a winning strategy. Then that means that if the first player eats the bottom right corner as their first move, the second player can choose a different square and force victory. But if that’s the case, the first player could have just chosen that new square as their first move and used the second player’s winning strategy to win!

(Why is that? The allowable moves on the rectangular board and the allowable moves on the rectangular board minus the bottom corner are exactly the same, other than that on the latter, the first player cannot choose the bottom right corner as their first move. But we’ve already established that is a losing move anyway.)

Note what is weird here: we’ve proved that there is a winning strategy, and we have even proved that it is the first player who must have this winning strategy, but we have not determined what this winning strategy is!

And, in fact, it is a deeply non-trivial problem. It is known how to win at Chomp if you have a square chocolate bar or a few other special cases, or if the chocolate bar is not too big (you can just do a brute-force computer search). But the number of possible intermediate positions on an m×n chocolate board is

\(\frac{(m+n)!}{m!n!}, \)

which grows very rapidly. A 19×75 board would admit ≈10²⁰ different positions, so it would take thousands of years to analyze via brute force.

If you mistakenly think that winning at Chomp should be easy, I invite you to try to play against a computer. Even though you get to move first (and therefore should win if you are playing perfectly!), you’ll probably find that it will take you many tries.

---

Now, I promised to give a proof of Zermelo’s theorem, so let’s do that.

The setup is this: we have a game with two players that take alternating moves. There should only be finitely many moves possible; there shouldn’t be any hidden information (both players know everything about the state of the game); the game should be zero-sum (when the game ends, at most one player wins, although draws are possible); and there shouldn’t be any randomness involved.

Chomp fits these criteria: the board gets smaller after every move, and so it is clear that, eventually, the only remaining move is to eat the poisoned square. This proves that the game is finite. (And also that the game never ends in a draw.)

Chess also fits these criteria, and it was actually the original game that Zermelo considered. Thanks to the fifty-move rule, games of chess cannot go on forever, so they are finite. Similarly to Chomp, there is no hidden information and no chance.

Tic-tac-toe is also such a game, as is checkers, Nim, and many others.

For such a game, Zermelo’s theorem states the following: either the first player can force a win, or the second player can force a win, or neither player can force a win and the game ends in a draw.

The proof is by induction, working backward from the end of the game. Let’s say that we have two players who play such a game—Holmes and Moriarty. We’ll assume that they engage in perfect play: they analyze all of the possible moves and always choose the best one. (What “best” means here will become clear shortly.)

Now, let’s say that the game has ended in a loss for Moriarty and a win for Holmes. For the last move that Moriarty made, could there have been another move such that if Moriarty had taken it, Holmes would not eventually be able to force a win? No, of course not: if there were such a move, Moriarty would have taken it. Remember, he has the ability to see all of the possible moves.

So, let’s go back one more turn, to Holmes’ move. What we see is that Holmes chose a move that forced Moriarty into a position where he would lose—thus, once the game reached this state, Holmes had a winning strategy going forward.

Okay, now let’s rewind a step further, to Moriarty’s go. Moriarty knows that once he makes this move, Holmes has a winning strategy—he will be able to force a win. So, was there some other move that he could make to avoid this? Of course not: if there had been, he would have taken it. Since we know that he didn’t, it must mean that for any other move, Holmes would still have a winning strategy.

Naturally, that means that on Holmes’ previous turn, he already had a winning strategy. Which means that Moriarty must have been forced to make a move for which Holmes had a winning strategy, which means that Holmes already had a winning strategy, and so on and so forth. We conclude that from the very first turn, Holmes had a winning strategy. It didn’t matter what Moriarty did—Holmes would eventually find a way to win.

The same reasoning applies if we suppose that Holmes lost and Moriarty won—Moriarty must have had a winning strategy. The only other option is that the game ends in a draw, for which we replace “winning strategy” with “not losing strategy,” but otherwise the argument is essentially the same.

It’s a slightly odd proof to read through, because it doesn’t entirely feel consistent with lived experience—chess games certainly don’t seem predetermined. But that is only because the number of possible moves in chess is so absurdly massive (there are an estimated 10¹²⁰ possible games of chess) that doing what Holmes and Moriarty do in the proof (going through all possible moves) is utterly infeasible. If we could do it, chess would be just as inevitable as tic-tac-toe.