CMIS 160
Discrete Mathematics

Erich Prisner
Spring 2002

Project #4

This project is due on Thursday, April 4 (firm deadline).

1. Doubling and squaring mod n

We define  n = 17.

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

b) We define another function gn: Zn Zn by gn = n2 (mod n) (squaring modulo n). Draw the digraph of the relation.

c) Find the range of the functions fn and gn. Find fn(11), gn(11), and fn(fn(11)), and gn(gn(11)).

d) Find the range of the composed function fn ° fn ° fn ° fn ° fn.

e) Find the range of the composed function gn ° gn ° gn ° gn ° gn.

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 Zn = {0,1,2, ... n-1} have the property that fn(M) is contained in M, i.e. that fn restricted to M is again a function from M to M?

i) Similiar, how many subsets M of Zn have the property that gn(M) is contained in M?

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

2. Liers

In Wafabia there are only two kind of people. Honest people who will never lie, and (chronical) liers, who will never say a true sentence. Let's listen to some conversation on the market place:
Astrid : Rosi is a lier.
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.
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)

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.