1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeonhole Principle and Boolean Matrices

  1. May 6, 2013 #1
    1. The problem statement, all variables and given/known data

    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.

    3. 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: May 6, 2013
  2. jcsd
  3. May 6, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You did not give it, but I guess that it is 8x8.
    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?
     
  4. May 6, 2013 #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?
     
  5. May 6, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't think that makes it any easier. Just think through mfb's hint.
     
  6. May 7, 2013 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  7. May 7, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Hmm...
    Code (Text):
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Pigeonhole Principle and Boolean Matrices
  1. Pigeonhole principle (Replies: 12)

  2. Pigeonhole Principle (Replies: 1)

Loading...