And answer the following questions:

(a) Is it reflexive?

(b) Is it symmetric?

(c) Is it transitive?

(d) Is it an equivalence relation?

Q. Look at the following relation:

(a) Is it reflexive?

(b) Is it symmetric?

(c) Is it transitive?

(d) Is it an equivalence relation?

Q. Show that if p is a prime number > 3, then 24 | p²-1.

Hint: Use a case split on what the remainder (rest) of p can be when dividing it by 6.

Q. Show the following: If we have a prime number p such that p | a², then we also have p² | a².

Q. Prove or disprove: If we have a natural number n such that n | a², then we also have n² | a².

Q. For what numbers m do we have that m²-1 is a prime number?

Hint: m²-1 = (m+1)(m-1)

Q. We have a natural number n > 1 that is not a prime number. Show that there must be a natural number b, such that 1 < b ≤ √n and b | n.

Q. Show that if we have a ≡ b (mod mn) then we also have a ≡ b (mod n).

Some code:

  elem :: Eq a => a -> [a] -> Bool
  x `elem` []     = False
  x `elem` (y:ys) = x==y || (x `elem` ys)   

  (++) :: [a] -> [a] -> [a]
  []     ++ ys = ys
  (x:xs) ++ ys = x : (xs ++ ys)

  rev :: [a] -> [a]
  rev []     = []
  rev (x:xs) = rev xs ++ [x]

  length :: [a] -> Integer
  length []     = 0
  length (x:xs) = 1 + length xs

  take :: Integer -> [a] -> [a]
  take n _  | n <= 0 = []
  take n []          = []
  take n (x:xs)      = x : take (n-1) xs

Q. Prove that, for all x and all lists xs, ys:

  x `elem` (xs ++ ys) = (x `elem` xs) || (x `elem` ys)

Q. Prove that, for all lists xs:

  length (rev xs) = length xs

Some more code. Here, we define a datatype for trees. The flatten function takes a tree and produces a list of all the elements in the tree. The swap function works the same as in the lecture. The size function computes the number of nodes in a tree.

  data Tree a = Empty | Node a (Tree a) (Tree a)

  flatten :: Tree a -> [a]
  flatten Empty        = []
  flatten (Node x p q) = flatten p ++ [x] ++ flatten q

  swap :: Tree a -> Tree a
  swap Empty        = Empty
  swap (Node x p q) = Node x (swap q) (swap p)

  size :: Tree a -> Integer
  size Empty        = 0
  size (Node _ p q) = 1 + size p + size q

Q. Prove that, for all trees p:

  size p = length (flatten p)

Q. Take a look at Figure 7.3 in the book (page 192), where you can see 5 examples of graphs. Which of these graphs have an Eulercycle and which ones don't?

For the ones that have an Eulercycle, construct the cycle.

Q. Given a simple graph G. Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a path from u to v in G"

Show that R is an equivalence relation.

Q. Prove that a tree with n nodes has exactly n-1 edges.

Hint: Use strong induction on the number of nodes n. In the induction step, remove one edge from the graph, and see what happens. How many components do you get?

Q. Take a look at Fig. 7.8 and 7.9 from the book (page 200-201), where you can see two examples of directed graphs. Which of these has a topological ordering and which doesn't?

For the graph that has a topological ordering, construct one.

Q. Take a look at the graph in the above figure. How many topological orderings are there for this graph? Explain how you arrived at tour answer.

Q. Given a directed graph G.

Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a directed path from u to v in G"

What properties does or doesn't R have: reflexivity, symmetry, transitivity? Explain.

Q. You roll 3 dice. What is the probability that the three values that turn up are all different? What is the probability that there are at least two dice with the same value?

Q. You roll n dice. What is the probability that there are at least two dice with the same value?

Q. Given a prime number p. Show that

(	p	)
	k

Does this also hold when p is not prime?

Q. Given the set A = {1,2,3,4,5}. How many strictly sorted lists are there of length 3 where all the elements come from the set A? A list is strictly sorted if the list is sorted, and no two elements are the same.

How many strictly sorted lists are there if A={1,2,3,...,n}, and the list length is k?

Q. Prove Fermat's little theorem, namely that

a^p ≡ a (mod p)

for any prime number p, and any natural number a.

We have actually already proved this in the lecture. This time, do it by induction on a.

Let me help you: The base case (a=0) is easy: 0^p ≡ 0 (mod p) for any p > 0.

The step case assumes that k^p ≡ k (mod p) (this is the induction hypothesis), and has to show that

(k+1)^p ≡ (k+1) (mod p)

Hint: Make use of the following: If p is a prime number, then

(	p	)
	k

Q. Prove:

(	n	) + (	n	) = (	n+1	)
	k		k+1		k+1

Q. You are taking a course with 54 students (including you). For the exercise sessions, you are randomly divided into 9 groups of size 6. You are secretly in love with one of your classmates (not yourself). What is the probability that the two of you end up in the same group?

Q. How many undirected graphs exist that have n distinct nodes?

Q. Given a directed graph that is a bijection. This means that every node has exactly one outgoing arrow, and exactly one ingoing arrow. What is the probability that there is a cycle in the graph?