Permutation of Flags

For discussing Olympiad Level Combinatorics problems
User avatar
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Location: Dhaka, Bangladesh.

Permutation of Flags

Unread post by Labib » Wed Mar 26, 2014 6:17 pm

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.
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
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

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

Re: Permutation of Flags

Unread post by sadman sakib » Fri Mar 28, 2014 12:53 pm

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.

User avatar
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Location: Dhaka, Bangladesh.

Re: Permutation of Flags

Unread post by Labib » Fri Mar 28, 2014 11:35 pm

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.
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
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

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

Re: Permutation of Flags

Unread post by sadman sakib » Sat Mar 29, 2014 7:14 pm

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 .

User avatar
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Location: Dhaka, Bangladesh.

Re: Permutation of Flags

Unread post by Labib » Sat Mar 29, 2014 9:47 pm

Only one country has 4 flags.
I'll ask Saumitra da to check the solution. :)
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
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

User avatar
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Location: Dhaka, Bangladesh.

Re: Permutation of Flags

Unread post by Labib » Mon Apr 07, 2014 10:19 am

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.
sadman sakib wrote:
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\) .
Saumitra da says, even according the given statement, the logics you used in some cases were wrong.
Try harder :)
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
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

Post Reply