Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(deleted old partial solution and wrote new one)
m (fixed 6\choose3 LaTeX error in my solution)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
  
−
Consider the first column.  There are <math>\binom{6}{3} = 20</math> ways that the balls could be chosen, but WLOG let them be the first three rows.  (So change the order of the rows to make this true.)  We will multiply whatever answer we get by 20 to get an answer.
+
Consider the first column.  There are <math>{6\choose3} = 20</math> ways that the balls could be chosen, but WLOG 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:
 
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:
Line 13: Line 13:
  
 
*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.
 
*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.
−
[[Casework]] shows that:
 
  
 
So there are <math>20(3+54+36) = 1860</math> different shadings, and the solution is '''860'''.
 
So there are <math>20(3+54+36) = 1860</math> different shadings, and the solution is '''860'''.

Revision as of 22:43, 14 March 2007

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

Consider the first column. There are ${6\choose3} = 20$ ways that the balls could be chosen, but WLOG 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.

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_I_Problems/Problem_10&oldid=14021"