2
$\begingroup$

I am to color four squares, 2 red and 2 blue, in a 5 x 5 grid such that squares of the same color do not lie in the same row or column. How many ways are there to do this?

I would like to know if my thought process is correct.
Step 1: Out of the 25 squares, we choose one to color it red. There are 25 ways to do this.

Step 2: We now proceed to color another square red. Since the column and the row of the previous square are unavailable for this purpose, we only have 25 - 9 = 16 squares to choose from. There are hence 16 ways to carry out this step.

Step 3: Now, we choose a square to color it blue. There are no restrictions, so we have 23 available squares i.e. 23 ways to carry out this step.

Step 4a: Suppose both red squares are situated in the union of the row and column of the blue square. Then, we have 16 squares to choose from to color the next blue square.

Step 4b: Suppose only one red square is situated in the union of the row and column of the blue square. Then, we only have 15 squares to choose from.

Step 4c: Suppose both red squares are not situated in the union of the row and column of the blue square. Then, we only have 14 squares to choose from.

Now, since steps 4a, 4b and 4c are independent cases, the number of ways to carry out step 4 is 16 + 15 + 14 = 45.

As the entire coloring process is a sequence of steps 1 to 4, the total number of ways to color 4 squares is 25 x 16 x 23 x 45 = 414000. Is this correct?

$\endgroup$
2
$\begingroup$

There are some problems with it. First, you’ve counted $25\cdot16$ ways to choose the red squares, but that counts each possibility twice, once for each possible order of choosing the two squares. You’ve counted ordered pairs of red squares; to get unordered pairs, you have to divide by $2$, getting $\frac12\cdot25\cdot16$.

You’ve made the same mistake in counting the ways to choose the blue squares, but you’ve also made a more significant one: you cannot add the results of steps 4a, 4b, and 4c. Case 4a, for instance, arises only when the first blue square is in one of two specific positions relative to the red squares, so this case actually accounts for only $2\cdot16$ ordered pairs of choices of blue squares. Similarly, case 4b arises only when the first blue square is in one of $12$ positions, so this case accounts for another $12\cdot15$ ordered pairs of blue squares. Finally, case 4c arises when the first blue square is in one of $9$ positions relative to the red squares, so it gives rise to $9\cdot14$ ordered pairs of blue squares. The total number of ordered pairs of blue squares is therefore

$$2\cdot16+12\cdot15+9\cdot14\;,$$

and there $$\frac12\left(2\cdot16+12\cdot15+9\cdot14\right)$$ unordered pairs.

Now you can finish up by multiplying the number of unordered pairs of red squares by the number of unordered pairs of blue squares.

$\endgroup$
  • $\begingroup$ I see what you mean by having to divide by two as I only want to consider unordered pairs. However, I don't quite understand what you mean when you refer to the 12 positions and the 9 positions in case 4b and 4c respectively. Aren't there 15 positions in case 4b? Because if I void the entire row and column of the first blue square, and consider that in the remaining 16 squares, one of them is a red squuare, then I only have 15 squares to choose from? $\endgroup$ – Vizuna Nov 9 '14 at 11:18
  • 1
    $\begingroup$ @Vizuna: The $2$, $12$, and $9$ are the numbers of positions of the first blue square that fall into cases 4a, 4b, and 4c, respectively. In each case you correctly counted the number of possible positions for the second blue square, but you overlooked the fact that the count was possible for only some positions of the first blue square. $\endgroup$ – Brian M. Scott Nov 9 '14 at 11:20
  • $\begingroup$ I see what you mean now! I had to draw out the grid to see that it was indeed 12 positions and 9 positions for the first blue square in case 4b and 4c respectively. (I'm really bad at visualizing stuff.) Thanks for your help! Do you know if there's a simpler way to approach this problem? $\endgroup$ – Vizuna Nov 9 '14 at 11:32
  • $\begingroup$ @Vizuna: You’re welcome! I thought just a little about alternative approaches and didn’t immediately see anything a lot better. You could try starting with $200\cdot200$ ways to choose two acceptable unordered pairs and then subtracting the ones in which the pairs ‘collide’; I’ve not actually gone through it, but I don’t think that it’s any simpler in the end. $\endgroup$ – Brian M. Scott Nov 9 '14 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.