6
$\begingroup$

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ 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 $N$ is divided by $1000$.

This is a tricky problem to be honest.

Let $|$ distinguish the two flagpoles.

I tried arranging it as:

$$G B GBGBGB | BGBGBGBGBGB$$

$$G G G GB | BGGGGGB$$

There are: $\binom{12}{3} = 220$ to arrange the blue/green. Then multiply by $11$ because of the divider of the poles.

$$= 220(11) = 2420$$

And this multiplication by $11$ takes care of the at least one flag on pole condition.

Then why is this the wrong answer?

$\endgroup$
1
  • $\begingroup$ When 0 blue is on a pole, only ${11\choose8} = {11\choose 3}$ arrangements are possible. See my answer for details. $\endgroup$ Jul 18, 2015 at 20:37

3 Answers 3

4
$\begingroup$

Here's a simple way to tackle the problem.

Blues on a flagpole can range from 0 to 10.
When 0 blue is on a flagpole (which means 1 green is there), there will be ${11\choose 8}$ ways to place the greens, else there will be ${12\choose 9}$ ways to place the greens.

Thus # of arrangements = $2\cdot{11\choose 8} + 9\cdot{12\choose 9}= 2310$

and remainder on dividing by 1000 = 310

$\endgroup$
6
  • $\begingroup$ but why are you multiplying by $2$ and $9$? $\endgroup$
    – Amad27
    Jul 18, 2015 at 20:58
  • $\begingroup$ There are 2 cases (0-10 and 10-0) where a pole has 0 blue and hence must have 1 green, with the remaining 8 greens placed in 11 gaps between blues (including ends). In the remaining 9 cases, 12 gaps are available for 9 greens. $\endgroup$ Jul 18, 2015 at 21:06
  • $\begingroup$ But what do you mean: "when 0 blue is on a flagpole there will be $\binom{11}{8}$ ways to place the greens?" I dont get this. How many spaces are on the flag pole? $\endgroup$
    – Amad27
    Jul 18, 2015 at 21:30
  • $\begingroup$ The question merely specifies a minimum of 1 flag on a pole, no maximum, so if pole 1 has 0 blue, 1 green, we have G || - B - B - B - B - B - B - B - B - B - B - i.e. 11 gaps between blues ( - ) any 8 of which the remaining greens can occupy. And ditto if it is pole 2 that has 0 blue, 1 green. $\endgroup$ Jul 19, 2015 at 2:36
  • $\begingroup$ but that doesnt use all 19 flags then. $\endgroup$
    – Amad27
    Jul 19, 2015 at 8:12
3
$\begingroup$

We don't change the number of arrangements if we stipulate that there are instead 12 blue flags and 9 green flags, and each flag must be topped with a blue flag. The reason is that we can go back and forth by adding/removing a blue flag from the the top of each flag pole.

Now the advantage of this change is that now every green flag is guaranteed to have a blue flag after it. So instead of 12 blue and 9 green, we have 3 blue and 9 [Green-Blue] chunks. So we can arrange these 12 symbols in any order, and then make a divide at any of the 11 gaps. This can be done in: $\binom{12}{3}\cdot 11$ ways. But we might have created an empty flagpole by isolating a blue flag on one end (and then removing it). This can be done in $\binom{11}{2}$ ways (on each side). So:

$$\binom{12}{3} \cdot 11 - 2 \cdot \binom{11}{2} = 2310$$

$\endgroup$
5
  • $\begingroup$ But the multiplication by $11$ takes care of the isolation though. $\endgroup$
    – Amad27
    Jul 18, 2015 at 17:53
  • $\begingroup$ ? why do you need the extra subtraction? $\endgroup$
    – Amad27
    Jul 18, 2015 at 18:55
  • $\begingroup$ At the beginning I added one blue flag to each pole, so at the end I have to take away one blue flag from each pole. So for instance, the arrangement B-B-GB-GB-GB-GB-GB-GB-GB-GB-GB | B actually corresponds to BBGBGBGBGBGBGBGBGBG | -. The second pole is empty. $\endgroup$
    – Alex Zorn
    Jul 18, 2015 at 20:47
  • $\begingroup$ Why did we add extra blue in the beginning though? $\endgroup$
    – Amad27
    Jul 18, 2015 at 20:58
  • $\begingroup$ To ensure that every green flag had a blue flag above it.. in retrospect this isn't the simplest way but it's the one that occurred to me first. $\endgroup$
    – Alex Zorn
    Jul 19, 2015 at 20:58
1
$\begingroup$

Another method would be to put one flagpole on top of the other. Then we have 10 blue flags and 9 green flags arranged in order, and there are two possibilities:

1) If the flags where the flagpoles meet are not both green, we have an arrangement where no 2 green flags are consecutive; so there are $\binom{11}{9}$ ways to choose the 9 gaps for the green flags (from the 11 gaps created by the blue flags), and then 18 choices for separating the flags to form the two flagpoles.

2) If the flags where the flagpoles meet are both green, then there are 11 ways to select the gap for these two flags and $\binom{10}{7}$ ways to choose the gaps for the 7 remaining green flags (from the 10 remaining gaps).

Therefore there are $\displaystyle 18\binom{11}{9}+11\binom{10}{7}=11(90+210)=2310$ such arrangements,

and the remainder when dividing by 1000 is 310.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .