/compile/output.dvi
CIT 592 – Fall 2021 (Prof. Clayton Greenberg)
Homework 4 (100 pts)
Posted Saturday, September 25
Due Saturday, October 2, 11:59 PM, uploaded to Gradescope
Logistics Your homeworks must be typeset in LATEX and turned in as a PDF file. Handwritten
homeworks, or homeworks that are prepared with other tools (e.g., MS Word), will not be accepted.
The front page of your homework must contain: your name, when you plan to attend recitation,
and the names of your collaborators (see Canvas for the collaboration policy). You must upload
to Gradescope the PDF file of your submission. It is your responsibility to verify that you have
submitted the correct file by redownloading your submission from Gradescope. For full credit, all
solutions must be in closed form unless stated otherwise. You must show all work and justify
all solutions unless otherwise stated.
1. [16 pts] For each of the following relations, tell us whether they are reflexive, symmetric,
anti-symmetric, and transitive. Provide very brief explanations when the answer to a property
is YES. Provide a single counter example when the answer to a property is NO.
Let H be the set of all humans.
(a) On the set {Anna, Elsa, Kristoff}, the relation {(Anna, Kristoff), (Kristoff, Anna)}
(b) On H, for h1, h2 ∈ H, h1 ∼ h2 iff they live in the same town (Arendelle, for example).
(c) On H, for h1, h2 ∈ H, h1 ∼ h2 iff h1 WANTS to build a snowman with h2.
Note: This is about wanting something, not building something!
(d) On the set of {1, 2, 3, 4, 5}, the relation {(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)}
2. [16 pts] Talking to the n ≥ 6 (n ∈ N) distinct pictures on the walls isn’t fun enough anymore,
so Anna has decided redecorate the n−3 rooms in the castle. Elsa, on this one isolated occasion,
responds and agrees to help through the door, but she doesn’t remember the layout of the castle
anymore. So the best Elsa can do is group the paintings into exactly n− 3 groups by creating
an equivalence relation such that each set of paintings forms an equivalence class. That way
Anna can assign the groups to rooms later. How many equivalence relations can Elsa make?
Homework 4 CIT 592 2
3. [12 pts] Give an example of finite sets X,Y and functions f : X → Y and g : Y → X such that
all of the following conditions are simultaneously satisfied:
• g ◦ f is a bijection,
• g ◦ f is different from the identity function,
• f is not a surjection,
• g is not an injection, and
• X has exactly 2 elements.
You must justify why f and g are well-defined, that your g ◦ f is not the identity function, why
your f is not a surjection, and why your g is not an injection. No other proof is required.
4. [18 pts] Let X = Z × Z and let Y = Z × N. Consider a function f : X → Y . Therefore,
this function takes two numbers in and gives two numbers out. Notationally, we can write an
input pair as ~x = 〈x1, x2〉 and an output pair as ~y = 〈y1, y2〉. Now we can define the mapping:
f(~x) = 〈x2, abs(x1)〉 = 〈y1, y2〉 = ~y.
(a) Prove or disprove that f is well-defined.
(b) Prove or disprove that f is surjective.
(c) Prove or disprove that f is injective.
5. [18 pts] Summer is now over and indeed, it made Olaf a. . . happy snowman! He is now collecting
a non-empty set L of autumn leaves and wants to distribute them to the non-empty set A of all
Arendellians. A non-empty subset of picky Arendellians P are very particular about their leaves
and only want leaves from the non-empty subset R of red leaves. All leaves are distinguishable.
To make sure that each Arendellian gets a leaf, Olaf wants to use an injective function g : A → L
to map each Arendellian to the leaf they will receive such that given an Arendellian a, the leaf
g(a) will only belong to a. Note, however, that Olaf is considerate and will only give the
picky Arendellians in P a red leaf, so for every Arendellian a ∈ P, g(a) ∈ R. For notational
convenience, let |A| = a, |L| = l, |P | = p, and |R| = r.
(a) What relationships (equalities or inequalities) must exist between a, l, p and r for Olaf to be
able to assign Arendellians to leaves such that everyone is satisfied? Justify your answer.
(b) Given that the relationships you found in part (a) hold, how many different ways can Olaf
assign Arendellians to leaves? Your answer should depend upon only the given variables.
Homework 4 CIT 592 3
6. [20 pts] Oaken decides he needs to offer something new to attract business for his trading
post, so he decides to start selling snowcones with many artisanal flavors that can only be made
once. But, the real million dollar idea is that he can put multiple artisanal flavors on the same
snowcone! So to organize production, Oaken creates a surjective function f : F → S assigning
distinct flavors to snowcones, where F is the set of all flavors, and S is the set of all snowcones.
Note, each flavor must exist on exactly 1 snowcone. In addition, each snowcone must have
exactly k ≥ 1 flavors.
(a) Give an example of a set of flavors F and a function g : F → S, where S = {1, 2, . . . , k} is
the set of snowcones. Show that g satisfies the properties above, namely that g is surjective
and exactly k ≥ 1 flavors must be on each snowcone.
(b) Given that there are k times as many flavors as snowcones and there are n > 0 snowcones,
how many different functions can Oaken create that satisfy the properties above?