Can all arbuzoids assume the same color?

This puzzle is from a Russian web-site http://www.arbuz.uz/ and there are many solutions to it, but mine uses linear algebra and is very naive. There’s a planet inhabited by arbuzoids (watermeloners, to translate from Russian). Those creatures are found in three colors: red, green and blue. There are 13 red arbuzoids, 15 blue ones, and 17 green. When two differently colored arbuzoids meet, they both change to the third color. The question is, can it ever happen that all of them assume the same color?

Edited: Apr 10, 2021, I just wanted to add that this is quoted from Jim Hefferon, Linear Algebra.

I still have no idea how this problem carved its way into my Linear Algebra book, but I gave it a go. Strangely, I didn't realize the relationship this had with Linear Algebra, so I decided to formalize it.

let $S$ be a set such that:

$\langle 13, 17, 15\rangle \in S $

$\forall r,g,b,a \in \mathbb N ( \langle r,g,b\rangle\in S \to ($ $[(a \leq r \land a\leq g) \to \langle r-a,g-a,b+2a\rangle \in S] \land$ $\qquad\qquad\qquad\qquad\qquad\qquad\quad\space[(a \leq r \land a\leq b) \to \langle r-a,g+2a,b-a\rangle \in S] \land$ $\qquad\qquad\qquad\qquad\qquad\qquad\quad\space[(a \leq g \land a\leq b) \to \langle r+2a,g-a,b-a\rangle \in S] \space ))$

We have to show that:

$\exists a \in \mathbb N(\langle a,0,0 \rangle\in S \lor \langle 0,a,0 \rangle\in S \lor \langle 0,0,a \rangle\in S) \tag{I}$

or..

$\not\exists a \in \mathbb N(\langle a,0,0 \rangle\in S \lor \langle 0,a,0 \rangle\in S \lor \langle 0,0,a \rangle\in S) \tag{II}$

I don't know how this is at all related to Linear Algebra, and I barely know anything about set theory, so bye.

What I did

I started from the first element in $S$, as shown.

First start with the element. remember, the order is red, green, blue:$\langle 13,17,15 \rangle \in S \tag{0}$ Eliminate the red arbuzoids:$\langle 0,43,2 \rangle \in S \tag{1}$ combine $1$ green with $1$ blue: $\langle 2,42,1 \rangle \in S \tag{2}$

Note that if the blue arbuzoids in $(1)$ were $3$, the problem would have been solved.Also, If they had been any multiple of 3 less than or equal to green, the problem would have been solved, since you'll combine 1 third of blue with green, and then red and blue would be equal, then you combine them, and get all green.

Anyway,the blue arbuzoids were not 3. I did many failed steps, noting a few things, and I couldn't get anything. I decided to write some code to test(i.e brute force the combinations and find) whether it's possible, starting from (2), but it failed to reach anything.

Can you prove $(I)$, or $(II)$?

Solution 1:

The problem can be equivalently stated as follows:

Find $a, b, c \in \mathbb N$ such that $$\begin{pmatrix} 13 \\ 17 \\ 15\end{pmatrix} + a\begin{pmatrix} 2 \\ -1 \\ -1 \end{pmatrix} + b\begin{pmatrix} -1 \\ 2 \\ -1 \end{pmatrix} + c \begin{pmatrix} -1 \\ -1 \\ 2 \end{pmatrix} \in \left \{ \begin{pmatrix} 45 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 45 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 45 \end{pmatrix} \right \}$$

This amounts to solving three linear systems.

For example, the first one is given by: $$\begin{pmatrix} 13 \\ 17 \\ 15\end{pmatrix} + a\begin{pmatrix} 2 \\ -1 \\ -1 \end{pmatrix} + b\begin{pmatrix} -1 \\ 2 \\ -1 \end{pmatrix} + c \begin{pmatrix} -1 \\ -1 \\ 2 \end{pmatrix} = \begin{pmatrix} 45 \\ 0 \\ 0 \end{pmatrix}$$ and can be rewritten as $$\begin{cases} 2 a - b - c = 32 \\ -a + 2b - c = -17 \\ -a - b + 2 c = -15 \end{cases}$$ Solving for $a, b, c$ we obtain $$a = n, \qquad b = n - \frac {49} 3, \qquad c = n - \frac {47} 3$$ where $n$ is a parameter. Since $a, b, c$ must be positive integers, there is no solution.

Solution 2:

Take the difference between any two colours. For example $G-R=17-13=4$.

Now consider how any colour change will affect this difference. It is unchanged if red+green become blues, will increase by $3$ if blue+red become greens, and will decrease by $3$ if blue+green become reds.

The difference is not itself a multiple of $3$, so it can never become zero by these colour changes. The same is true of any pair of colours, so it isn't even possible for any two colours to become equinumerous, let alone for both to become zero.

Solution 3:

The point is that we may consider the free module $M := \mathbb Z^3$. In it, we have the submodule

$$ N := \langle (-1, -1, 2), (-1, 2, -1), (2, -1, -1) \rangle $$

and the residue class

$$ (13,15,17) + N; $$

we want to check whether or not $0$ is in that residue class; this is because we can undo color changes:

$$ (a,b,c) \to (a+2,b-1,c-1) \to (a+1,b-2,c+1) \to (a,b,c), $$

so that $N$ may be assumed a submodule, since it's closed under (additive) inversion. Hence, the problem implies a solution of

$$ (13,15,17) = (2x - y - z, 2y - x - z, 2z - x - y) $$

in integers $x, y, z$. But a clever series of insertions leads to the equation $$ 3(x-y) = 43, $$ which is unsolvable in the integers because $43$ is not divisible by $3$.

Solution 4:

Another way of solving it: suppose it takes 8 hours to feed a red arbuzoid, 16 for a blue one, and 24 for a green one. How will the total amount of time it takes to feed all the arbuzoids be affected by them changing colors? If a red and blue meet, then the total decreases by 8 for losing a red one and 16 for losing blue one, but increases 48 for getting two green ones. The net result is an increase of 24 hours. For a red and green one, the net is 16*2-8-24 = 0. For a blue and green, it's 8*2-16-24 = -24. So every time two arbuzoids meet, the total time changes by an integer number of days. But if you add up the time for the current number of arbuzoids, it's 31 days and eight hours. If you start with a non-integer number of days, and change it by an integer number of days, then you end up with a non-integer number of days. But since there are 45 arbuzoids, having them be all red would give you 15 days, an integer number. All blue would be 30, and all green would be 45.

That is, we start with a non-integer number of days, we're trying to get to an integer number of days, but there's no way to change the total by a fractional number of days.

Put in mathematical terms, if a r = 1, b = 2, and g = 0, then:

$r+b-2g\equiv r+g-2b\equiv b+g-2r\equiv0mod3$

So none of these meetings change the total, mod 3. But:

$13r+15b+17g\equiv1mod3$

$45r \equiv 45b \equiv 45g \equiv 0 mod3$

So to get from the starting situation to all one color, the total, mod 3, must change.