Question

a) 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 pairs of rows and
columns.
b) If a planar graph has the degree sequence {2,2,3,3,4,4,4}, how many faces will it have? Draw
a planar graph with this degree sequence and number the faces to check your answer.
c) Give the order and the degree of the recurrence
a
2
n+2 = a
2
n +2an +4
Is the recurrence homogeneous?

Answer 1

ANSWER on Question #81202 – Math – Discrete Mathematics

QUESTION

a) Let $A$ be an $8 \times 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 pairs of rows and columns.

b) If a planar graph has the degree sequence $\{2,2,3,3,4,4,4\}$, how many faces will it have? Draw a planar graph with this degree sequence and number the faces to check your answer.

c) Give the order and the degree of the recurrence

$$a_{n+2}^2 = a_n^2 + 2a_n + 4$$

Is the recurrence homogeneous?

SOLUTION

a.1) 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.

a.2) 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.

b) Euler's formula for finite, connected, planar graphs with $v$ vertices, $e$ edges and $f$ faces is $v - e + f = 2$ .

The sequence $\{4,4,4,3,3,2,2\}$ is easily seen to be the degree sequence of a connected, planar graph.

Label the vertices of a cycle $C_7$ by 1,2,3, ...,7. Draw additional edges

$1 \leftrightarrow 3, 3 \leftrightarrow 5, 5 \leftrightarrow 1$ internally and the edge $2 \leftrightarrow 4$ externally. This gives a plane drawing of a connected graph with the given degree sequence.

Since $2e$ equals the sums of the degrees of the vertices, $e = 11$ . Therefore $f = 2 + e - v = 2 + 11 - 7 = 6$ .

There are 6 faces, including the unbounded face, in this planar graph.

c)

$$a _ {n + 2} ^ {2} = a _ {n} ^ {2} + 2 a _ {n} + 4 \rightarrow \left[\begin{array}{l}n + 2 \rightarrow k\\n \rightarrow k - 2\end{array}\right]\rightarrow a _ {k} ^ {2} = a _ {k - 2} ^ {2} + 2 a _ {k - 2} + 4$$

This recursive relation has order 2, since it contains terms whose order is not higher than 2.

This recursive relation has degree 2, since it contains term $a_{k-2}$ .

This recurrence relation is not homogeneous because it contains a constant summand - 4.

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