문제

The magician Meg is a little puzzled. She has three white rabbits, two black rabbits and one green rabbit. She wants them in a nice line where two rabbits of the same colour never are directly beside each other. How many such lines exist. You may assume that rabbits of the same colour are identical.

도움이 되었습니까?

해결책

I will denote by W, W, W, B, B and G the rabbits of each color.

Note first that, at most, you will have binomial(6, 3)×binomial(3, 2)×binomial(1, 1) = 60 such alignments. As this is not a so large number, and as the constraint of "not two rabbits of the same color side-by-side" is pretty strong (as half of your rabbits already share the exact same color!), let's try to enumerate all such correct lines.

First you have the lines where you have White rabbit at one and only one edge of the line. This means the line must look like (assuming the White rabbit starts the line) W _ W _ W _, and that's it. Now you can fill as you wish the empty spots _ with the remaining rabbits, and the constraint will be satisfied for all of the colors. You have 3 different ways of filling the empty spots, hence 3 of such alignments. By symmetry, the White rabbit could end the line instead of starting it (ans such aligments are exclusives), hence 3 more alignments.

Now, note that you can't have a line whith no White rabbits neither at the beginning nor the end of the line (as you would be forced to place two White rabbits close by in the middle of the line).

The last case is if you have a White rabbit starting and ending the line. One more once, by symmetry, the line will look like W _ W _ _ W. You have to fill the empty spaces with the Black and Green rabbit, with the constraint that the two Black rabbits must not be in the middle _ _ position. You have only 2 of such fillings. By symmetry, you have 2 more of those alignments (with W _ _ W _ W).

Altogether, you have only 10 possible alignments (out of the 60 possibles of them without any constraint).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top