Difference between revisions of "2007 AIME I Problems/Problem 10"

Revision as of 19:54, 9 June 2019

Problem

In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let $N$ be the number of shadings with this property. Find the remainder when $N$ is divided by 1000.

Solution

Solution 1

Consider the first column. There are ${6\choose3} = 20$ ways that the rows could be chosen, but without loss of generality let them be the first three rows. (Change the order of the rows to make this true.) We will multiply whatever answer we get by 20 to get our final answer.

Now consider the 3x3 that is next to the 3 boxes we have filled in. We must put one ball in each row (since there must be 2 balls in each row and we've already put one in each). We split into three cases:

All three balls are in the same column. In this case, there are 3 choices for which column that is. From here, the bottom half of the board is fixed.

Two balls are in one column, and one is in the other. In this case, there are 3 ways to choose which column gets 2 balls and 2 ways to choose which one gets the other ball. Then, there are 3 ways to choose which row the lone ball is in. Now, what happens in the bottom half of the board? Well, the 3 boxes in the column with no balls in the top half must all be filled in, so there are no choices here. In the column with two balls already, we can choose any of the 3 boxes for the third ball. This forces the location for the last two balls. So we have $3 \cdot 2 \cdot 3 \cdot 3 = 54$ .

All three balls are in different columns. Then there are 3 ways to choose which row the ball in column 2 goes and 2 ways to choose where the ball in column 3 goes. (The location of the ball in column 4 is forced.) Again, we think about what happens in the bottom half of the board. There are 2 balls in each row and column now, so in the 3x3 where we still have choices, each row and column has one square that is not filled in. But there are 6 ways to do this. So in all there are 36 ways.

So there are $20(3+54+36) = 1860$ different shadings, and the solution is $860$ .

Solution 2

There are ${6\choose3}$ to choose the arrangement of the shaded squares in each column. Examine the positioning of the shaded squares in the first two columns:

One example of each case for the first two columns

If column 1 and column 2 do not share any two filled squares on the same row, then there are ${6\choose3}$ combinations for column 1, and then column 2 is fixed. Now, any row cannot have more than 2 shaded squares, so after we pick three more squares in the third column, the fourth column is also fixed. This gives ${6\choose3}^2 = 400$ arrangements.
If column 1 and column 2 share 1 filled square on the same row (6 places), then they each share 1 filled square on a row ( $6 - 1 = 5$ places), share another empty square on a row, and have 2 squares each on different rows. This gives $6 \cdot 5 \cdot {4\choose2} = 180$ . Now, the third and fourths columns must also share a fixed shared shaded square in the row in which the first two columns both had spaces, and another fixed empty square. The remaining shaded squares can only go in 4 places, so we get ${4\choose2} = 6$ . We get $180 \cdot 6 = 1080$ .
If column 1 and column 2 share 2 filled squares on the same row ( ${6\choose2} = 15$ places), they must also share 2 empty squares on the same row ( ${4\choose2} = 6$ ). The last two squares can be arranged in ${2\choose1} = 2$ positions; this totals to $15 \cdot 6 \cdot 2 = 180$ . Now, the third and fourth columns have a fixed 2 filled squares in common rows and 2 empty squares in common rows. The remaining 2 squares have ${2\choose1} = 2$ places, giving $180 \cdot 2 = 360$ .
If column 1 and column 2 share 3 filled squares on the same row ( ${6\choose3} = 20$ places), then the squares on columns 3 and 4 are fixed.

Thus, there are $400 + 1080 + 360 + 20 = 1860$ number of shadings, and the solution is $860$ .

Solution 3

We draw a bijection between walking from $(0,0,0,0)$ to $(3,3,3,3)$ as follows: if in the $i$ th row, the $j$ th and $k$ th columns are shaded, then the $(2i-1)$ st step is in the direction corresponding to $j$ , and the $(2i)$ th step is in the direction corresponding to $k$ ( $j < k$ ) here. We can now use the Principle of Inclusion-Exclusion based on the stipulation that $j!=k$ to solve the problem:

$\frac{1}{2^6}\left(\frac{12!}{3!^4}-4\cdot{6 \choose 1}\frac{10!}{3!^3}+4\cdot 3\cdot{6 \choose 2}\frac{8!}{3!^2}-4\cdot 3\cdot 2\cdot{6 \choose 3}\frac{6!}{3!}+4\cdot 3\cdot 2\cdot 1\cdot {6 \choose 4}4!\right) = 1860$

So that the answer is $860$ .

Solution 4

Solution 5

Consider all possible shadings for a single row. There are ${4 \choose 2}=6$ ways to do so, and denote these as $a=1+2$ , $b=3+4$ , $c=1+4$ , $d=2+3$ , $e=1+3$ , and $f=2+4$ where $x+y$ indicates that columns $x$ and $y$ are shaded. From our condition on the columns, we have $a+c+e=a+d+f=b+d+e=b+c+f=3$ Summing the first two and the last two equations, we have $2a+c+d+e+f=6=2b+c+d+e+f$ , from which we have $a=b$ . Likewise, $c=d$ and $e=f$ since these pairs shade in complimentary columns. So the six rows are paired up into a row and its compliment. In all, we can have 3 a's and 3 b's and similar setups for $c$ / $d$ and $e$ / $f$ , 2 a's, 2 b's, 1 c and 1 d and similar setups for all six arrangements, or one of each. This first case gives $3{6 \choose 3}=60$ solutions; the second gives $6\cdot 6\cdot5\cdot{4 \choose 2}=1080$ solutions, and the final case gives $6!=720$ solutions. In all, we have 1860 solutions, for an answer of $860$ .

Solution 6

Each shading can be brought, via row swapping operations, to a state with a $3\times2$ shaded $L$ in the lower left hand corner. The number of such arrangements multiplied by ${5 \choose 2}{3\choose 2}$ will be the total. Consider rows 2 and 3 up from the bottom: they each have one of their allotted two squares shaded. Depending how the remaining three shades are distributed, the column totals of columns 2,3, and 4 from the left can be of the form $\{3,0,0\},\{0,1,2\},\{1,1,1\}$ . Form 1: The entire lower left $3\times2$ rectangle is shaded, forcing the opposite $3\times2$ rectangle to also be shaded; thus 1 arrangement Form 2: There is a column with nothing shaded in the bottom right $3\times2$ , so it must be completely shaded in the upper right $3\times2$ . Now consider the upper right half column that will have $1$ shade. There are $3$ ways of choosing this shade, and all else is determined from here; thus 3 arrangements Form 3: The upper right $3\times3$ will have exactly $2$ shades per column and row. This is equivalent to the number of terms in a $3\times3$ determinant, or $6$ arrangements

Of the $3^2$ ways of choosing to complete the bottom half of the $4\times6$ , form 1 is achieved in exactly 1 way; form 2 is achieved in $3\times2$ ways; and form $3$ in the remaining $2$ ways. Thus, the weighted total is $1+6\times3+2\times6=31$ . Complete: $31\times60=860\mod{1000}$

Solution 7

Note that if we find a valid shading of the first 3 columns, the shading of the last column is determined. We also note that within the first 3 columns, there will be 3 rows with 1 shaded square and 3 rows with 2 shaded squares.

There are ${6 \choose 3}$ ways to choose which rows have 1 shaded square (which we'll call a "1-row") within the first 3 columns and which rows have 2 (we'll call these "2-rows") within the first 3 columns. Next, we do some casework:

If all of the shaded squares in the first column are in a 1-row, then the squares in the second and third columns must be in the 2-rows. Thus there is only ${3 \choose 3}{3 \choose 0} \times 1= 1$ valid shading in this case.

If 2 of the shaded squares in the first column are in a 1-row, and the third shaded square is in a 2-row, then the other shaded square in that 2-row can either be in column 3 or column 4. Once we determine that, the other shaded squares are uniquely determined. Thus, there are ${3 \choose 2}{3 \choose 1}\times 2=18$ valid shadings in this case.

If 1 shaded square in the first column is in a 1-row, and the other 2 are in 2-rows, then the 2-row without a shaded square in the first column must have shaded squares in both column 2 and column 3. This leaves 4 possible squares in the second column to be shaded (since there can't be another shaded square in the occupied 1-row). Thus, there are ${3 \choose 1}{3 \choose 2}\times {4 \choose 2}=54$ valid shadings in this case. (We only need to choose 2, since 1 of the shaded squares in the third column must go to the unoccupied 2-row).

If all of the shaded squares in the first column are in the 3 2-rows, then if we choose any 3 squares in the second column to be shaded, then the third column is uniquely determined to create a valid shading. Thus, there are ${3 \choose 0}{3 \choose 3}\times{6 \choose 3} = 20$ valid shadings in this case.

In total, we have ${6\choose3}(1+18+54+20)=20*93=1860$ . Thus our answer is $\boxed{860}$ .

Solution 8

We can use generating functions. Suppose that the variables $a$ , $b$ , $c$ , and $d$ represent shading a square that appears in the first, second, third, or fourth columns, respectively. Then if two squares in the row are shaded, then the row is represented by the generating function $ab+ac+ad+bc+bd+cd$ , which we can write as $P(a,b,c,d)=(ab+cd)+(a+b)(c+d)$ . Therefore, $P(a,b,c,d)^6$ represents all of the possible ways to color six rows such that each row has two shaded squares. We only want the possibilities when each column has three shaded squares, or rather, the coefficient of $a^3b^3c^3d^3$ in $P(a,b,c,d)^6$ .

By the Binomial Theorem, $P(a,b,c,d)^6=\sum_{k=0}^6 \binom{6}{k} (ab+cd)^k(a+b)^{6-k}(c+d)^{6-k}.\tag{1}$ If we expand $(ab+cd)^k$ , then the powers of $a$ and $b$ are always equal. Therefore, to obtain terms of the form $a^3b^3c^3d^3$ , the powers of $a$ and $b$ in $(a+b)^{6-k}$ must be equal. In particular, only the central term in the binomial expansion will contribute, and this implies that $k$ must be even. We can use the same logic for $c$ and $d$ . Therefore, the coefficient of $a^3b^3c^3d^3$ in the following expression is the same as the coefficient of $a^3b^3c^3d^3$ in (1). $\sum_{k=0}^3 \binom{6}{2k} (ab+cd)^{2k}(ab)^{3-k}(cd)^{3-k}\binom{6-2k}{3-k}^2.\tag{2}$ Now we notice that the only way to obtain terms of the form $a^3b^3c^3d^3$ is if we take the central term in the binomial expansion of $(ab+cd)^{2k}$ . Therefore, the terms that contribute to the coefficient of $a^3b^3c^3d^3$ in (2) are $\sum_{k=0}^3 \binom{6}{2k}\binom{2k}{k}\binom{6-2k}{3-k}^2(abcd)^3.$ This sum is $400+1080+360+20=1860$ so the answer is $\boxed{860}$ .

@@ Line 75: / Line 75: @@
 In total, we have <math>{6\choose3}(1+18+54+20)=20*93=1860</math>. Thus our answer is <math>\boxed{860}</math>.
-===Solution 7===
+===Solution 8===
 We can use generating functions. Suppose that the variables <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> represent shading a square that appears in the first, second, third, or fourth columns, respectively. Then if two squares in the row are shaded, then the row is represented by the generating function <math>ab+ac+ad+bc+bd+cd</math>, which we can write as <math>P(a,b,c,d)=(ab+cd)+(a+b)(c+d)</math>. Therefore, <math>P(a,b,c,d)^6</math> represents all of the possible ways to color six rows such that each row has two shaded squares. We only want the possibilities when each column has three shaded squares, or rather, the coefficient of <math>a^3b^3c^3d^3</math> in <math>P(a,b,c,d)^6</math>.

2007 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 9	Followed by Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search