水果魔法碰撞

Fruit Magic

专题: Discrete Math / 离散数学
难度: L4
来源: Brainstellar

题目详情

帽子里有 13 个苹果、15 根香蕉、17 个樱桃。

每当两种不同水果发生一次“碰撞”，它们会同时变成第三种水果（例如 1 苹果 + 1 香蕉 → 2 樱桃）。

问：是否存在一系列碰撞，能让 45 个水果最终全部变成同一种？

提示：找一个在碰撞中保持不变的不变量。

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?

Hint

This can't be done. Try to create a function of A,B,C which remains constant during a collision to get contradiction.

解析

不能。

设当前数量为 $(A,B,C)$ ，构造不变量

(A+2C)\bmod 3

（等价于 $(0\cdot A+1\cdot B+2\cdot C)\bmod 3$ ）。每次碰撞会让 $(A,B,C)$ 在模 3 意义下保持该值不变。

初始 $(13,15,17)$ 的不变量值为 1，而目标态 $(45,0,0)$ 、 $(0,45,0)$ 、 $(0,0,45)$ 的不变量值都为 0，矛盾，因此无法达到。

Original Explanation

Solution

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.

A refreshment to this old trick was given by Aritro Pathak: call the no of times apples are increased by 2 as A, bananas increased by 2 as B, and cherries increased by 2 as C. if we need 45 apples,total increments - decrements of apple = 32 but increments of apple = 2 * A; when ever 2 banana's are created, 1 Apple is lost, similarly for 2 cherries decrements = B+C

thus we have 2A-B-C=32, -2B+C+A=15, -2C+B+A=17. Subtract the last two to get 2=3 * (B-C) which is impossible. similar cases for when you want 45 of either cherries or bananas.