Intuition for this tricky puzzle

Question

Problem : $13$ Apples, $15$ Bananas and $17$ Cherries are put in the magic hat. When ever a collision of two different fruits occurs, they both get converted into the third type. For example $1$ Apple and $1$ Banana can collide to form $2$ cherries. No other collision is holy. Can a sequence of such magical collisions lead all $45$ fruits to give just one type?

Solution provided : Create the invariant function $f(A,B,C) = (0A+1B+2C)mod3$, this function remains constant during a collision. But $f(13,15,17) = 1$ is not same as any of final states $f(45,0,0)=f(0,45,0)=f(0,0,45)=0$. Hence this can not be done.

Query : I understood the solution but it seems non-intuitive to me. Is there any better solution to this problem?

Answer 1

In fact, in any collision, each of the $3$ numbers gets decremented by $1 \pmod 3$, or equivalently, gets incremented by $2 \pmod 3$.

This gives several invariants which would work, incl. the given $(0A + 1B + 2C) \pmod 3$. This is of course equivalent to $(B-C) \pmod 3$ which is symmetric with lulu's $(A-B)\pmod 3$.

Or you can simply argue that, since the $3$ numbers did not start as equal $\pmod 3$, you cannot get to $(45,0,0) = (0,45,0) = (0,0,45) = (0,0,0) \pmod 3$.

Answer 2

Well.... intuition is iffy....

Let suppose there are $M_i$ collisions of each type.

So if there are $M_a$ collision of bananas and cherries you will end up with $13+2M_a$ apples, $15-M_a$ bananas, and $17-M_a$ cherries.

And if $M_b$ are the collision of apples and cherries and $M_c$ are the collisions of apples and bannanas we end up with:

$(13 + 2M_a -M_b -M_c)$ apples, $15-M_a + 2M_b - M_c)$ bananas, and $17-M_a - M_b +2M_c$ cherries.

Three cases:

Only apples left so

$13+2M_a - M_b - M_c =45; 15-M_a + 2M_b-M_c = 0; 17-M_a-M_b + 2M_c = 0$

$2M_a = 32+M_b+M_c;15+2M_b = M_a + Mc; 17+2M_c = M_a+M_b$.

$30+4M_b = (32+M_b+M_c) + 2Mc; 34 + 4M_c = (32+M_b+M_c)+ 2M_b$

$3M_b = 2+3M_c$ which is not possible.

Similar con be shown for bananas or cherries.

And ....

Now at this point we realize that the gyst of the argument is a modulo $3$ argument and you figure:

If you start with $T_{x,y,z}$ of fruits $x,y,z$ and you end up with entirely $K$ of fruit $x$ then you must have

$T_x +2M_x - M_y -M_z=K$ so $2M_x = (K-T_x) + M_y +M_z$ while

$T_y + 2M_y -M_x - M_z = 0$ so $2T_y + 4M_y = 2M_x +2M_z=(K-T_x)+M_y+3M_z$ so

$ 3M_y = (K-T_x - 2T_y)+3M_z$ and $3M_z = (K-T_x-2T_z) +3M_y$.

And thus this can break down into whether $K-T_x- 2T_y \equiv 0 \pmod 3$

In this case neither $45 - (13|15|17) - 2(\{15|17\}\{13|17\}\{13|15\})\equiv (-1|0|1)+(\{0|-1\}\{1|-1\}\{1|0\})\equiv (\{-1|1\}\{1|-1\}\{-1,1\})\not\equiv 0\pmod 3$.

....

But if we notice that $K - T_x - 2T_y = T_z-T_y (= -(K-T_x-T_z))$ then we get that to get all of one fruit you must have: The two fruits that end up with $0$ with $T_y \equiv T_z\pmod 3$.

And as $13,15,17$ are distinct $\mod 3$ this can't be done.

But I guess if you had say $13$ apples and $15$ bannanas and $18$ cherries you could conceivably end up with $46$ apples.

We'd have $3M_b=3+3M_c$, For example if we have $1$ apple/cherry collisio to make $12$ apples, $17$ bananas, and $17$ cherries and then then $17$ banana/cherry collisions to get $46$ apples. (Or any $x$ apple/banana collisions to make $13-x$ apple, $15-x$ bananas, $18+2x$ cherries, and $x+1$ apple/cherry collisions to get $12-2x$ apples, $17+x$ bananas, and $17+x$ cherries, and then $17+x$ banana/cherry collisions to get $12-2x+34+2x=46$ apples.

Which will set us to looking for preserving functions.... I guess.