[email protected] wrote:classroom consists of a 5 X 5 array of desks, to be filled by anywhere from 0 to 25 students, inclusive. No student will sit at a desk unless either all other desks in its row or all others in its column are filled (or both).
Considering only the set of desks that are occupied (and not which student sits at each desk), how many possible arrangements are there?
(a) 624 (b) 625 (c) 961 (d) 962 (e) none of these
I am unable to solve this question...Please help!!!
Tricky question (perhaps too tricky to be an actual GMAT question).
To set this up, let's consider the classroom as a 5x5 chessboard.
We have 5 rows, which we'll label as row#1, row#2, row#3, row#4 and row#5.
And we have 5 columns, which we'll label as column#1, column#2, column#3, column#4 and column#5.
We can now think of each possible arrangement as selecting possible rows and columns to fill up with students.
Now, for any counting question, it's often a good idea to list some possible outcomes. Doing so may help us identify the best way to approach the solution.
- One possible outcome is: row#3 (that is, seat 5 students in this row)
- Another possible outcome is: column#1 and column#4 (seat 10 students in these two columns)
- Another possible outcome is: row#3 and column#5 (seat 9 students: 5 in row#3 and 4 more in column#5)
- Another possible outcome is: row#2, row#4 and column#1 (seat 13 students accordingly)
Important: Notice that something "bad" happens if we select all 5 rows or all 5 columns.
For example, the outcome row#1, row#2, row#3, row#4, row#5, column#2 is the same as the outcome row#1, row#2, row#3, row#4, row#5, column#3, since in both cases we are filling all 5 rows, in which case the entire chessboard is already covered. At that point, it doesn't make any difference whether we've selected any columns.
So, in our solution, we'll say that
we won't select all 5 rows or all 5 columns. We'll deal with this at the very end.
Okay, at this point, we can take the task of seating students and break it into stages:
Stage 1: Determine which rows to fill.
Stage 2: Determine which columns to fill
Stage 1: We can select 0 rows, 1 row, 2 rows, 3 rows or 4 rows to fill.
We can select 0 rows in 5C0 ways (1 way)
We can select 1 row in 5C1 ways (5 ways)
We can select 2 rows in 5C2 ways (10 ways)
We can select 3 rows in 5C3 ways (10 ways)
We can select 4 rows in 5C4 ways (5 ways)
So, the total number of ways to accomplish stage 1 = 1+5+10+10+5 = 31
Stage 2: We can select 0 columns, 1 column, 2 columns, 3 columns or 4 columns to fill.
We can select 0 columns in 5C0 ways (1 way)
We can select 1 columns in 5C1 ways (5 ways)
We can select 2 columns in 5C2 ways (10 ways)
We can select 3 columns in 5C3 ways (10 ways)
We can select 4 columns in 5C4 ways (5 ways)
So, the total number of ways to accomplish stage 2 = 1+5+10+10+5 = 31
This means that the total number of ways to accomplish both stages = 31x31=961
At this point, we need to deal with the case where all 5 rows or all 5 columns are filled.
In other words, we need to deal with the case where all 25 seats are filled.
Well, there's only 1 way to fill all 25 seats.
So, the total number of arrangements = [spoiler]961 + 1 = 962 = D[/spoiler]
Aside: This includes the arrangement where there are no students seated.
Cheers,
Brent
