Linear Algebra – Can All Arbuzoids Assume the Same Color?

elementary-set-theorylinear algebrapuzzle

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)$?

Best Answer

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.

Related Question