If your solution doesn't work, make it work

post by Ege Erdil (ege-erdil) · 2022-03-11T16:10:51.479Z · LW · GW · 7 comments

Contents

7 comments

Consider the following problem:

There are an unspecified but finite number of chips on a table. Each chip is one of three colors: white, black or red. Define a "move" to be the act of replacing two chips of different colors with one chip of the third color. Prove that if after some sequence of moves we end up with a single chip on the table, the color of this chip can't depend on the exact sequence of moves that we made. In other words, if there are two distinct sequences of moves we could make such that in both cases we end up with a single chip left on the table, these chips must be of the same color.

So this is a game in which we have a state that can be represented by an ordered triplet of natural numbers $(x_1,x_2,x_3)\in N^3$ where each coordinate corresponds to the number of the chips of each of the three colors currently on the table. We're allowed to make any one of the following three moves:

$$(x_1+1,x_2+1,x_3)\to (x_1,x_2,x_3+1)(x_1+1,x_2,x_3+1)\to (x_1,x_2+1,x_3)(x_1,x_2+1,x_3+1)\to (x_1+1,x_2,x_3)$$

For the moment, let's assume that the claim we're being asked to prove is indeed correct. The first question we can ask is whether it's even always possible to end up with only one chip, and here the answer is obviously no: if we start with, say, $(2,0,0)$ then we have no legal moves and therefore no way to get down to only one chip.

Therefore, if we rephrase the claim, we can say that the claim asks us to show that there is a function

$$f:N^3\to \{\text{white},\text{black},\text{red},\text{none}\}$$

which sends each state to a particular color if we can end up with a single chip of that color, and sends a state to "none" if there's no way to end up with a single chip from that initial state. This is the part of the claim which says that the color of the final chip should be independent of the sequence of moves we choose to make: it can only be a function of the current state of the game, not of what the players choose to do later on.

Furthermore, we can notice that we lose nothing by allowing moves to be inverted in this game (why?). This means $f$ actually has to be invariant under all legal moves.

What is a good guess for what this function could be? The simplest guess is that it's a linear function: we have some expression like

$$f(x_1,x_2,x_3)=x_1{v}_1+x_2{v}_2+x_3{v}_3$$

where the $v_i$ are some numbers, and these outputs correspond in some way to the four possible values of the function. If we impose the requirement that $f$ ought to be invariant under our three legal moves, we get a system of three equations for the numbers $v_i$:

$$v_1=v_2+v_3{v}_2=v_1+v_3{v}_3=v_1+v_2$$

However, when we try to solve this system, we're forced to face an unfortunate reality. Substituting the first equation to the second gives $v_2=v_2+2v_3$ or $2v_3=0$, so we deduce $v_3=0$, and similarly we deduce $v_1=v_2=0$ as well. Therefore the only solution to this system seems to be trivial: $f$ is simply zero on every possible state. This is indeed invariant under all the moves, but it doesn't give us any information about the states, so it's not what we are looking for.

At this point, you might be tempted to give up and conclude that a linear invariant doesn't work after all. You could look for some $f$ having a different form or some entirely different approach to solve this problem.

This is a common situation in mathematics: you have some idea to solve a problem but it doesn't work, at least not the way you tried to execute it. However, that doesn't mean the idea itself doesn't have merit, and often it only takes some effort on the part of the mathematician to bring what seems like a dead idea back to life by putting the idea in a different context or looking at it from a different perspective.

Let's go back and examine what we did when we concluded no linear invariant could work. If the $v_i$ are indeed real numbers, our solution of the linear system is impeccable: the only solution is indeed trivial. However, what if the $v_i$ don't have to be real numbers?

We smuggled in an assumption which might not even seem like one if we don't pay attention: that $2v=0$ implies $v=0$. If this assumption holds and addition has all of its usual properties, it's indeed true that the only solution to this system will be trivial. However, this doesn't have to be the case. What if, in whatever structure we happen to be working in, $2=0$?

There is a notable example in which this is true: the integers modulo $2$, often denoted as $Z/2Z$. This means we declare that two integers are the same if they have the same remainder when divided by $2$. This definition turns out to be well-behaved and compatible with addition and multiplication of integers, so it's a legitimate structure (specifically, an abelian group) in which $2$ is equal to $0$.

We can notice this structure doesn't quite meet our needs: we need $f$ to take four possible values, but the integers modulo 2 only have two possible values: 0 and 1. It's not too far off, however, and we only need one last idea to come up with the right structure which will solve the problem. What if $f$ takes not one, but two values in $Z/2Z$? In other words, what if $f$ takes a pair of values in the integers modulo 2?

We notice this set has the right size: there are four such pairs and four values that we need in the codomain of $f$. It's also obvious what values the $v_i$ have to take: there are only three nonzero pairs, so we must have some permutation of

$$v_1=\left[\begin{array}{c}1\\ 0\end{array}\right],v_2=\left[\begin{array}{c}0\\ 1\end{array}\right],v_3=\left[\begin{array}{c}1\\ 1\end{array}\right]$$

If you check the three linear equations we wanted to be satisfied earlier, you'll find that these values of the $v_i$ satisfy all of them!

This means we've solved the problem, as will be clear shortly. $f$ is defined as follows:

$$f(x_1,x_2,x_3)=\left[\begin{array}{c}{x}_1+x_3\\ x_2+x_3\end{array}\right]$$

and we consider the right hand side to be a pair of values, each living in the integers modulo 2. In other words, $f$ is a function $N^3\to (Z/2Z{)}^2$.

Finally, we do the translation of these pairs to the four elements we defined earlier as follows:

$$\text{white}=\left[\begin{array}{c}1\\ 0\end{array}\right],\text{black}=\left[\begin{array}{c}0\\ 1\end{array}\right]\text{red}=\left[\begin{array}{c}1\\ 1\end{array}\right],\text{none}=\left[\begin{array}{c}0\\ 0\end{array}\right]$$

This definition of $f$ is not quite what we wanted, since it will assign colors to configurations such as $(3,0,0)$ which really have no way of being reduced to a single chip state. However, this turns out to be unimportant for solving the problem. If we start from a state $S_i$ and end up in a single-chip state $S_f$ after some legal moves, then since $f$ is invariant under the moves we have $f\left(S_i\right)=f\left(S_f\right)$, and since all three single chip states have distinct values of $f$ this means there can only be one single chip state reachable from any initial state $S_i$.

This is a toy example intended to be accessible to a more general audience, but the general message is very powerful: many abstract concepts in mathematics arise from "trying to make ideas work" in this way. Often if an idea doesn't work, the problem is not with the idea itself but with your intellectual tools or the power of the concepts at your disposal. Noticing this can both provide an opportunity to expand these tools and to save some ideas from being prematurely consigned to the garbage bin.

7 comments

Comments sorted by top scores.