Instructions:
1. This exam is 120 minute long, and worth 100 points.
2. This exam has 12 pages, consisting of 6 questions, all to be attempted. Write down your full working in this exam paper.
3. Calculator is allowed.
4. This exam is in closed book format. No books, dictionaries or blank papers to be brought in except one page of A4 size paper note which you can write anything on both sides. Any cheating will be given ZERO mark.
Student Number: Name:
2
2. 18 points Suppose that you are given two “NOT”s, two “AND”s, and two “OR”s of the following electronic components:
Design a circuit so that it has the following input/output table.
P Q R output
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 1
4
3. 19 points Consider the set of all strings of a’s, b’s and c’s. Let rn be the number of strings of a’s, b’s and c’s of length n that do not contain the patterns aa and ab. (n ∈Z+)
6
4. 24 points Find the smallest positive integer x satisfying the following:
95x ≡ 5 (mod 40)
21x ≡−9 (mod 60)
2x ≡ 152 (mod 75)
8
5. (10 points) A robot is cleaning floor on an n × n square grid. Each step of its movement is to move from a square to its adjacent square (up/down/left/right). Discuss
for which n it can find an n2-step path so that it can clean each square and return to the initial squre in the last step. When it is possible, present such a path; otherwise prove the infeasibility.
10
6. (18 points) A confectionery company is designing an assorted pack of confectionery consisting of chocolate (15g/bag), marshmallow (6g/bag) and toffee (10g/bag). Show that for any pack with an integer weight at least 61g (i.e., 61g, 62g, 63g, etc), there is always a way to mix these three kinds of confectionery so that the pack contains some (≥ 1 bag) of each confectionery.
12
