Bodyguards in a Territory

Probability Level 5

Four letters, two "a" and two "b" are filled into 16 cells of a matrix as given in the above figure. It is required each cell contains at most one letter and each row or column cannot contain same letters. In how many ways can the matrix be filled?

The answer is 3960.

5 solutions

Andy Hayes
Mar 5, 2015

There are 16 ways to place the 1st a. There are 9 ways to place the 2nd a.

There are 2 ways to place the 1st b in which it is in the same row or column of both a's. There are 9 ways to place the 2nd b if this is the case.

There are 8 ways to place the 1st b in which it is in the same row or column of one of the a's. There are 8 ways to place the 2nd b if this is the case.

There are 4 ways to place the 1st b in which it is in not in the same row or column of either of the a's. There are 7 ways to place the 2nd b if this is the case.

Thus, there are $16\times 9\times \left( 2\times 9+8\times 8+4\times 7 \right) =15840$ ways to place the a's and b's in this order . Since we don't care about the order, we divide by the number of permutations of a and b to get the final answer: $15840\div 4=3960$ .

I solved the question right, but I am not able to post solution!!!!

Observe this: The given conditions are satisfied when a pair of identical letters occupy diagonally opposite ends of a rectangle(square or rectangle) formed by squares of the grid.

First we arrange the 'a's. There are $36$ rectangles. And each rectangle has $2$ pairs of diagonally opposite squares, hence number of ways of arranging 'a's is $36*2=72$ .

Now for 'b's. Since we have already placed the 'a's, some of the rectangles have one of their corners occupied by these 'a's. There are 17 of these. In these 17 rectangles, only one pair of opposite corners is available. The rest 19 have both pairs available. hence, the number of ways of arranging 'b's is $(17+19*2)=55$

Therefore, final answer is $72*55=\boxed{3960}$

Raghav Vaidyanathan - 6 years, 3 months ago

Sorry, I did not properly update the answers previously. Can you post your solution now?

Calvin Lin Staff - 6 years, 3 months ago

No, I cannot.

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – Hm, can you email me a screenshot of what the top of this page looks like for you? Thanks. You can reach me at calvin@brilliant.org

Calvin Lin Staff - 6 years, 3 months ago

Aryan Goyat
Jan 7, 2016

Igmut Schnoll
Sep 3, 2015

I placed the two a's in 16x9/2 ways. Then I independently placed the two b's in 16x9/2 ways. This gives (16x9/2)^2 = 5184 placements of two a's and two b's, but it has overlaps of a's and b's. So we must subtract the overlaps. The number of placements with precisely two a-b overlaps is just 16x9/2 = 72. It's the same as if we just placed two a's. The number of configurations with precisely one a-b overlap is trickier. There are 72 placements of two a's. For each of these, we can choose an a in 2 ways. Place one b on that a. There will then remain 8 places that you can place the second b. That gives 72x2x8 = 1152 cases with precisely one a-b overlap. The answer to the problem is then 5184 - 1152 - 72 = 3960.

This is about how I solved it, except I imagined that for any given placement of A's, there is exactly 1 way to place the B's both overlapping, and exactly 8 ways to place the B's when the first overlaps, and 8 ways to place the B's when the second overlaps. So I subtracted 17 16 9 which is the same as 1152+72.

M M - 4 years, 4 months ago

Satvik Choudhary
May 27, 2015

First we can place the As and Bs separately and then subtract the cases when one of the Bs coincides with one of the As and also subtract the case when both the As coincide with the Bs.

Lam Nguyen
May 12, 2015

there are 16 9/2 = 72 ways to place 2 a same for b thus there are 72^2 ways (ignoring the individual cell condition) to fill there are 16 9 8 ways which will result in exactly 1 cell with both a and b, and 72 ways that there are 2 cells with both a and b thus 72^2 - 16 9*8 - 72 = 3960

Bodyguards in a Territory

The answer is 3960.

5 solutions

0 pending reports