Friday, November 25, 2011

The blue and yellow particles problem

Some time ago, I read the following problem:
In a box, there is a certain amount of blue and yellow particles. The particles can react with each other in three different ways:
• Two yellow particles can fuse into a blue particle
• Two blue particles can fuse into a blue particle
• An yellow and a blue particle can fuse into an yellow particle
Given the initial amount of yellow and blue particles, which color will be the last particle?
I was kinda confused with this problem. My first thought was "How the hell am I supposed to know? Can't the three types of reactions happen in different orders which may eventually lead to last particles with different colors?" The problem wording seemed to tell you that the color of the last particle only depended on the number of initial particles of each color. This appeared to be true, because every time I drew a box with a certain amount of blue and yellow particles, I couldn't find two different sequences of reactions which would produce last particles with different colors.
To solve this problem let's start by writing some math. Hopefully it will lead us to the solution.

The first thing I did was to define three functions to represent the possible reactions. Each function receives and returns a pair of values, nBlues and nYellows which represent the number of particles of each color in the box. The functions argument correspond to the state of the box before the reaction and the function return value represent the state after the reaction. I defined these functions in Mathematica (a computer program) like this:
bb[{nBlues_, nYellows_}] := {nBlues, nYellows} + {-1, 0}
yb[{nBlues_, nYellows_}] := {nBlues, nYellows} + {-1, 0}
yy[{nBlues_, nYellows_}] := {nBlues, nYellows} + {1, -2}

The name of the functions correspond to the reaction they represent.
• The blue-blue function will return a "box" from which one blue particle was taken because two blue particles fuse into one in the corresponding reaction.
• The yellow-blue function will return a "box" from which one blue particle was taken because one blue particle and one yellow particle fuse into one yellow particle in the corresponding reaction .
• The yellow-yellow function will return a "box" from which two yellow particles were taken and one blue particle was added because two yellow particles fuse into one blue particle in the corresponding reaction.
Ok, suppose you want to know the resulting state of having a box with 5 blue particles and 6 yellow particles after a serie of reactions, for example (in left to right order): bb,yb,bb,yy. All you have to do is to write:
yy[bb[yb[bb[{5, 6}]]]]

Notice that the function at the right is calculated before the function at left. Mathematica will output:
{3, 4}

Mathematica is an algebra system software, so it can also do math with symbols which can represent, for example, variables:
yy[bb[yb[bb[{a, b}]]]]

Output:
{-2 + a, -2 + b}

Now, let's define some notation. Let $$f$$ be a function, and $$n$$ be a number. We will say that: $$\underbrace{f(f(...f(x)...))}_{f \textrm{ composed } n \textrm{ times}} = \underbrace{f \circ f \circ ...\circ f(x)}_{f \textrm{ composed } n \textrm{ times}} = f^{n}(x)$$ Since all the functions we defined are commutative between each other (this is really easy to prove so let's skip this job and give it to Mathematica):
bb[yb[{a, b}]]
{-2 + a, b}
yb[bb[{a, b}]]
{-2 + a, b}
bb[yy[{a, b}]]
{a, -2 + b}
yy[bb[{a, b}]]
{a, -2 + b}
yy[yb[{a, b}]]
{a, -2 + b}
yb[yy[{a, b}]]
{a, -2 + b}

,we can write any sequence of reactions that happens in the box as:
$$bb^a \circ yb^b \circ yy^c$$ Where $$a$$,$$b$$ and $$c$$ correspond to the number of times each kind of reaction happened. So, for example, the sequence of reactions yb,yy,bb,yy,bb,bb,yb could be represented as $$bb^3 \circ yb^2 \circ yy^2$$.
Notice we can only say this because all the functions we have are commutative. Suppose there is another reaction $$dd$$ where, for example, the number of yellow particles in the box is doubled. The corresponding function would not be commutative with the rest of the functions we already have, i.e $$(dd \circ yy(4,5) = (5,6)) \ne (yy \circ dd(4,5) = (5,8))$$ so we couldn't change the order in a composition of functions and expect the same result.

The following equation now emerges:
$$(b_{\textrm{final}},y_{\textrm{final}}) = bb^a \circ yb^b \circ yy^c(b_{\textrm{initial}},y_{\textrm{initial}})$$ It is also not hard to come up with the conclusion that:
\begin{array}{lcl} bb^a(b_{\textrm{initial}},y_{\textrm{initial}}) = (b_{\textrm{initial}}-a, y_{\textrm{initial}})\\ yb^b(b_{\textrm{initial}},y_{\textrm{initial}}) = (b_{\textrm{initial}}-b, y_{\textrm{initial}})\\ yy^c(b_{\textrm{initial}},y_{\textrm{initial}}) = (b_{\textrm{initial}}+c, y_{\textrm{initial}} - 2c)\\ \end{array} I'll prove the third equality. The others are analogous.
\begin{array}{lcl} yy^c(b_{\textrm{initial}},y_{\textrm{initial}})=((...((b_{\textrm{initial}},y_{\textrm{initial}})+\underbrace{(1,-2))+(1,-2))+...)+(1,-2)}_{(1,-2) \textrm{ is summed } c \textrm{ times}})\Leftrightarrow \\ yy^c(b_{\textrm{initial}},y_{\textrm{initial}})= (b_{\textrm{initial}}+c,y_{\textrm{initial}}-2c) \end{array} Now we can have a more workable equation:
$$(b_{\textrm{final}},y_{\textrm{final}}) = bb^a \circ yb^b \circ yy^c(b_{\textrm{initial}},y_{\textrm{initial}}) \Leftrightarrow (b_{\textrm{final}},y_{\textrm{final}}) = (b_{\textrm{initial}}-a-b+c,y_{\textrm{initial}}-2c)$$ In our problem, we want to find out what color the last particle will be. If it is the last one, then we know that $$b_{\textrm{final}} + y_{\textrm{final}} = 1$$ Using all our equations, we can write the following system where all variables are natural numbers:
\begin{cases} b_{\textrm{final}} = b_{\textrm{initial}}-a-b+c \\ y_{\textrm{final}} = y_{\textrm{initial}}-2c \\ b_{\textrm{final}} + y_{\textrm{final}} = 1 \end{cases} We have two possibilities for the $$(b_{\textrm{final}},y_{\textrm{final}})$$: $$(0,1)$$ and $$(1,0)$$.
If $$(b_{\textrm{final}},y_{\textrm{final}})=(1,0)$$ then:
$$y_{\textrm{initial}} = 2c \wedge b_{\textrm{initial}} = 1 + a + b - c$$ $$2c$$ is even, so we can say that
$$(b_{\textrm{final}},y_{\textrm{final}})=(1,0)\Rightarrow y_{\textrm{initial}} \textrm{ is even}$$ If $$(b_{\textrm{final}},y_{\textrm{final}})=(0,1)$$ then:
$$y_{\textrm{initial}} = 2c + 1 \wedge b_{\textrm{initial}} = a + b - c$$ $$2c + 1$$ is odd, so we can say that
$$(b_{\textrm{final}},y_{\textrm{final}})=(0,1)\Rightarrow y_{\textrm{initial}} \textrm{ is odd}$$ The meaning of an implication is that if $$a$$ implies $$b$$, every time $$a$$ is true, $$b$$ is also true. And there is only one final result which leads to an even initial number of yellow particles, and one final result which leads to an odd initial number of yellow particles. So
\begin{array}{lcl} y_{\textrm{initial}} \textrm{ is even} \Rightarrow (b_{\textrm{final}},y_{\textrm{final}})=(1,0) \\ y_{\textrm{initial}} \textrm{ is odd} \Rightarrow (b_{\textrm{final}},y_{\textrm{final}})=(0,1) \end{array} are also true statements. Now we can finally give a justified answer to the problem:
Given the initial amount of yellow and blue particles, which color will be the last particle?
If the amount of yellow particles is even, the last particle will be blue. If it is odd, the last particle will be yellow. In this case, the last particle will be yellow. I guess that's why the yellow particle is smiling :D