Pigeonhole Principle and Boolean Matrices

  • #1

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:

Answers and Replies

  • #2
35,651
12,217
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?
 
  • #3
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?
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
619
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.
 
  • #5
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,955
7,199
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.
 
  • #6
35,651
12,217
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...
Code:
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?
 

Related Threads on Pigeonhole Principle and Boolean Matrices

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
12
Views
11K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
831
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
17
Views
8K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
3
Views
1K
Replies
2
Views
3K
Top