| medium | discrete |
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?
This can't be done. Try to create a function of A,B,C which remains constant during a collision to get contradiction.
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.