w******i
发帖数: 503 | 1 on page 26, how to prove that if combination of (m+1, n+1, p+1)
can be converted to the same color, combination (m,n,p) can be converted
to the same color as well?
Here is the original problem:
A remote island has three types of chameleons with the following
population:
13 red, 15 green and 17 blue. Each time two chameleons with different
colors meet, they both change their colors to the third color. For
example, if a green chameleon meets a red one, they both change their
colors to blue. is it ever possible for all chameleons to become
the same color? why or why not?
Thanks for your help. | f**********i
发帖数: 45 | 2 倒了吧？应该是如果m,n,p能变成同一种颜色，那么在加入三种各一个的话把另两种颜
色变作同一种就可以了。
【在 w******i 的大作中提到】
: on page 26, how to prove that if combination of (m+1, n+1, p+1)
: can be converted to the same color, combination (m,n,p) can be converted
: to the same color as well?
: Here is the original problem:
: A remote island has three types of chameleons with the following
: population:
: 13 red, 15 green and 17 blue. Each time two chameleons with different
: colors meet, they both change their colors to the third color. For
: example, if a green chameleon meets a red one, they both change their
: colors to blue. is it ever possible for all chameleons to become
| w******i
发帖数: 503 | 3 no. it is the original statement that is needed in the following argument.
【在 f**********i 的大作中提到】
: 倒了吧？应该是如果m,n,p能变成同一种颜色，那么在加入三种各一个的话把另两种颜
: 色变作同一种就可以了。
| r****t
发帖数: 10904 | 4 for（m+1, n+1, p+1), apply (m,n,p) conversion.
WLOG, assume (m,n,p) -> (0,0,p+x),
so (m+1, n+1, p+1) -> (1,1,p+1+m+n) ->(use the rule again) (0,0,p+1+m+n+2)
证反了。。。
【在 w******i 的大作中提到】
: on page 26, how to prove that if combination of (m+1, n+1, p+1)
: can be converted to the same color, combination (m,n,p) can be converted
: to the same color as well?
: Here is the original problem:
: A remote island has three types of chameleons with the following
: population:
: 13 red, 15 green and 17 blue. Each time two chameleons with different
: colors meet, they both change their colors to the third color. For
: example, if a green chameleon meets a red one, they both change their
: colors to blue. is it ever possible for all chameleons to become
| w******i
发帖数: 503 | 5 yes, 证反了。。。
【在 r****t 的大作中提到】
: for（m+1, n+1, p+1), apply (m,n,p) conversion.
: WLOG, assume (m,n,p) -> (0,0,p+x),
: so (m+1, n+1, p+1) -> (1,1,p+1+m+n) ->(use the rule again) (0,0,p+1+m+n+2)
: 证反了。。。
| s**********r
发帖数: 8153 | | w******i
发帖数: 503 | 7 Ding. There are many smart people on this forum. Could
someone please help? thanks. | f**********i
发帖数: 45 | 8 I think that approach may simply be inaccurate. Ultimately you need a
conserved quantity.
【在 w******i 的大作中提到】
: Ding. There are many smart people on this forum. Could
: someone please help? thanks.
| w******i
发帖数: 503 | 9 thanks for your reply. conservation is the essence of the second approach,
which seems more intuitive to me. but i cannot reject the first
approach without a proof.
【在 f**********i 的大作中提到】
: I think that approach may simply be inaccurate. Ultimately you need a
: conserved quantity.
| x*****t
发帖数: 353 | 10 if (r,g,b)=(m+1,n+1,p+1) can be converted to the same color.
it will be (0,0,m+n+p+3), but you do not know which color is left.
It could be (r,g,b) = (0,0,m+n+p+3)
OR it could be (r,g,b) = (0,m+n+p+3,0)
OR it could be (r,g,b) = (m+n+p+3,0,0)
if it is the first case, then (m+1,n+1,p+1) can be converted to the same
color means (m,n,p+x) can also be converted to the same color, where x can
be any #.
if it is the second case, then (m,n+x,p) can be converted to the same color.
if it is the third case, then (m+x,n,p) can be converted to the same color.
no matter which case it is, set x = 0, you will see that (m,n,p) common for
all three cases.
【在 w******i 的大作中提到】
: on page 26, how to prove that if combination of (m+1, n+1, p+1)
: can be converted to the same color, combination (m,n,p) can be converted
: to the same color as well?
: Here is the original problem:
: A remote island has three types of chameleons with the following
: population:
: 13 red, 15 green and 17 blue. Each time two chameleons with different
: colors meet, they both change their colors to the third color. For
: example, if a green chameleon meets a red one, they both change their
: colors to blue. is it ever possible for all chameleons to become
| | | f**********i
发帖数: 45 | 11 I don't think the argument is rigorous enough. In fact it has secretly used
the statement it wants to prove between the lines.
color.
【在 x*****t 的大作中提到】
: if (r,g,b)=(m+1,n+1,p+1) can be converted to the same color.
: it will be (0,0,m+n+p+3), but you do not know which color is left.
: It could be (r,g,b) = (0,0,m+n+p+3)
: OR it could be (r,g,b) = (0,m+n+p+3,0)
: OR it could be (r,g,b) = (m+n+p+3,0,0)
: if it is the first case, then (m+1,n+1,p+1) can be converted to the same
: color means (m,n,p+x) can also be converted to the same color, where x can
: be any #.
: if it is the second case, then (m,n+x,p) can be converted to the same color.
: if it is the third case, then (m+x,n,p) can be converted to the same color.
| x*****t
发帖数: 353 | 12 i do not understand your 2nd sentence. can you be clear? thanks
used
【在 f**********i 的大作中提到】
: I don't think the argument is rigorous enough. In fact it has secretly used
: the statement it wants to prove between the lines.
:
: color.
| w******i
发帖数: 503 | 13 Thanks. I think the following line of proof is not clear:
if it is the first case, then (m+1,n+1,p+1) can be converted to the same
color means (m,n,p+x) can also be converted to the same color, where x can
be any #.
【在 x*****t 的大作中提到】
: i do not understand your 2nd sentence. can you be clear? thanks
:
: used
| x*****t
发帖数: 353 | 14 if (r,g,b) = (m+1,n+1,p+1) goes to (r,g,b) = (0,0,m+n+p+3)
then before the last step, it must be (r,g,b) = (1,1,m+n+p+1)
if you start from (r,g,b)=(m,n,p+1), use the same method as you do from (m+1
,n+1,p+1) to (1,1,m+n+p+1), you will go from (m,n,p+1) to (0,0,m+n+p+1).
【在 w******i 的大作中提到】
: Thanks. I think the following line of proof is not clear:
: if it is the first case, then (m+1,n+1,p+1) can be converted to the same
: color means (m,n,p+x) can also be converted to the same color, where x can
: be any #.
| f**********i
发帖数: 45 | 15 This is still not granted. The extra chameleons may play some role in the
condition.
+1
【在 x*****t 的大作中提到】
: if (r,g,b) = (m+1,n+1,p+1) goes to (r,g,b) = (0,0,m+n+p+3)
: then before the last step, it must be (r,g,b) = (1,1,m+n+p+1)
: if you start from (r,g,b)=(m,n,p+1), use the same method as you do from (m+1
: ,n+1,p+1) to (1,1,m+n+p+1), you will go from (m,n,p+1) to (0,0,m+n+p+1).
| x*****t
发帖数: 353 | 16 this is just my understanding. can you give an example that the extra
chameleons play role? thanks
【在 f**********i 的大作中提到】
: This is still not granted. The extra chameleons may play some role in the
: condition.
:
: +1
| f**********i
发帖数: 45 | 17 For instance you can convert two red and two green into two blue but cannot
do that for one red and two green... You may argue this is not the case we
may consider, but it indicates a flaw if we want a proof.
【在 x*****t 的大作中提到】
: this is just my understanding. can you give an example that the extra
: chameleons play role? thanks
| f**********i
发帖数: 45 | 18 What is missing in the proof is that if A can be converted into B, then A-C
can be converted into B-C. It is obviously true for A+C, but for A-C it is
not guaranteed without a proof.
【在 x*****t 的大作中提到】
: this is just my understanding. can you give an example that the extra
: chameleons play role? thanks
| x*****t
发帖数: 353 | 19 I agree you can not do that for one red and two green.
But this example is not the same as we are talking about, because you do not
change the SAME number for both red and green.
if you change from (m+1,n+1) to (m,n), you change both by the same number.
This is the point.
another way i am think is, starting from (m,n,p), you can go to (m+2,n-1,p-1
), then to (m+1,n+1,p-2). This would be the same as (m+1,n+1,p+1) as long as
you kill the color associate with (m,n) at last.
if you are thinking p-2 is 3 less than p+1 (for B color). my understanding
is:
if you never run out of B color for p-2 case, it will be OK.
if at some point, B = 0, then at the same time R>0 AND G>0 must holds. then
you should let R meets G until R = 0 or G = 0, then you have some B balls.
cannot
【在 f**********i 的大作中提到】
: For instance you can convert two red and two green into two blue but cannot
: do that for one red and two green... You may argue this is not the case we
: may consider, but it indicates a flaw if we want a proof.
| x*****t
发帖数: 353 | 20 From approach 2 in the book, my conclusion is that (R,G,B) = (m,n,p) can go
to (R,G,B) = (0,0,m+n+p) if and only if m%3 = n%3
if m%3 = n%3
it follows that (m-1)%3 = (n-1)%3
not
-1
as
【在 x*****t 的大作中提到】
: I agree you can not do that for one red and two green.
: But this example is not the same as we are talking about, because you do not
: change the SAME number for both red and green.
: if you change from (m+1,n+1) to (m,n), you change both by the same number.
: This is the point.
: another way i am think is, starting from (m,n,p), you can go to (m+2,n-1,p-1
: ), then to (m+1,n+1,p-2). This would be the same as (m+1,n+1,p+1) as long as
: you kill the color associate with (m,n) at last.
: if you are thinking p-2 is 3 less than p+1 (for B color). my understanding
: is:
| j******n
发帖数: 271 | 21 Let R be the number of meetings between blue and green;
and G, B similar. It's trivial that
(1) r = delta of number of reds = 2R-G-B
(2) g = delta of number of greens = 2G-R-B
(3) b = delta of number of blues = 2B-G-R
Suppose the final state is "all red", then
g=-15, b=-17, and
g+2b = -34 mod 3 = 2 mod 3
But from (2) and (3) we have
g+2b = 3(G-R), which is a multiple of 3
So the final state cannot be "all red".
Similarly the final state cannot be "all blue", or "all green" as
-13 = -1 (mod 3)
-15 = 0 (mod 3)
-17 = 1 (mod 3)
and 2*a+b != 0 (mod 3), where a,b in (-1,0,1) and a!=b.
【在 w******i 的大作中提到】
: on page 26, how to prove that if combination of (m+1, n+1, p+1)
: can be converted to the same color, combination (m,n,p) can be converted
: to the same color as well?
: Here is the original problem:
: A remote island has three types of chameleons with the following
: population:
: 13 red, 15 green and 17 blue. Each time two chameleons with different
: colors meet, they both change their colors to the third color. For
: example, if a green chameleon meets a red one, they both change their
: colors to blue. is it ever possible for all chameleons to become
|
|
