Question

Let A be an 8*8 boolean matrix (i.e.,every entry is 0 or 1).if the sum of the entries in A is 51, prove that there is a row i and a column j in A such that the entries in row i and in column j add up to more than 13. Further show that there are at least 4 such pair of rows and columns.

Answer 1

Answer on Question #80903 – Math – Discrete Mathematics

Question

Let A be an $8*8$ boolean matrix (i.e., every entry is 0 or 1). If the sum of the entries in A is 51, prove that there is a row i and a column j in A such that the entries in row i and in column j add up to more than 13. Further show that there are at least 4 such pair of rows and columns.

Remark

It's easy to see that in the matrix below satisfying the conditions of this question, there are no pair of rows and columns with sum of entries more than 13.

Instead, let's prove that there are pairs with the sum greater or equal to 13.

Solution

a)

First, let's note that there exists a row containing at most one zero entry.

Indeed, if each of 8 rows has at least two zeroes then the sum of entries in each row is less than or equal to 6 and the sum of all entries in A is less or equal to $8 \cdot 6 = 48 < 51$.

That row will contain at least 7 ones.

It can be shown in the same way that there exists at least one column with at least 7 ones.

Let's consider the entry at the intersection of that row and that column. If it is equal to zero then the sum of entries of both the row and the column will be equal to the sum of entries in the row and the sum of entries in the column. So, the sum of entries in the same row and in the same column will be greater or equal to $7 + 7 = 14$. If this entry will be equal to one this sum will be at least $14 - 1 = 13$.

So, taking that row and that column we have entries with sum at least 13.

b)

In order to show that there are at least 4 such pair of rows and columns, let's show that there exist at least 2 rows with at least 7 ones. Let's suppose that there exists at most one such row. Then there exist $8 - 1 = 7$ rows containing at most 6 ones and the sum of entries in these 7 rows is at most $7 \cdot 6 = 42$. So, the sum of all entries in A will be at most $42 + 8 = 50 < 51$.

It can be shown in the same way that there exist at least 2 columns containing at least 7 ones.

Now, consider 4 intersections of these 2 rows and 2 columns. It's clear that for each of 4 pairs of these 2 rows and 2 columns, the sum of entries in the same row and in the same column will be greater or equal to $7 + 7 - 1 = 13$ which concludes the proof.

Also, it proves the part "a)" of this question as it is a corollary of the part "b)".

Answer provided by https://www.AssignmentExpert.com