There are 25 "ones" arranged in a 5*5 matrix.
You are requested to erase n ones leaving a matrix in which the quantities of "ones" in each column and each row are divisible by 3.
How many distinct solutions are there, provided you do not erase the "one" in the upper left corner?
Every row (also each column) must contain either zero or three 1's. Since the first row and the first column are each populated, they must have 3 1's each.
In the first row, there are C(4,2) = 6 ways of choosing the other two columns in which 1's appear. Similarly, for the first column there are C(4,2) = 6 ways of choosing the other two rows in which 1's appear.
Once a row or column has a 1, it must have three of them. The only way of doing this is by having 1's remain at the intersection of the chosen columns of the first row and the rows of the first column; other arrangements would force columns or rows to occur in which only two 1's appear, or force the first row or column to have more than three 1's.
So the answer is 6*6 = 36 distinct solutions for the placement of the nine non-erased 1's.
|
|
Posted by Charlie
on 2016-02-18 10:55:02 |
solution
