1

"Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove that there is a row and a column such that when the total entries of the row and column are added, the sum is greater than 13."

  • I have started with the idea that a sum of 51 implies that there are 13 0s to be placed in the matrix. Every selection of a row and a column results in the selection of 15 boxes. For the sum of this selection to be less than or equal to 13, there must be at least 2 0s in the selection. But other than drawing out the matrix and experimenting with placing the 0s, I'm unsure of how to prove this elegantly.
JesseP_613
  • 63

1 Answers1

1

Hint: There is a column whose sum is at least 7.

Hint: There is a row whose sum is at least 7.

Hint: Combine the two.

Calvin Lin
  • 68,864
  • So is it true that there is both a column and a row whose sum is at least 7 because there is no way to place the 0s in such a way that they all have a sum < 7? Is that sufficient enough for an answer? – JesseP_613 May 06 '13 at 21:21
  • Suppose all rows had sum $\le 6$. What could you say about the total sum? – vadim123 May 06 '13 at 21:22