MATH-UA 120 Discrete Mathematics:

Problem Set 6
Alfred Pennyworth
Due Monday, November 11th, 2024

Assignment Instructions
• These are to be written up in LATEX and turned in on Gradescope.
• Click here to duplicate this .tex file in Overleaf .
• Write your solutions inside the solution environment.
• You are always encouraged to talk problems through with your peers and your instructor, but your
write up should be done independently.

• Problems are graded on correctness and fluency.

• Unless stated otherwise, all answers require justification.
• Some tutorials on how to use LATEX can be found here. If you have any questions about LATEX
commands you can always ask your instructor for advice.

Statement on generative AI
In this and other mathematics courses, you are expected to construct clear and concise mathematical argu-
ments based on statements proven in our text and class notes. Large language models such as ChatGPT
are unable to produce this kind of solution. They also frequently generate circular logic and outright false
results.
You may use AI to summarise content, generate study plans, create problems, or do other study-related
activities. You may not ask a chatbot to solve your quiz or homework problems, or do any assessment-related
activities.
You may use AI tools to edit your grammar and punctuation, but remember that mathematical English
is not the same as academic English in other disciplines.

1
Problem 1
For each of the following functions, determine whether it is one-to-one and/or onto.
a) f : Z −→ Z where f (n) = n2 + 1.
(
n
if n is even
b) f : Z −→ Z where f (x) = 2 .
0 if n is odd
(
1
if x ̸= 0
c) f : R −→ R where f (x) = x .
0 if x = 0
(
2n if n is even
d) f : N −→ N where f (n) = .
n if n is odd

e) f : 2Z −→ 2Z where f (A) = A ∪ {0}.

(a) Since there does not exist an n such that f (n) is negative, it is not onto. For n = −1 and m = 1,
f (n) = f (m), so it is also not one-to-one.
(b) For any integer z, there exists an integer n = 2z such that f (n) = z, so it is onto. However, all odd
numbers are mapped to 0, so it is not one-to-one.
(c) For any real number y, if y = 0, let x = 0, then f (x) = y. If y ̸= 0, let x = 1/y, then f (x) = y.
Therefore, it is onto. If f (x) = y, we consider two cases: if y = 0, then x can only be 0; if y ̸= 0, then
1/x = y implies x = 1/y, which has only one value. Therefore, it is one-to-one.
(d) It is one-to-one but not onto. It is not onto because there does not exist an n such that f (n) = 6. It
is one-to-one because if x ̸= y, then f (x) ̸= f (y). This can be easily verified by considering different cases:
when x and y have different parities, f (x) and f (y) are definitely not equal. When both x and y are odd,
f (x) = x ̸= y = f (y). When both x and y are even, f (x) = 2x ̸= 2y = f (y).
(e) It is neither onto nor one-to-one. It is not onto because for B = ∅, there does not exist an A such
that f (A) = B. It is not one-to-one because f (∅) = {0} = f ({0}), but ∅ = ̸ {0}.

2
Problem 2
Let A = {1, 2, 3, 4} and B = {5, 6, 7}. Let f be the relation {(1, 5) , (2, 5) , (3, 6) , (x, y)}, where the values of
(x, y) are to be filled by you. Give an example of (x, y) ∈ A × B so that
a) The relation f is not a function.
b) The relation is a function from A to B but not onto B.

c) The relation is a function from A to B and is onto B.

(a) Let (x, y) = (1, 6). Since 1 is related to both 5 and 6 by f , f is not a function.
(b) Let (x, y) = (4, 5). Since every element in A is related to some element in B by f , and each element
in A is related to exactly one element in B, but there is no x ∈ A such that f (x) = 7, f is not onto.
(c) Let (x, y) = (4, 7). Since every element in A is related to some element in B by f , and each element
in A is related to exactly one element in B, and for every element y in B, there exists an x ∈ A such that
f (x) = y, f is onto.

3
Problem 3
Let A be an n-element set and let i, j, k ∈ N with i + j + k = n. How many functions f : A −→ {0, 1, 2} are
there for which all three of the below are satisfied:
• a ∈ A f (a) = 0 = i,


• a ∈ A f (a) = 1 = j,


• a ∈ A f (a) = 2 = k.


Your final answer should be expressed in terms of n, i, j and k.

Given a set A with n elements, we want to determine the number of ways to define a function f : A →
{0, 1, 2} such that:

|{a ∈ A | f (a) = 0}| = i

|{a ∈ A | f (a) = 1}| = j
|{a ∈ A | f (a) = 2}| = k

We know that i + j + k = n.
First, we need to choose i elements from the n elements to assign them the value 0. There are ni ways

to do this.
Next,
we need to choose j elements from the remaining n − i elements to assign them the value 1. There
are n−ij ways to do this.
Finally, the remaining n − i − j = k elements will naturally be assigned the value 2.
Therefore, the total number of ways to define the function is:
   
n n−i
×
i j

4
Problem 4
You have 20 jellybeans and you want to eat all of the jellybeans over the course of 2 weeks. Suppose that
you eat at least one jellybean a day. Prove, using the pigeonhole principle, that there is a set of consecutive
days where you ate exactly 7 jellybeans.

Let ai represent the number of jellybeans eaten on day i, where i ranges from 1 to 14 (since there are 14
days in two weeks).
Define Sk as the total number of jellybeans eaten by the end of day k:

Sk = a1 + a2 + · · · + ak

for k = 1, 2, . . . , 14.
The set of partial sums {S1 , S2 , . . . , S14 } represents the cumulative number of jellybeans eaten by the
end of each day. Since at least one jellybean is eaten each day, S1 , S2 , . . . , S14 are strictly increasing and
distinct.
We need to prove that there exist i and j (with j > i) such that Sj − Si = 7.
Consider the set {S1 + 7, S2 + 7, . . . , S14 + 7}. These values represent the cumulative number of jellybeans
eaten plus 7.
Combine the two sets:

{S1 , S2 , . . . , S14 } ∪ {S1 + 7, S2 + 7, . . . , S14 + 7}

The combined set has 14 + 14 = 28 elements. However, each element in the combined set must be an
integer between 1 and 27 (since S14 ≤ 20 and S14 + 7 ≤ 27).
By the pigeonhole principle, since there are 28 elements and only 27 possible values (from 1 to 27), at
least two elements in the combined set must be equal. Since S1 , S2 , . . . , S14 are distinct, the equality must
occur between an element from {S1 , S2 , . . . , S14 } and an element from {S1 + 7, S2 + 7, . . . , S14 + 7}.
If Sj = Si + 7 for some j > i, then:
Sj − Si = 7
This means that the number of jellybeans eaten from day i + 1 to day j is exactly 7.
Therefore, there must be a set of consecutive days where exactly 7 jellybeans were eaten. This completes
the proof using the pigeonhole principle.

5
Problem 5
Let A be a set of 10 distinct integers between 1 and 100, inclusive.
a) Use the pigeonhole principle to prove that there are two different, non-empty subsets of A such that the
sum of their elements are the same.
b) Prove that there are two non-empty, disjoint subsets of A such that the sum of their elements is the same.

(a):
The set A has 10 elements, so it has 210 = 1024 subsets in total, including the empty set. Therefore, the
number of non-empty subsets is 210 − 1 = 1023.
The smallest possible sum of a non-empty subset is 1 (if the subset contains the smallest element of A).
The largest possible sum of a non-empty subset is the sum of all 10 elements of A. Since each element of A
is at most 100 and distinct, the maximum sum is 100 + 99 + 98 + 97 + 96 + 95 + 94 + 93 + 92 + 91 = 955.
We have 1023 non-empty subsets, but only at most 955 possible sums (from 1 to 955). By the pigeonhole
principle, since there are more subsets than possible sums, at least two subsets must have the same sum.
Therefore, there are two different non-empty subsets whose elements have the same sum.
(b):
According to (a), we know that there are two different non-empty subsets B and C whose elements have
the same sum.
Let B ∩ C = D. Define B ′ = B \ D and C ′ = C \ D. Note that B ′ and C ′ are two non-empty and
disjoint subsets of A. Since B and C are not equal and are both non-empty, and it is impossible for B ⊂ C
or C ⊂ B, B ′ and C ′ are also non-empty and not equal.
The sum of the elements in B is the sum of the elements in B ′ plus the sum of the elements in D.
Similarly, the sum of the elements in C is the sum of the elements in C ′ plus the sum of the elements in D.
Since the sum of the elements in B is equal to the sum of the elements in C, we have:

sum(B) = sum(C)

which implies:
sum(B ′ ) + sum(D) = sum(C ′ ) + sum(D)
Subtracting sum(D) from both sides, we get:

sum(B ′ ) = sum(C ′ )

Therefore, B ′ and C ′ are two non-empty and disjoint subsets whose elements have the same sum.

6
Problem 6

Let A = x ∈ Z 3 | x . Show that A and N have the same cardinality.
Hint: Define a function f : A −→ N and show that it is a bijection.

Let A = {x ∈ Z | 3 | x}. This means A contains all integers divisible by 3. To prove that the set A and
the set of N have the same cardinality, we need to find a bijective function f : A → N.
Let f (x) = x3 , ∀x ∈ A.
Now, we need to prove that f is bijective.
Assume f (x1 ) = f (x2 ), then:
x1 x2
=
3 3
Thus:
x1 = x2
Therefore, f is one-to-on.
For any y ∈ N, we need to find x ∈ A such that f (x) = y. Take x = 3y, clearly x ∈ A and:
3y
f (3y) = =y
3
Therefore, f is onto.
In conclusion, the function f is bijective, which shows that the set A and the set of natural numbers N
have the same cardinality.

7
Problem 7
Let f : A −→ B be a function. For any subset X of A we define

f (X) = f (x) x ∈ X .

Let X and Y be subsets of A. Prove that f (X ∪ Y ) = f (X) ∪ f (Y ).

To prove that f (X ∪Y ) = f (X)∪f (Y ), we can show both directions of inclusion: f (X ∪Y ) ⊆ f (X)∪f (Y )

and f (X) ∪ f (Y ) ⊆ f (X ∪ Y ).
Step 1: Prove f (X ∪ Y ) ⊆ f (X) ∪ f (Y )
∀z ∈ f (X ∪ Y ), there exists a x ∈ X ∪ Y such that f (x) = z.
If x ∈ X, then z ∈ f (X).If x ∈ Y , then z ∈ f (Y ).
Hence, regardless of whether x belongs to X or Y , we have z ∈ f (X) ∪ f (Y ). Thus, f (X ∪ Y ) ⊆
f (X) ∪ f (Y ).
Step 2: Prove f (X) ∪ f (Y ) ⊆ f (X ∪ Y )
∀z ∈ f (X) ∪ f (Y ). There are two cases:
If z ∈ f (X), then there exists some x ∈ X such that f (x) = z. Because X ⊆ X ∪ Y , we have x ∈ X ∪ Y ,
hence z ∈ f (X ∪ Y ).
If z ∈ f (Y ), then there exists some y ∈ Y such that f (y) = z. Because Y ⊆ X ∪ Y , we have y ∈ X ∪ Y ,
hence z ∈ f (X ∪ Y ).
Therefore, regardless of whether z comes from f (X) or f (Y ), we always have z ∈ f (X ∪ Y ). Hence,
f (X) ∪ f (Y ) ⊆ f (X ∪ Y ).
Combining the above steps, f (X ∪ Y ) = f (X) ∪ f (Y ).

8
Problem 8
Suppose A and B are non-empty sets and f : A −→ B and g : B −→ A are functions that satisfy g ◦ f = idA .
a) Is is necessarily true that f is surjective?
b) Is it necessarily true that g is injective?
c) Is it necessarily true that f ◦ g = idB ?

(a) No ,let A = {1, 2, 3}, B = {1, 2, 3, 4},set

f (1) = 1, f (2) = 2, f (3) = 3, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 1

Then g ◦ f = idA but f is not surjective.
(b) No ,let A = {1, 2, 3}, B = {1, 2, 3, 4},set

f (1) = 1, f (2) = 2, f (3) = 3, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 1

Then g ◦ f = idA but g is not injective.
(c) No ,let A = {1, 2, 3}, B = {1, 2, 3, 4},set

f (1) = 1, f (2) = 2, f (3) = 3, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 1

Then g ◦ f = idA but f ◦ g ̸= idB .