1)  Consider the following statement:

“If two numbers have the same remainder modulo 10 then their product is divisible by 100.

a)  Labeling the appropriate statements record this statement in the form of an implication.

b)  Write the contraposition of given statement.

c)   Write the negation of this statement.

2)  “All real numbers have non-negative squares.          The number  i  has a negative square.               Therefore, the number i is not a real number. ”

Is this argument valid? Label the appropriate statements with propositional variables and check the table of the inference obtained.

3)  Add (-70)+(27) using 8-bit representation.

4)  Consider the statement:

“Ifthe sum of two integers is an odd number, and one of them is even then the other integer  must be odd”.

a)  Write a predicate formula representing this statement.

b)  Write a contraposition of this formula.

c)  Prove the statement.

5)  Use mathematical induction to prove that for all integers n  4 ,

2n  3  2n .

6)   Define sets A and B of integers as follows: A  n  Z | n  5r for some integer r

B  m Z | m  3s for some integers  s

C  m Z | m  u  v for some u A,v B  .

a)   Is A  B ? Prove by an element argument or provide a counterexample.

b)  Is A  C ? Prove by an element argument or provide a counterexample.

7)  Prove or disprove:  For all sets A,B and C:  (A  B)  C  A  (B C).

.

8)  Form an eleven-letter word by mixing the letters in the word ABRACADABRA.

a)   In how many ways can you do this?

b)  In how many ways can you do this if the word must include the sub-word CAD (these letters together and in the same order)?

9)   12 people are lined up in 2 rows of 6 for a photo. How many ways can they be            arranged if the tallest person must stand in the back row and the 2 shortest in the front row (the other 9 can stand anywhere)?

10) A ball is dropped from the height of 20 feet. Each time it drops h feet, it rebounds 0.72hfeet. Find the total distance traveled by the ball until the moment it hits the ground for the seventh time.

11) A sequence a0 , a1 , a2 ,... , satisfies the recurrence relation ak    3ak 1  10ak 2   , with initial conditions a0   5 and a1   8 . Find an explicit formula for the sequence. Use this formula to calculate a10 .

12) Let A  1,2,3,4,5 and define a binary relation R among the subsets of A as follows: XRY  X  Y.

a)   Is R reflexive? Explain.

b)  Is R symmetric? Explain.

c)   Is R transitive? Explain.

13) What is the inverse of 16 modulo 43 i.e. which number a has the property that 16*a has the remainder 1 when divided by 43?

14) Prove that a full binary tree has odd number of vertices. If the number of vertices is 2k+1, then k vertices are internal and k+1 external.