Fun Interview Question

[JeongHaCho]

Hi all,
yesterday I had my 4th phone interview with a decent company and I couldn't give the right answer for one question on time(10mins) BUT managed to solve it after the interview ended.
The question is the following.
There are 3 types of cats. Blue, Green and Purple.
These cats are magical and if a blue and green cat meet they both turn into purple. If green and purple meet they both turn into blue. Lastly, if purple and blue meet they both turn into green.
The question is whether it is possible for all the cats to become the same color.

I would like to know a very fast idea to solve it because it took me some time to rigorously prove it.
The purpose of my post is to know a lot of different ways to solve this problem if there exists.

I'll post my solution after a couple of hours.

Thank you so much.:D

 

[amraj]

"There are 3 types of cats. Blue, Green and Purple.
These cats are magical and if a blue and green cat meet they both turn into purple"

Have you stated the question incorrectly?. When a B and G cat meet, they both become P. So you have three P cats???

 

[JeongHaCho]

@amraj I'm so sorry. I just realized that I missed writing that there are 13 blue cats, 15 green cats and 17 purple cats. Thanks a lot.

 

[amraj]

@amraj I'm so sorry. I just realized that I missed writing that there are 13 blue cats, 15 green cats and 17 purple cats. Thanks a lot.

LOL. Makes a 'slight' difference. Change it in the question by pressing edit so that it is clear

 

[Daniel Duffy]

Compute exp(5) to two decimal places using just pencil and paper.

 

[tjk]

Answer to cat question-- not possible

 

[JeongHaCho]

@amraj Seems like I can't edit it after someone added a reply. Sorry.
@tjk The answer needs the explanation how it can be done or why it cannot be done. Thanks!

 

[Jakelaker]

Start with an even amount of purple cats and work backwards using a tree diagram or whatever. Do the same for odd amount. I found that the height of each tree was 2 so it can be done mentally.

You will arrive at some ratios of R : B : P cats. From my non-rigorous, intuitive working, my conclusion was that there must be equal amount of two colour of cats (e.g. 1B 1G xP) and this is not the case for the question, hence cannot be done.

Is it this reasonable?

 

[Pavlos Sakoglou]

Start with an even amount of purple cats and work backwards using a tree diagram or whatever. Do the same for odd amount. I found that the height of each tree was 2 so it can be done mentally.

You will arrive at some ratios of R : B : P cats. From my non-rigorous, intuitive working, my conclusion was that there must be equal amount of two colour of cats (e.g. 1B 1G xP) and this is not the case for the question, hence cannot be done.

Is it this reasonable?

You can also do it that way:
Since order doesn't matter, you have three unique cat meet ups, i.e. BinomialCoeff(3,2) to find non-duplicate pairs:
1) (B, G)
2) (B, P)
3) (P, G)
Thus
13B meets 15G => 13P + 17P + 2G = 30P + 2G (doesn't work)
13B meets 17P => 13G + 15G + 4P = 28G + 4P (doesn't work)
17P meets 15G => 2P + 15B + 13B = 28B + 2P (doesn't work)
Thus, it cannot be done.

Or

(mod 10) each cat group, since 10B + 10G = 10P and the remainders are 3, 5, 7 respectively. Then apply the same logic as before and you arrive at the same conclusion.

 

[Jakelaker]

You can also do it that way:
Since order doesn't matter, you have three unique cat meet ups, i.e. BinomialCoeff(3,2) to find non-duplicate pairs:
1) (B, G)
2) (B, P)
3) (P, G)
Thus
13B meets 15G => 13P + 17P + 2G = 30P + 2G (doesn't work)
13B meets 17P => 13G + 15G + 4P = 28G + 4P (doesn't work)
17P meets 15G => 2P + 15B + 13B = 28B + 2P (doesn't work)
Thus, it cannot be done.

Or

(mod 10) each cat group, since 10B + 10G = 10P and the remainders are 3, 5, 7 respectively. Then apply the same logic as before and you arrive at the same conclusion.

So I'm guessing my method is still reasonable?

I tried your first method originally but did not recognise that order doesn't matter and therefore thought that you could somehow combine it using some ingenious ordering.

Also, you mean 10B + 10G = 20P, right?

 

[Pavlos Sakoglou]

So I'm guessing my method is still reasonable?

I tried your first method originally but did not recognise that order doesn't matter and therefore thought that you could somehow combine it using some ingenious ordering.

I didn't work out your method, but we are assuming that:
B meets G == G meets B
P meets G == G meets P
P meets B == B meets P
That is, in the 3-tuple of cat colors: (B, G, P) there are 3! possible meet ups, but only BinomialCoeff(3,2) meaningful ones for the problem.

 

[JeongHaCho]

@Jakelaker I think you got very close to the solution but you still need to prove why having an equal amount of cats is not the case for this question. I don't get you're method of working backwards though. Do you mean you start with all purple cats and try to get to 13 blue, 15 green and 17 purple cats? How is this done?
@Pavlos Sakoglou Thanks for the solution. But why are you sure that just these 3 different ways of meetings are the only possible ways to show that it doesn't work? I think there could be a lot of color changes not just by meeting once.

This is how I thought about it. Since we need to get to 1 color starting from 3 different colors, I thought it would be best to decrease the type of colors to 2 first and then to 1. But since we have 45 cats in total, the 2 numbers of cats of 2 different types would never be equal and any meeting would give us 3 different colors again. So, I thought there should be some meeting that gives 1 color from 3 colors immediately but this is possible iff the numbers of any 2 types of cats are equal after some meetings.(As Jakelaker wrote)
But this never happens, because any meeting would always give us 3 different numbers of the 3 different cat types. This could be proved as follows.
Any meeting can be broken down into single meetings. For instance, 1 blue cat and 1 purple cat meet. Then we have (13, 15, 17)->(12, 17, 16) and the numbers are all different. This is always the case because blue and purple which are the cat types that meet started from unequal numbers and so they would never be the same after the single meeting.
Blue and green or green and purple can never be the same because the differences should've been 3 to be equal(Green increases by 2 but the other two decrease by 1).
Likewise, successive meetings would always end up in 3 different numbers because the differences between the numbers have changed by a multiple of 3 from 2,2, and 4 which are not multiples of 3 and so are not equal to 3.
Finally, starting from the fact that the difference between any pair of the cats are 2, 2, and 4 and each meeting changes the differences by 3 and using mathematical induction finishes the proof.
Proving the claim that there could never be an equal number of cats of different types, shows that we cannot reach (0,0,45), (0,45,0), or (45,0,0) starting from (13,15,17).

 

[Jakelaker]

@Jakelaker I think you got very close to the solution but you still need to prove why having an equal amount of cats is not the case for this question. I don't get you're method of working backwards though. Do you mean you start with all purple cats and try to get to 13 blue, 15 green and 17 purple cats? How is this done?

Here is some notation. 4P -> {2B, 2G} reads "4 purple cats splits into 2 blue and 2 green cats."
Start with all purple cats, so there arises two cases. For some positive integer n, we have

Case 1: even (2n) purple cats.
Sub-case 1.1: 2n purple cats splits into an even amount of blue and green cats. i.e. (2n)P -> {(2k)B, (2k)G}.
Sub-case 1.1.1: 2k blues can split into an even amount of blue and green cats
Sub-case 1.1.2: 2k blues can split into an odd amount of blue and green cats

Sub-case 1.2: 2n purple cats splits into an odd amount of blue and green cats i.e. (2n)P -> {(2k+1)B, (2k+1)G}. Then isolate a blue and green cat so we split them again.
Sub-case 1.2.1: etc
Sub-case 1.2.2: etc

Case 2: odd (2n+1) purple cats. Hide one purple cat so you have 2n left, then do the same thing as case 1.

You end up with n:n:Xn ratios but I really haven't tried some of the cases since it seems too tedious to do on the spot.

 

[Peppino]

Let's call the three types of cats a,b and c
After a colour-change the number of cats changes from (a,b,c) to (a-1,b-1,c+2) modulo permutations.
We will use the second symmetric polynomial (that is invariant to permutations) to help us. Let
F(a,b,c)=ab + bc + ac mod 3
If some cats change colours, we have
F(a-1,b-1,c+2)=(a-1)(b-1)+(b-1)(c-1)+(a-1)(c-1)=ab + bc + ca - 2a - 2b - 2c +3 =ab + bc + ca + (a + b + c) mod 3
Because our starting values are a=13,b=15,c=17 we have a+b+c =0 mod 3 and thus
F(a-1,b-1,c+2)=ab+bc+ac=F(a,b,c) mod 3
So F(a,b,c) is really invariant to colour-changing. Now, F(13,15,17)=2 mod 3, but if we happened to have all the cats of the same colour, we'd have F=0 contraddicting the invariance of F.

 

[JeongHaCho]

Let's call the three types of cats a,b and c
After a colour-change the number of cats changes from (a,b,c) to (a-1,b-1,c+2) modulo permutations.
We will use the second symmetric polynomial (that is invariant to permutations) to help us. Let
F(a,b,c)=ab + bc + ac mod 3
If some cats change colours, we have
F(a-1,b-1,c+2)=(a-1)(b-1)+(b-1)(c-1)+(a-1)(c-1)=ab + bc + ca - 2a - 2b - 2c +3 =ab + bc + ca + (a + b + c) mod 3
Because our starting values are a=13,b=15,c=17 we have a+b+c =0 mod 3 and thus
F(a-1,b-1,c+2)=ab+bc+ac=F(a,b,c) mod 3
So F(a,b,c) is really invariant to colour-changing. Now, F(13,15,17)=2 mod 3, but if we happened to have all the cats of the same colour, we'd have F=0 contraddicting the invariance of F.

Thanks for providing a great alternative insight. Just minor questions though.
F(a-1,b-1,c+2)=(a-1)(b-1)+(b-1)(c-1)+(a-1)(c-1).
Here, c-1 should be replaced by c+2, right?
But then I don't think it's enough to just check that a+b+c=o mod3.
I still think mathematical induction should be invoked to justify that F is invariant after color changes. What do you think?

 

[luckyslevin]

Hi all, may be I am wrong, but if we combine 2 G and 2 P we have after this operation: 15B 13G and 15 P, now combine 15B and 15P and we have all G. May be I am wrong.

 

[Liam]

The above responses seem a bit muddled.

Look at the 3 possible moves at each stage - combining Blue and Purple (call this move BP), combining Blue and Green (call this move BG), combining Green and Purple (call this move GP).

After \(a\) BP moves, \(b\) BG moves and \(c\) GP moves the state is
\(13-a-b+2c\) Blue, \(15-a-c+2b\) Green and \(17-b-c+2a\) Purple
irrespective of the order of the moves.

We can solve for \(a\), \(b\) and \(c\) so that the end state is 15B 15P 15G. We are talking about existence of a solution and hence just need to check the determinant of the matrix of the set of equations, which is \(0\). Given that the rhs of the set of equations is not zero, a solution does not exist.

This approach is slightly computation heavy, especially for an interview, so a better way that is less prone to screwing up (and more elegant) would be to note that the set of simultaneous equations is the exact same set you get when starting with the state 0B 2P 4G, the only difference being that 13 is added to both sides.

Hence a solution exists to the original problem if and only if a solution exists to the problem of transforming the state 0B 2P 4G into the state 2B 2P 2G.

It's much easier to see, using a decision tree, that the state 0B 2P 4G can never become 2B 2P 2G as the only states you ever get are 0B 2P 4G, 2B 1P 3G, 1B 0P 5G and variants of those states where the labels B, P, G are permuted.

 

[Victor Tse]

The key is just to find an invariant in the process, let's denote green be 0, blue be 1, purple be 2, then invariant is the summation mod(3). Initial state, the sum is 1*13+0*15+2*17 =2 mod(3). However, assume all cats be the same color, the sum is 0 mod(3), so impossible.