Problem:
There are two distinguishable flagpoles, and there are flags, of which are identical blue flags, and are identical green flags. Let be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when is divided by .
Solution:
For convenience, label the flagpoles and , and denote by the number of flag arrangements in which flagpole has green flags. If either flagpole contains all the green flags, then it must also contain at least blue flags to act as separators. The flagpole with no green flags must therefore contain either or blue flags. Hence, , because there are possible positions in which to place blue flag on the flagpole with all the green flags (otherwise, the flagpole with no green flags contains blue flags). If , then a flagpole that has green flags must contain at least blue flags, and the other flagpole has green flags and must contain at least blue flags. Thus in any flag arrangement where each flagpole contains at least one green flag, of the blue flags have fixed positions relative to the green flags, and there are remaining blue flags that can be freely distributed. If flagpole has green flags, then there are possible positions in which blue flag can be placed on that flagpole, and there are possible positions in which blue flag can be placed on flagpole . Thus, for , after placing the green flags and of the blue flags, there remain blue flags with distinguishable locations. This is a standard problem of distributing indistinguishable objects among distinguishable bins. Because bins require separators to divide them, the problem is equivalent to choosing locations out of (the flags and the separators). Thus the number of ways to place the blue flags is . The desired number of flag arrangements is then
and the required remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions