Discrete Mathematics

Erich Prisner

UMUC SG

Spring 2002

a) We define a function
f_{n}: **Z**_{n} = {0,1,2, ... n-1}
**Z**_{n}
by f_{n} = 2n (mod n)
(doubling modulo n).
Draw the digraph of the relation.

b) We define another function
g_{n}: **Z**_{n}
**Z**_{n}
by g_{n} = n^{2} (mod n) (squaring modulo n).
Draw the digraph of the relation.

c) Find the range of the functions f_{n} and g_{n}.
Find f_{n}(11), g_{n}(11), and
f_{n}(f_{n}(11)), and g_{n}(g_{n}(11)).

d) Find the range of the composed function
f_{n} ° f_{n} ° f_{n} ° f_{n} ° f_{n}.

e) Find the range of the composed function
g_{n} ° g_{n} ° g_{n} ° g_{n} ° g_{n}.

f) Look at the tree shown to the right. How many labeling of the vertices of the tree with 1's and 0's have the property that for every vertex x labeled by 1, all vertices of the path from this vertex x to the root have label 1 too. Such a labeling is also shown in the picture.

g) Answer the same question for the second tree to the right.

h) How many subsets M of **Z**_{n} = {0,1,2, ... n-1}
have the property that f_{n}(M) is contained in M,
i.e. that f_{n} restricted to M is again a function
from M to M?

i) Similiar, how many subsets M of **Z**_{n}
have the property that g_{n}(M) is contained in M?

j) Answer all questions (a), (b), (c), (d), (e), (h), (i) for n = 15.

Astrid : Rosi is a lier.Can you find out who is lying and who is honest if you get the additional information that out of the 15 people involved, exactly 7 are liers? (Hint: Use bipartite graphs)

Boris : Steffi is a lier.

Steffi : Astrid is a lier.

Rosi : Erik is a lier.

Steffi : Heide is a lier.

Dieter : Jan is a lier.

Grit : Boris is a lier.

Heide : Michael is honest.

Uwe : Lothar is a lier.

Dieter : Rosie is a lier.

Franz : Grit is a lier.

Jan : Uwe is a lier.

Heide : Jan is a lier.

Lothar : Franz is a lier.

Xaver : Jan is honest.

Christel : Grit is honest.

Go to Project # 5.

Go back to Project # 3.

Projects differ in certain ways from homework. They questions there are more complex, more difficult, have several steps, and sometimes you have to use notions and tools from several chapters to solve them. But in most cases, the theorems and tools learned do not suffice to solve all parts of the project. Rather you have to discover certain facts by yourself. Learning how to make "discoveries" in the field is an important part of the class---in real life you donīt have always a textbook telling you exactly what to do. Of course you are encouraged to use any other material---books, webpages, and so on.