- #1
annpaulveal
- 15
- 0
Homework Statement
Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove there is a row and a column such that when the total of the entries in the row and column are added, their sum is greater than 13.
The Attempt at a Solution
I considered a selection of one row and one column, which contains 16 boxes. Given the size of the matrix, there are 4 such selections of unique boxes, or 4 pigeonholes. If the sum of each such pigeonhole was <= 12, the sum of A would be 48 at a maximum. Therefore, the sum of at least one such pigeonhole must be greater than 13 to reach the sum of 51.
However, I'm not sure if my solution is sufficient to account for the single overlapping box between a row and a column at every selection of one row and one column. Also, the fact that there are 64 unique boxes and therefore 4 unique selections of 16 does not account for the fact that the problem is specifically asking for rows and columns, which intersect in the way I just described.
Last edited: