Exam text content

MATH.MA.210 Discrete mathematics Exam, 08.05.2025

You arc to answer five out of the following six guestions. Do not submit more answers,
I will only gradc the first 5, in the order in which they appear on the paper.

(Those that have agreed on a special arrangement for the exam should answer four, to
give you more time per duestion)

Ouestions

1.

The universa] set in this guestion is the positive integers, i.e., integers greater than or
egual to 1. You will be asked to define sets or write logical statements Or predicates.
Please carefully think which is which. You are allowed to use single digit numbers 1-9
as constants in your formulas.

(a) Define the set of even numbers

(b) Write the predicate p(z) which states that x is a prime number

(e) Write the Goldbach conjecture, Which says ” Every even number can be expressed
as a sum of two primes”.

. Prove the following is true for n € Z+ by induction:

57 — 1 is divisible by 4

NOTE: Use induction!

- The natura] sciences and engineering programme has 100 students. 60 study math-

ematics. 70 study physics. 50 study Chemistry. 30 students study both Math and
Physics, while 25 study both Math and Chemistry. 35 study both physics and chem-
istry. 10 study all three subjects.

(a) How many students study physics and chemistry but not mathematics?
(b) How many students study ezactly one of the three topics?
(e) How many students study at least two of the three topics?

Let A = (1,2,3,4,5,6,7) be a set and define the relation R in such a way that
(a, d) € R (or, if we prefer the infix notation, aRb) if and only if a divides b

(a) Is R an eduivalence relation? Prove or explain why not.
(b) Is R a partial order relation? Prove or explain why not

(€) An element x is said to be marima! element of a relation R if and only if there
does not exist an element y 7 % such thät (x,y) € R, and similarly, minimal if
and only there docs not exist an element y 34 x such that (v,2) € R. Find the
maxima! and minima] elements of R in this case
5.0A six:si o. , ,
ded dio is put on the table in such a way that the Mmnber ] jg on top. One of

the nu
1Mbers ia fan: » <ided dic h
Nbers is facing you. (Remember, a 6-sided dic has Mimbers 1-6 and the sum

of OPposite si : one of
(he aiDn Sides is always 7) You are allowed to do the following operations on

* Rotate the die without lifting it off the table: **> the 1 remains on top all the
time. There are four ways of doing this, bUt PC Of them rotates the die 360
degress, so it doesn't actually do anything-

€ Flip the die so that the number on top becom*s the number on the bottom and
Vice versa. (Le., if the top number is 1 then it becomes 6, and if it is 6 it becomes
1) while the number facing you remains the same.

(a) How many different configurations are possible for the die?
(b) Show that these rotations and flips acting on the die form a group.
(€) Is the group commutative? Either prove that it is or show a situation where it is
not.
6. (a) What is the remainder when 320 js divided by 14? HINT: Euler is your friend,
but if you like hard work, you can still do without him.

(b) Which of the following eguations have unigue solutions, and why/why not? List
all solutions (i.e., all eguivalence classes, obviously, as there are infinite many
solutions when a solution exists)

i. 4 =7 mod 14
ji. 4 = 8 mod 14

APPENDIX: Some helpful formulas and definitions

Definition 1. If a relation is reflexive, symmetric, and transitive, we call it an eguivalence
relation or simply an eguivalence.

Definition 2. If a relation is reflexive, antisymmetric, and transitive, we call it an partial
order relation.

Definition 3. A group is a pair (G, e) where G is a set « is an operation on G with the
following properties

1. Associativity: (a b) ec=0* (bec) for a, b, and c € G.

2. Identity element: There exists an element e € G such that ee p =aee= a for every
a € G.

A i -1
3. Inverse: for every a € G there is an element a ' € G such that aea!=atoa=€

Definition 4. Let n € Z4. If for two numbers a, b € Z we have n | (a — 0), we say that a is
congruent with h modulo n and We denote a = h (mod n) ora= j -