@Sandeep: there are 45 chameleons, not 44.
If blue and green meet first, there will be 15 red, not 14.
You can find all of the possible combinations very quickly using a
46x46 table. Start with all cells set to false except for the first
(13,15). If you know the red and green count, you can deduce blue.
Now loop over all the cells. For any which is set to possible, look at
all combinations which can be reached from there by one meeting. If
any are not set to possible, set them to possible.
Repeat until one pass finds no new possible cells. You will find 360
possible states, and none of them have 45 of any one color. Code
follows.
Don
int main(int argc, char* argv[])
{
int r,g,b;
int possible[46][46] = {{0}};
possible[13][15] = 1;
int prevPossible, numPossible = 1;
do
{
prevPossible = numPossible;
for(r = 0; r < 46; ++r)
for(g = 0; g < 46; ++g)
{
b = 45-r-g;
if (b < 0) break;
if (possible[r][g])
{
if (r && g && !possible[r-1][g-1])
{
possible[r-1][g-1] = 1;
++numPossible;
}
if (r && b && !possible[r-1][g+2])
{
possible[r-1][g+2] = 1;
++numPossible;
}
if (g && b && !possible[r+2][g-1])
{
possible[r+2][g-1] = 1;
++numPossible;
}
}
}
} while(numPossible > prevPossible);
printf("%d positions are possible\n", numPossible);
if (possible[45][0]) printf("45 red is possible\n");
if (possible[0][45]) printf("45 green is possible\n");
if (possible[0][0]) printf("45 blue is possible\n");
return 0;
}
On Sep 6, 11:13 am, sandeep gupta <sandeepgupta...@gmail.com> wrote:
> let the blue and green chameleon meet first.
> Result :
> 14 - red
> 14 - green
> 16 - blue
> now 14 times pair of red and green meet to make it all 44 blue
>
> On Sep 5, 11:44 pm, Don <dondod...@gmail.com> wrote:
>
> > Yes, you are right, it is 4 in that case. It seems that f is always
> > even. It is possible for 44 chameleons to be one color, but then there
> > is only one left and it cannot change to that color. Any time there
> > are 43 chameleons of one color, the other two are the same color.
> > It is true that all the chameleons can never be the same color, but I
> > agree that his "proof" is not valid.
> > Don
>
> > On Sep 5, 9:08 pm, wujin chen <wujinchen...@gmail.com> wrote:
>
> > > hi Don, i think f(15,14,16) =|15-14|+|14-16|+|16-15| = 1+2+1=4, hou do you
> > > get f(15,14,16) = 5?
>
> > > 2011/9/6 Don <dondod...@gmail.com>
>
> > > > No, f(15,14,16) = 5.
> > > > Don
>
> > > > On Sep 5, 8:33 pm, wujin chen <wujinchen...@gmail.com> wrote:
> > > > > hi all, i encountered this puzzle
> > > > > (http://www.crackpuzzles.com/?p=236):
>
> > > > > At one point, a remote island's population of chameleons was divided
> > > > > as
> > > > > follows:
> > > > > - 13 red chameleons
> > > > > - 15 green chameleons
> > > > > - 17 blue chameleons
> > > > > Each time two different colored chameleons would meet, they would
> > > > > change
> > > > > their color to the third one. (i.e.. If green meets red, they both
> > > > > change
> > > > > their color to blue.) Is it ever possible for all chameleons to become
> > > > the
> > > > > same color? Why or why not?"
>
> > > > > and the solution provided by auther is like this:
> > > > > *Solution: *
> > > > > Lets define a function f(red, blue, green) = |red - blue| + |blue -
> > > > green| +
> > > > > |green - red|
> > > > > When two chameleons of different colours meet and convert to the third
> > > > one,
> > > > > the value of function f will always change by 0 or 3 or 6 (i.e. a
> > > > multiple
> > > > > of 3). In the initial situation f is 8.
> > > > > If all of them get converted into a single colour then f would be 90 =
> > > > > 2*(red+blue+green)
> > > > > So we are basically looking for a solution to the equation: 8 + 3x =
> > > > > 90,
> > > > > which has no integer solutions. Hence it is not possible.
>
> > > > > well, my problem is this:
>
> > > > > f(13,15,17)=8,
> > > > > f(15,14,16)=2
> > > > > so , we can see that " the value of function f will always change by
> > > > > 0 or
> > > > 3
> > > > > or 6″ is not true, i am wondering~！
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > > > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
>
> > - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
