# Discrete Structure Midterm Solutions

Exercise 1 (20 points). Prove or disprove: For any three sets A,B,C,

(a) C \ (A ∩ B) = (C \ A) ∩ (C \ B).
(b) C ∪ (A ∩ B) = (C ∪ A) ∩ (C ∪ B).

Solution

(a) The statement is false. A counterexample is: A = {1}, B = {2}, C = {1, 2}. Then C\(A∩B) = {1, 2}
but (C \ A) ∩ (C \ B) = Ø;.

(b) The statement is true. We will first show that C ∪ (A ∩ B) (C ∪ A) ∩ (C ∪ B). Consider any e
which is an element of the C \ (A ∩ B). Then e ∈ C or e ∈ A ∩ B. If e ∈ C, then e ∈ C ∪ A and
e ∈ C ∪ B, so e is an element of the (C ∪ A) ∩ (C ∪ B). If e C, then e must be in A ∩ B to still be
in the (C ∪ A) ∩ (C ∪ B). But then e ∈ A, which implies e ∈ C ∪ A, and similarly e ∈ C ∪ B, so e is
still an element of the (C ∪ A) ∩ (C ∪ B). This proves C \ (A ∩ B) (C ∪ A) ∩ (C ∪ B).

Now we show that C ∪(A∩B) (C ∪A)∩(C ∪B). Consider any element e in the (C ∪A)∩(C ∪B).
Since e must be an element of C ∪ A, it must be in C or in A. If e ∈ C, then e must be in the
C \ (A ∩ B) too. If e C, then we necessarily require e ∈ A for it to still be in C ∪ A. Also, e must
be in C ∩ B, so if e C then e must be in B. So e ∈ A ∩ B, and hence e is in the C \ (A ∩ B). So
C \ (A ∩ B) (C ∪ A) ∩ (C ∪ B).

Putting the two results together, we have proved that C ∪ (A ∩ B) = (C ∪ A) ∩ (C ∪ B).

Exercise 2 (20 points). You have been appointed Postmaster General for a new nation. Your job is to
de termine what denominations to issue stamps in. Unfortunately, the government wants to be able to
charge an amount for each letter or package that corresponds exactly to its weight, so the postage fee could
be any integral number of cents. The government is also cheap and wants to reduce costs by only printing
a minimal number of types of stamps, and stamps of value less than 5 cents will not be allowed.

(a) What is the minimum number n of integer values (where for all i) such that
all positive integers can be ex pressed as linear combinations of them? What is the precise condition
that such a minimal set has to satisfy? Prove. Does your answer apply to real life ?

(b) Suppose the government caps the lowest possible package charge at c cents, for some c > 50. In a
“real life” scenario, what is now the minimum number of stamp values (where for
all i) that you can get away with so as to cover all package weights greater or equal to c? Prove.

Solution

(a) The minimum number of values is n = 2. The precise condition is that and are coprime, namely
gcd(, ) = 1. To prove, invoke Theorem 4.4.2, that an integer is a linear combination of and
iff it is a multiple of gcd(, ). Thus if gcd(, ) = 1, all positive integers can be a linear
combination of and since all positive integers are a multiple of 1. And if gcd(, ) > 1, then 1
is not a multiple of the GCD and cannot be represented. (Note that almost every one forgot to show
this: this is what the comments “prove other direction” or “prove necessity” referred to.) Finally, it
won't work in “real life” because to represent values such as 1 requires negative coefficients , and in
real life you can't to put negative amounts of stamps on letters.

(b) The minimum number is still 2. The simplest way is to use 5- and 6-cent stamps. To prove that
this works, note that all integers c > 50 can be written as 5n + 1, 5n + 2, 5n + 3, 5n + 4, 5n + 5 for
some integer n ≥10. We can prove by induction on these five types that they can all be a linear
combination of 5 and 6 with nonnegative coefficients. For base cases (n = 10):

51 = 9 × 5 + 1 × 6
52 = 8 × 5 + 2 × 6
53 = 7 × 5 + 3 × 6
54 = 6 × 5 + 4 × 6
55 = 5 × 5 + 5 × 6

Now assume that for n = k, that 5k+1 is a linear combination of 5 and 6 with nonnegative coefficients,
so 5k + 1 = a × 5 + b × 6 with a, b ∈ N. If we consider n = k + 1, then 5(k + 1) + 1 = 5k + 6 can be
represented as (a+1)×5+b×6, so it is also a linear combination with nonnegative coefficients. The
inductive step is exactly the same for the other four cases, so if 5k + 1, 5k + 2, 5k + 3, 5k + 4, 5k + 5
can be represented than so can 5(k +1)+1, 5(k +1)+2, 5(k +1)+3, 5(k +1)+4, 5(k +1)+5. This
concludes the proof by induction.

Exercise 3 (20 points). Given a non zero rational number r and two irrational numbers a and b, prove or
disprove:

(a) ab is irrational.

(b) ar is irrational.

(c) ab is irrational.

Solution

(a) The statement is false. An immediate counterexample is . We know is irrational, but
the product ab = 2 is rational.

(b) The statement is true. Proof by contradiction: Assume ar is a rational number , where p, q ∈ Z, q ≠
0. Since r is rational, it can be written as , s, t ∈ Z, t ≠ 0. Then . Now r ≠ 0, so s ≠ 0, and
hence qs ≠ 0. pt and qs are both integers, and the latter is non-zero, so   is rational. This implies
a is rational, which contradicts our assumption. Hence the product is always irrational.

(c) The statement is false. Here are two ways to disprove it:

i. Consider . Then ab = 2, which is rational. We know b to be irrational, but a's
status is unclear. If a is irrational, then we have an immediate counterexample. If a is rational,
then we have a counterexample cd, where c = d = are irrational but the product (a) is
rational. Either way, we have shown that an irrational power of an irrational may be rational.

ii. Consider a = , . Then ab = 3, which is rational. We know a is irrational, and
so is from Theorem 3.1.2 in the lecture notes. By part (b), b is irrational and we have a
counterexample. (A very similar method can be used to show that , which
was one of the solutions you came up with during the midterm, works.)

Note: Euler's identity, , is not a counterexample: irrational numbers are a subset of the real
numbers, so an imaginary number like i does not count as irrational.

Exercise 4 (20 points). A perfect number is a natural number n ≥ 2 with the property that the sum of
all of n's divisors (including 1, but not n itself) is n. 6 and 28 are the first two examples. Prove that if
is prime, then is a perfect number. Using this property, find another perfect number
besides 6 and 28.

Solution The only prime factors are 2 and . The powers of 2 range from 0 to p - 1. Thus the
only factors are and (The second sequence stops at
since we are omitting the number itself.) We can then write the sum of factors as

The right sum can be factored out giving

Now we can use a fact about sums of powers of 2 (this is a specific example of the sum of a geometric
series):

(In your solutions, you were not required to prove this. You can prove it fairly simply by induction). If we
apply this identity twice, we have

This simplifies to

so the sum of the number's factors is the number itself and thus is a perfect number.

To find another perfect number, note that the next prime is 31 when p = 5. Plugging this into
the formula gives 16 × 31 = 496.

Exercise 5
(20 points). Consider n planes in 3-dimensional space so that no two are parallel, any three
have exactly one point in common, and no four have a common point. What is the number of 3-dimensional
parts into which these planes partition the space? Prove. (You can use the 2-dimensional result without
proof.)

Solution The problem is solved much like the 2-dimensional version. Consider adding the i -th plane (call
it plane P) and counting how many new regions it creates. Two nonparallel planes intersect along a line,
so the other i-1 planes all produce intersection lines on P. The conditions that no two planes are parallel,
any three have one point in common, and no four have a common point imply that on P, no intersection
lines are parallel and no three lines have a common point. Thus we can apply the two-dimensional result
and say that plane P is divided into regions by the i-1 lines produced from the intersections of
the other planes. Each region of P divides one of the existing regions of 3-space created by the first i - 1
planes in two, so adding the ith plane adds regions. Recalling that there is one region before any
planes are added, we can then write the number of regions as

We can break up this sum into a sum over 1, i and i2. Obviously . We know from the
lecture notes that

and from midterm practice that

(As in problem 4, you were allowed to use these without proof.) Substituting these in, the number of
regions for n planes is

which simplifies to

Much like the two-dimensional version, this can be formalized as a proof by induction.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of April 25th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!