Problem Set 4
Name
MATH-UA 120 Discrete Mathematics
due March 3, 2023
These are to be written up in LATEX and turned in to Gradescope. 
LATEXInstructions: You can view the source (.tex) file to get some more
examples of LATEX code. I have commented the source file in places where new
LATEX constructions are used.
Remember to change \showsolutionsfalse to \showsolutionstrue in the
document’s preamble (between \documentclass{article} and \begin{document})
Assigned Problems
1. Consider the set A = {0, 1, 2, . . . , 8}. Define a relation R on A by
a R b ⇐⇒ a2 ≡ b2 (mod 9).
(a) Show that R is an equivalence relation,
(b) then determine all its (distinct) equivalence classes.
2. Are the given relations reflexive? antisymmetric? transitive? Either prove
generally or disprove via counterexample.
(a) For x, y ∈ Z, x R y ⇐⇒ |x− y| ≤ 2.
(b) x R y means that x and y have a common prime factor (a prime number
that divides both x and y), where x, y ∈ Z.
(c) For x, y ∈ 2Z. x R y ⇐⇒ x ∩ y ̸= ∅.
3.
(a) What is the total number of partitions in two of {1, 2, . . . , 100}? Remem-
ber, both parts should be non-empty.
(b) Suppose that a single character is stored in a computer using eight bits.
How many bit patterns have at least two 1’s?
1
4.
(a) Twenty people are to be divided into two teams with ten players on each
team. In how many ways can this be done?
(b) Thirty five discrete math students are to be divided into seven discussion
groups, each consisting of five students. In how many ways can this be
done?
5. (Scheinerman, Exercise 17.26:) Prove combinatorially that(
n
0
)(
n
n
)
+
(
n
1
)(
n
n− 1
)
+
(
n
2
)(
n
n− 2
)
+. . .+
(
n
n− 1
)(
n
1
)
+
(
n
n
)(
n
0
)
=
(
2n
n
)
.