Maths Olympiad Prep

Library / /686 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

In how many ways can 6 purple balls and 6 green balls be placed into a 4×44 \times 4 grid of boxes such that every row and column contains two balls of one color and one ball of the other color? Only one ball may be placed in each box, and rotations and reflections of a single configuration are considered different.

A number or a short expression. Spacing and $ signs are ignored.

Solution

In each row or column, exactly one box is left empty. There are 4!=244!=24 ways to choose the empty spots. Once that has been done, there are 6 ways to choose which two rows have 2 purple balls each. Now, assume without loss of generality that boxes (1,1)(1,1), (2,2),(3,3)(2,2),(3,3), and (4,4)(4,4) are the empty ones, and that rows 1 and 2 have two purple balls each. Let A,B,CA, B, C, and DD denote the 2×22 \times 2 squares in the top left, top right, bottom left, and bottom right corners, respectively (so AA is formed by the first two rows and first two columns, etc.). Let a,b,ca, b, c, and dd denote the number of purple balls in A,B,CA, B, C, and DD, respectively. Then 0a,d2,a+b=40 \leq a, d \leq 2, a+b=4, and b+d4b+d \leq 4, so ada \geq d. Now suppose we are given the numbers aa and dd, satisfying 0da20 \leq d \leq a \leq 2. Fortunately, the numbers of ways to color the balls in A,B,CA, B, C, and DD are independent of each other. For example, given a=1a=1 and d=0d=0, there are 2 ways to color AA and 1 way to color DD and, no matter how the coloring of AA is done, there are always 2 ways to color BB and 3 ways to color CC. The numbers of ways to choose the colors of all the balls is as follows: a\d01201(12)1=20012(23)1=122(11)2=4021(22)1=41(32)2=121(21)1=2\begin{array}{c|c|c|c} a \backslash d & 0 & 1 & 2 \\ \hline 0 & 1 \cdot(1 \cdot 2) \cdot 1=2 & 0 & 0 \\ \hline 1 & 2 \cdot(2 \cdot 3) \cdot 1=12 & 2 \cdot(1 \cdot 1) \cdot 2=4 & 0 \\ \hline 2 & 1 \cdot(2 \cdot 2) \cdot 1=4 & 1 \cdot(3 \cdot 2) \cdot 2=12 & 1 \cdot(2 \cdot 1) \cdot 1=2 \end{array} In each square above, the four factors are the number of ways of arranging the balls in AA, B,CB, C, and DD, respectively. Summing this over all pairs (a,d)(a, d) satisfying 0da20 \leq d \leq a \leq 2 gives a total of 36. The answer is therefore 24636=518424 \cdot 6 \cdot 36=5184.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.