Pigeonhole Principle and Boolean Matrices

[annpaulveal]

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.

 

[mfb]

Given the size of the matrix

You did not give it, but I guess that it is 8x8.

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.

I think you cannot fix that problem in your approach, so a different approach is needed.

Can you show that there is at least one row with 7 entries? What would happen if all rows had at most 6 entries?
Can you do the same with columns? How many columns have to have 7 entries?

 

[annpaulveal]

Would a better solution be to say that the sum of 51 in a 64-square Boolean matrix implies there are are 13 0s to be placed, and they can't be placed in such a way that each row/column combination adds up to 13 or less?

 

[Dick]

Would a better solution be to say that the sum of 51 in a 64-square Boolean matrix implies there are are 13 0s to be placed, and they can't be placed in such a way that each row/column combination adds up to 13 or less?

I don't think that makes it any easier. Just think through mfb's hint.

 

[haruspex]

when the total of the entries in the row and column are added, their sum is greater than 13.

If I read that strictly, an entry that is in both that row and that column should only be counted once. OTOH, I don't think the result is true in that case.

 

[mfb]

If I read that strictly, an entry that is in both that row and that column should only be counted once. OTOH, I don't think the result is true in that case.

Hmm...

0	0	1	1	1	1	1	1
1	0	1	1	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	0	1	1	1	1
1	1	1	1	0	0	1	1
1	1	1	1	1	0	1	1
1	1	1	1	1	1	0	0
0	1	1	1	1	1	1	0

On the other hand, if that entry is counted twice, where is the point in this matrix?