 9.4.1E: a. If 4 cards are selected from a standard 52card deck,must at lea...
 9.4.2E: a. If 13 cards are selected from a standard 52card deck,must at le...
 9.4.3E: A small town has only 500 residents. Must there be 2 residents who ...
 9.4.4E: In a group of 700 people, must there be 2 who have the same first a...
 9.4.5E: a. Given any set of four integers, must there be two that have the ...
 9.4.6E: a. Given any set of seven integers, must there be two that have the...
 9.4.7E: Let S = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Suppose six integers are...
 9.4.8E: Let T = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Suppose five integers are chos...
 9.4.9E: a. If seven integers are chosen from between 1 and 12 inclusive, mu...
 9.4.10E: If n + 1 integers are chosen from the set{1, 2, 3,…, 2n},where n is...
 9.4.11E: If n + 1 integers are chosen from the set{1, 2, 3,…, 2n},where n is...
 9.4.12E: How many cards must you pick from a standard 52card deck to be sur...
 9.4.13E: Suppose six pairs of similarlooking boots are thrown together in a...
 9.4.14E: How many integers from 0 through 60 must you pick in order to be su...
 9.4.15E: If n is a positive integer, how many integers from 0 through 2n mus...
 9.4.16E: How many integers from 1 through 100 must you pick in order to be s...
 9.4.17E: How many integers must you pick in order to be sure that at least t...
 9.4.18E: How many integers must you pick in order to be sure that at least t...
 9.4.19E: How many integers from 100 through 999 must you pick in order to be...
 9.4.20E: a. If repeated divisions by 20,483 are performed, how many distinct...
 9.4.21E: When 683/1493 is written as a decimal, what is the maximum length o...
 9.4.22E: Is 0.101001000100001000001 … (where each string of 0’s is one longe...
 9.4.23E: Is 56.556655566655556666… (where the strings of 5’s and 6’s become ...
 9.4.24E: Show that within any set of thirteen integers chosen from 2 through...
 9.4.25E: In a group of 30 people, must at least 3 have been born in the same...
 9.4.26E: In a group of 30 people, must at least 4 have been born in the same...
 9.4.27E: In a group of 2,000 people, must at least 5 have the same birthday?...
 9.4.28E: A programmer writes 500 lines of computer code in 17 days. Must the...
 9.4.29E: A certain college class has 40 students. All the students in the cl...
 9.4.30E: A penny collection contains twelve 1967 pennies, seven 1968 pennies...
 9.4.31E: A group of 15 executives are to share 5 assistants. Each executive ...
 9.4.32E: Let A be a set of six positive integers each of which is less than ...
 9.4.33E: Let A be a set of six positive integers each of which is less than ...
 9.4.34E: Let S be a set of ten integers chosen from 1 through 50. Show that ...
 9.4.35E: Given a set of 52 distinct integers, show that there must be 2 whos...
 9.4.36E: Show that if 101 integers are chosen from 1 to 200 inclusive, there...
 9.4.37E: a. Suppose a1, a2, …, an is a sequence of n integers none of which ...
 9.4.38E: Observe that the sequence 12, 15, 8, 13, 7, 18, 19, 11, 14, 10 has ...
 9.4.39E: What is the largest number of elements that a set of integers from ...
 9.4.40E: Suppose X and Y are finite sets, X has more elements than Y, and F:...
Solutions for Chapter 9.4: Discrete Mathematics with Applications 4th Edition
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 9.4
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4. Discrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326. Chapter 9.4 includes 40 full stepbystep solutions. Since 40 problems in chapter 9.4 have been answered, more than 51857 students have viewed full stepbystep solutions from this chapter.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Covariance matrix:E.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x  x) (x  x) T is positive (semi)definite; :E is diagonal if the Xi are independent.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Iterative method.
A sequence of steps intended to approach the desired solution.

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Norm
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.