## Permutation of Flags

For discussing Olympiad Level Combinatorics problems
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### Permutation of Flags

T20 World Cup 2014 is being held in Bangladesh.
Next to Mirpur stadium, there are \$24\$ flags standing in a row. The flags belong to \$9\$ different countries.
There are \$10\$ Australian flag. It's the highest number of flags a country has in that row.
The next highest number of flags that belong to the same country is \$4\$.
Pakistan and India have the same number of flags, but the number of flags each of them have is less than \$4\$.
How many permutations are possible for the flags?
(It is possible for a country to have \$0\$ flags)

Problem Setter: Saumitra da.
Learn how to write equations, and don't forget to read Forum Guide and Rules.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

Posts: 17
Joined: Thu Aug 29, 2013 6:33 pm
Location: Japan Garden City, Mohammadpur, Dhaka

### Re: Permutation of Flags

There are \(10\) Australian flag . So , \(14\) flags belong to \(8\) different countries . Since , at least one country has \(4\) flags , there are three cases :-

Case 1 : \(1\) country has \(4\) flags .
So, \(1\) country among \(6\) countries (excluding Pakistan and India )can have these \(4\) flags in \(6\) ways . Then , the other \(10\) flags belong to \(7\) countries (including Pakistan and India ) . Now applying stars and bars , we get the following cases :

Case 1.1 : Pakistan = India = \(0\) . Then, \(5\) countries have \(10\) flags . The number of ways are :

\( \displaystyle \binom{5 + 10 - 1}{10} = 1001\)

Case 1.2 : Pakistan = India = \(1\) . Then, \(5\) countries have \(8\) flags . The number of ways are :

\( \displaystyle \binom{5 + 8 - 1}{8} = 495\)

Case 1.3 : Pakistan = India = \(2\) . Then, \(5\) countries have \(6\) flags . The number of ways are :

\( \displaystyle \binom{5 + 6 - 1}{6} = 210\)

Case 1.4 : Pakistan = India = \(3\) . Then, \(5\) countries have \(4\) flags . The number of ways are :

\( \displaystyle \binom{5 + 4 - 1}{4} = 70\)

The number of permutation for this case is \( 6(1001 + 495 + 210 + 70) = 10656\) .

Case 2 : \(2\) countries have \(4\) flags each .
So, \(2\) countries among \(6\) countries (excluding Pakistan and India )can have these \(8\) flags in \( ^6P_2\) or \(30\) ways . Then , the other \(6\) flags belong to \(6\) countries (including Pakistan and India ) . Now applying stars and bars , we get the following cases :

Case 2.1 : Pakistan = India = \(0\) . Then, \(4\) countries have \(6\) flags . The number of ways are :

\( \displaystyle \binom{4 + 6 - 1}{6} = 84\)

Case 2.2 : Pakistan = India = \(1\) . Then, \(4\) countries have \(4\) flags . The number of ways are :

\( \displaystyle \binom{4 + 4 - 1}{4} = 35\)

Case 2.3 : Pakistan = India = \(2\) . Then, \(4\) countries have \(2\) flags . The number of ways are :

\( \displaystyle \binom{4 + 2 - 1}{2} = 10\)

Case 2.4 : Pakistan = India = \(3\) . Here's just \(1\) permutation in this case .

The number of permutation for this case is \( 30(84 +35 + 10 + 1) = 3900\) .

Case 3 : \(3\) countries have \(4\) flags each .
So , \(3\) countries among \(6\) countries can have these \(12\) flags in \( ^6P_3\) or \(120\) ways . So , the other \(2\) flags belong to \(5\) countries . Again applying stars and bars , we get the following cases :

Case 3.1 : Pakistan = India = \(0\) . Then, \(3\) countries have \(2\) flags . The number of ways are :

\( \displaystyle \binom{3 + 2 - 1}{2} = 6\)

Case 3.2 : Pakistan = India = \(1\) . Here's just \(1\) permutation in this case .

The number of permutation for this case would be \( 120(6 + 1) = 840\) .

Hence , the total number of possible permutation is \( 10656 + 3900 + 840 = 15396\) .
Last edited by sadman sakib on Sat Mar 29, 2014 7:12 pm, edited 1 time in total.

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### Re: Permutation of Flags

I think you got the problem wrong.
Australia has 10 flags. Another country has 4 flags. This country is neither India, nor Pakistan. It is the second highest.
The last 10 flags belong to the other 7 teams (which include India and Pakistan).
We are looking for the number of permutations possible.

I think the ans is a big number. You can change the number of second highest from 4 to 7.
Learn how to write equations, and don't forget to read Forum Guide and Rules.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

Posts: 17
Joined: Thu Aug 29, 2013 6:33 pm
Location: Japan Garden City, Mohammadpur, Dhaka

### Re: Permutation of Flags

The line of confusion is :
Labib wrote:The next highest number of flags that belong to the same country is \(4\)
'same' always means more than \(1\) ,doesn't it ?

From your post it seems that you wanted to say : The next highest number of flags that belong to at least \(1\) country is \(4\) .Those two statements are quite different .

I just edited the answer accordingly . I think this is the right answer .

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### Re: Permutation of Flags

Only one country has 4 flags.
I'll ask Saumitra da to check the solution. Learn how to write equations, and don't forget to read Forum Guide and Rules.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### Re: Permutation of Flags

Labib wrote:Only one country has 4 flags.
I'll ask Saumitra da to check the solution. Saumitra da says, more than one country can have 4 flags.
Try harder 