18
$\begingroup$

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?

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 get the 'Ahaa!' effect when I thought about this problem, 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)$?

$\endgroup$
  • 3
    $\begingroup$ What an incredibly nice problem! $\endgroup$ – AlgebraicsAnonymous Jul 16 '18 at 8:42
  • $\begingroup$ I gave you a plus just for inventing the word "arbuzoid". $\endgroup$ – Michal Adamaszek Jul 16 '18 at 8:58
  • 3
    $\begingroup$ Cross-site related: puzzling.stackexchange.com/questions/48063/… $\endgroup$ – GOTO 0 Jul 16 '18 at 12:09
  • $\begingroup$ Have 1 blue meet a green, then all the remaining blues meet a red. Now your problem is 1 red, 0 blue, and 44 green. Does that make it any easier for you? $\endgroup$ – Benubird Jul 16 '18 at 16:15
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you know that you can reach all combinations with those 3 vectors? $\endgroup$ – Comparative Jul 16 '18 at 8:49
  • 6
    $\begingroup$ The sum $\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}$ gives you the number of red, green and blue arbuzoids after $a$ green-blue meetings, $b$ red-blue meetings and $c$ red-green meetings. $\endgroup$ – Luca Bressan Jul 16 '18 at 8:52
  • 3
    $\begingroup$ I get it, The order doesn't matter. thanks $\endgroup$ – Comparative Jul 16 '18 at 8:53
  • 4
    $\begingroup$ The order would begin to matter if we hadn't learned at this point that the task was impossible. Then we'd need to figure out if the required meets can be ordered such that none of the counts drop below zero. For example, the linear algebra doesn't tell us that it's impossible to make 3 red arbuzoids into 3 blue ones, though in order to actually do that we'd need to borrow a green one from somewhere (and return it afterwards). $\endgroup$ – Henning Makholm Jul 16 '18 at 20:42
  • $\begingroup$ @HenningMakholm,It becomes a problem when we generalize the case to $r, g, b$ arbuzoids. then we would have to prove not just that there exists such a parameter $n$, but also that we can find an order of meetings such that there is no negative arbuzoid at any point of the order. I will work on that. $\endgroup$ – Comparative Jul 16 '18 at 21:22
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I, too, noted this in my 'noted a few things', but I didn't consider it a proof. I assumed that this still doesn't make it impossible. $\endgroup$ – Comparative Jul 16 '18 at 9:16
  • $\begingroup$ And also, my program was to make two colors equinumerous. $\endgroup$ – Comparative Jul 16 '18 at 9:21
  • 4
    $\begingroup$ @JavaLearner Why would you not consider this a proof? To make it more formal, just work modulo $3$. The initial numbers all different mod $3$ - $(13,15,17)\equiv (1,0,2)$ so all three differences are non-zero mod $3$. None of the moves change these differences mod $3$, so the differences remain non-zero. Therefore no two colours can become equal, and in particular they can't all become one colour since that would make the two other colours equal (to zero). But the more informal answer is just as much a proof as this. $\endgroup$ – Jaap Scherphuis Jul 16 '18 at 9:27
  • $\begingroup$ Ok, It looks like I haven't thought about it well. I get the proof now. $\endgroup$ – Comparative Jul 16 '18 at 9:33
  • $\begingroup$ I like this answer, but the linear algebra answer is the most relevant, since I found the problem on my linear algebra book $\endgroup$ – Comparative Jul 16 '18 at 9:36
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Well, I am still learning about set theory, and I haven't reached modules. $\endgroup$ – Comparative Jul 16 '18 at 8:45
  • $\begingroup$ You don't need really need the modules, it's just about the equation $(13, 15, 17) = (2x - y - z, \ldots)$. If you believe me that this would hold, you're done. $\endgroup$ – AlgebraicsAnonymous Jul 16 '18 at 8:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.