Homework 4
pdf
keyboard_arrow_up
School
University of Michigan *
*We aren’t endorsed by this school
Course
203
Subject
Mathematics
Date
Apr 3, 2024
Type
Pages
9
Uploaded by KidComputer12947
EECS 203: Discrete Mathematics
Winter 2024
Homework 4
Due
Thursday, Feb. 15th
, 10:00 pm
No late homework accepted past midnight.
Number of Problems: 8 + 2
Total Points: 100 + 20
•
Match your pages!
Your submission time is when you upload the file, so the time
you take to match pages doesn’t count against you.
•
Submit this assignment (and any regrade requests later) on Gradescope.
•
Justify your answers and show your work (unless a question says otherwise).
•
By submitting this homework, you agree that you are in compliance with the Engi-
neering Honor Code and the Course Policies for 203, and that you are submitting your
own work.
•
Check the syllabus for full details.
1
Individual Portion
1. Even Just One [12 points]
Prove that if
n
3
+ 4 is even or 3
n
+ 3 is odd, then
n
is even.
Solution:
Using the contrapositive, solve by cases. ”If
n
is odd, then
n
3
+ 4 is odd and 3
n
+ 3 is
even.”
Case 1:
Prove that if
n
is odd,
n
3
+ 4 is odd.
Assuming that
n
is odd, there is an integer
k
with
n
= 2
k
+ 1
So
n
3
+ 4 = (2
k
+ 1)
3
+ 4
= 8
k
3
+ 12
k
2
+ 6
k
+ 1
= 2(4
k
3
+ 6
k
2
+ 3
k
) + 1
Since k is an integer, 4
k
3
+ 6
k
2
+ 3
k
is also an integer
So
n
3
+ 4 is odd, proving the contrapositive.
Case 2:
Prove that if
n
is odd, 3
n
+ 3 is even.
Assuming that
n
is odd, there is an integer
k
with
n
= 2
k
+ 1
So 3
n
+ 3 = 3(2
k
+ 1) + 3
= 6
k
+ 3 + 3
= 6
k
+ 6
= 2(3
k
+ 3)
Since
k
is an integer,
k
+ 3 is also an integer.
So 3
n
+ 3 is even, proving the contrapositive.
By proving both of the contrapositive cases, we have proven the original statement that
if
n
3
+ 4 is even or 3
n
+ 3 is odd, then
n
is even.
2. Odd
2
[20 points]
Prove the following for all integers
x
and
y
:
2
(a) If
x
+
y
is even, then (
x
is even and
y
is even) or (
x
is odd and
y
is odd).
(b) Using your answer from part (a), show that if (
x
−
y
)
2
is odd, then
x
+
y
is odd.
Solution:
(a) Proving by cases, let
x
+
y
be an arbitrary even integer
Assume there is an integer k with
x
+
y
= 2
k
Case 1:
Assuming
x
is even, there is an integer
n
with
x
= 2
n
Substituting into the equation, we have 2
n
+
y
= 2
k
So,
y
= (2
k
−
2
n
)
→
y
= 2(
k
−
n
)
Since
k
is an integer, (
k
−
n
) is an integer, therefore
y
is even.
Case 2:
Assuming
x
is odd, there is an integer
n
with
x
= 2
n
−
1
Substituting into the equation, we have 2
n
−
1 +
y
= 2
k
So,
y
= 2
k
−
2
n
−
1
→
y
= 2(
k
−
n
)
−
1
Since
k
is an integer, (
k
−
n
) is an integer, therefore
y
is odd.
Since the statement holds true in every case, then the statement ”If
x
+
y
is even, then
(
x
is even and
y
is even) or (
x
is odd and
y
is odd)” is true
(b) Proving the contrapositive, ”if
x
−
y
is even, then (
x
−
y
)
2
is even.
Using my answer from (a), if
x
−
y
is even, then
x
and
y
must also be even.
Since the square of an even number is always even, then the statement holds.
By proving the contrapositive, if (
x
−
y
)
2
is odd, then
x
+
y
is odd.
3. Do you
∃
xist...? [8 points]
Prove or disprove
the following: There exist integers
x
and
y
so that 20
x
+ 4
y
= 1.
Solution:
First, rearrange the equation then prove by cases
So we have
y
=
1
−
20
x
4
3
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
We are looking for an integer
x
that will produce an integer solution
y
, so 1
−
20
x
must
be divisible by 4.
Allow x to be any arbitrary integer
Case 1:
Assume
x
= 1
So we have
y
=
1
−
20
4
-19 is not divisible by 4, so
y
will not have an integer solution.
Case 2:
Assume
x
= 2
So we have
y
=
1
−
40
4
-39 is not divisible by 4, so
y
will not have an integer solution.
Case 3:
Assume
x
= 3
So we have
y
=
1
−
60
4
-59 is not divisible by 4, so
y
will not have an integer solution.
Since y is not an integer in each case, the statement that ”there exist integers
x
and
y
so that 20
x
+ 4
y
= 1.” is disproved.
4. What’s Nunya? Nunya Products are Negative. [12 points]
Given any three real numbers, prove that the product of two of them will always be non-
negative.
Solution:
Prove by cases, denoting three real numbers as
x
,
y
, and
z
.
Case 1:
All three numbers are non-negative
If all three numbers are positive and greater than zero, the product of any two of them
will always be non-negative
Case 2:
One of the numbers is zero
WLOG, let
x
= 0. Since
x
×
y
= 0 and
x
×
z
= 0, the product of any two numbers will
be non-negative
4
Case 3:
Two of the numbers are negative
WLOG, let
x
and
y
be negative numbers.
x
×
y
will yield and positive number because
the product of any two negative numbers is a non-negative number
In all possible cases, the product of two of three real numbers will always be a non-
negative number.
5. Element or Subset? [8 points]
Let
A
=
{
1
,
2
,
“a”
}
. State whether each statement is true or false. Give a brief explanation
if false (you do not need to justify why a statement is true).
(a) “a”
∈
A
(b) “a”
⊆
A
(c)
{
1
,
2
} ∈
A
(d)
{
1
,
2
} ⊆
A
Solution:
(a) True
(b) False: ”a” is not a set, so it cannot be a subset of A
(c) False: 1,2 is notated as a set and A only contains elements,not the set 1,2.
(d) False: Again, 1,2 cannot be not a subset of A because A is only made up of elements.
6. Ready,
{
s, e, t
}
, go! [12 points]
Let
S
=
{
1
,
2
,
3
,
4
,
5
}
, A
=
{
1
,
2
}
, B
=
{
2
,
3
}
,
and
C
=
{
4
,
5
}
.
Compute the following, where
complements are taken within
S.
Show intermediate steps as part of your justification.
(a)
P
(
(
A
∩
B
)
∩
C
)
)
(b)
P
(
(
C
−
B
)
∩
A
)
(c)
{
A
×
B
} ∩ {
S
×
B
}
(d) (
A
×
B
)
∩
(
S
×
B
)
5
Solution:
(a) (
A
∩
B
) =
{
2
}
C
=
{
1
,
2
,
3
}
(
(
A
∩
B
)
∩
C
)
)
=
{
2
}
P{
2
}
= 2
1
=
{
2
}
P
(
(
A
∩
B
)
∩
C
)
)
=
{∅
,
{
2
}}
(b)
C
=
{
1
,
2
,
3
}
(
C
−
B
) =
{
1
}
(
(
C
−
B
)
∩
A
)
=
{
1
}
P
(
(
C
−
B
)
∩
A
)
=
{∅
,
{
1
}}
(c)
{
A
×
B
}
=
{{
1
,
2
}{
2
,
2
}{
1
,
3
}{
2
,
3
}}
{
S
×
B
}
=
{{
1
,
2
}{
1
,
3
}{
2
,
2
}{
2
,
3
}{
3
,
2
}{
3
,
3
}{
4
,
2
}{
4
,
3
}{
5
,
2
}{
5
,
3
}}
{
A
×
B
} ∩ {
S
×
B
}
=
{{
1
,
2
}{
1
,
3
}{
2
,
2
}{
2
,
3
}}
(d) (
A
×
B
) =
{{
1
,
2
}{
2
,
2
}{
1
,
3
}{
2
,
3
}}
(
S
×
B
) =
{{
1
,
2
}{
1
,
3
}{
2
,
2
}{
2
,
3
}{
3
,
2
}{
3
,
3
}{
4
,
2
}{
4
,
3
}{
5
,
2
}{
5
,
3
}}
(
A
×
B
)
∩
(
S
×
B
) =
{{
1
,
2
}{
1
,
3
}{
2
,
2
}{
2
,
3
}}
7. Subset Proofs [16 points]
Prove that if
A
and
B
are sets, then
A
∪
(
A
∩
B
) =
A
by proving each side is a subset of
the other. This set identity is known as an absorption law. Your answer should be a word
proof, and not use any set equivalence laws.
Solution:
To prove the absorption law, we must show that
A
∪
(
A
∩
B
)
⊆
A
Choosing an arbitrary element
x
, in
A
, then we know that because of the intersection
operator,
x
must be in both
A
and
B
, and we already know that
x
is in A alone based
on the union operator.
Now checking the other side
A
⊆
A
∪
(
A
∩
B
). Using the same arbitrary element
x
, by
definition of union,
x
must be in
A
∪
(
A
∩
B
) because it is in
A
. Therefore every element
of
A
is also in
A
∪
(
A
∩
B
)
6
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Since both sides are subsets of each other,
A
∪
(
A
∩
B
) =
A
8. IceCream-Exclusion [12 points]
Out of the 40 EECS 203 staff members, 21 like vanilla ice cream, 18 like chocolate ice cream,
and 24 like strawberry ice cream. In addition, 13 like both strawberry and vanilla, and 7
like chocolate and vanilla.
(a) How many staff members like all three ice cream flavors if 9 staff members like both
strawberry and chocolate ice cream, assuming everyone likes at least one type of ice
cream?
(b) How many staff members don’t like any of the ice cream flavors if 14 staff members like
both strawberry and chocolate ice cream and 3 staff members like all three ice cream
flavors?
Solution:
(a) Find
|
V
∩
C
∩
S
∩|
, where
V
represents staff who like vanilla ice cream,
C
represents
staff who like chocolate ice cream, and
S
represents staff who like strawberry ice
cream.
By the inclusion-exclusion pattern,
|
V
∪
C
∪
S
∪ |
= 40 can be broken down into
|
V
|
+
|
C
|
+
|
S
| − |
V
∩
C
| − |
V
∩
S
| − |
C
∩
S
|
+
|
V
∩
C
∩
S
|
.
We know that
|
V
|
= 21,
|
C
|
= 18, and
|
S
|
= 24.
We also know that
|
V
∩
C
|
= 7,
|
V
∩
S
|
, and
|
C
∩
S
|
= 9
Now, we only need to find
|
V
∩
C
∩
S
∩ |
. Plugging it all in we have:
40 = 21 + 18 + 24
−
7
−
13
−
9 +
|
V
∩
C
∩
S
∩ |
40
−
34 =
|
V
∩
C
∩
S
∩|
so
6 staff members like all three flavors of ice cream.
(b) Now, we want to find
|
N
|
, the amount of staff who do not like any flavors ice cream.
We are also given
|
C
∩
S
|
= 14 and
|
V
∩
C
∩
S
∩ |
= 3
Reusing our old equation, now account for
|
N
|
, we have
|
N
∪
V
∪
C
∪
S
∪ |
= 40
and
|
N
|
+
|
V
|
+
|
C
|
+
|
S
| − |
V
∩
C
| − |
V
∩
S
| − |
C
∩
S
|
+
|
V
∩
C
∩
S
|
Plugging in our values, we have 40 =
|
N
|
+ 21 + 18 + 24
−
7
−
9
−
14 + 3
40
−
36 =
|
N
|
, so
4 staff members do not like any flavors of ice cream
7
Grading of Groupwork 3
Using the solutions and Grading Guidelines, grade your Groupwork 3 Problems:
•
Use the table below to grade your past groupwork submission and calculate scores.
•
While grading, mark up your past submission. Include this with the table when you
submit your grading.
•
Write whether your submission achieved each rubric item. If it didn’t achieve one, say
why not.
•
For extra credit, write positive comment(s) about your work.
•
You don’t have to redo problems correctly, but it is recommended!
•
See “All About Groupwork” on Canvas for more detailed guidance, and what to do if
you change groups.
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
(ix)
(x)
(xi)
Total:
Problem 1
hspace1cm/30
Total:
hspace1cm/30
8
Groupwork 4 Problems
1. Mostly Rational [12 points]
Show that if
r
is an irrational number, there is a unique integer
n
such that the distance
between
r
and
n
is
strictly
less than
1
2
.
Solution:
2. Set in Stone [8 points]
Prove using set identities that
(
A
∩
C
)
−
(
B
∩
A
) = (
C
−
B
)
∩
A
for any three sets
A, B
and
C.
Solution:
9
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help