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
