Prelim I Solutions

CS 280 - Spring 2002

1. (5 points)
A function f(n) on the natural number is defined as follows: 
    f(0) = 2 
    f(n+1) = 2 f(n) + 1 
Use induction to prove that f(n) = 2ⁿ⁺¹ + 2ⁿ - 1 for n > 0. 

Basis: By formula f(0) = 2¹ + 2⁰ -1 = 2 + 1 - 1 = 2 which agrees with the definition. 

Induction Hypothesis: Assume that f(k) = 2^k+1 + 2^k -1 for some k.

Consider f(k+1).  
f(k+1) = 2f(k) + 1 by definition.
Thus, f(k+1) = 2(2^k+1 + 2^k -1) + 1 by the Induction Hypothesis.
Multiplying out and adding, we have, f(k+1) = 2^k+2 + 2^k+1 - 1 which agrees with the formula.

2. (10 points) 
A picture is drawn on a piece of paper according to certain rules. The picture starts with two points and the line segment connecting them. There are three operations that can be used to change the picture: (1) a new point can be placed on an existing line segment, destroying the old segment and creating two new segments, (2) a new line segment between two existing points can be added, and (3) a new point not on an existing line segment can be created and then connected to an existing point by a new line segment. Line segments are not allowed to cross other line segments and are not allowed to intersect points other than their endpoints.

Note that a valid picture divides the piece of paper into regions. For instance, the valid example shown above has 5 regions: the four triangular regions and a fifth region consisting of all the paper outside the drawing. A picture consisting of a single square would create two regions: one inside the square and one outside the square. A picture consisting of the single starting segment would have just one region. Let p represent the number of points, s represent the number of segments, and r represent the number of regions. Use induction on the number of operations to prove that p - s + r = 2 for any valid picture. 

Basis: For the starting segment, p=2, s=1, and r=1, confirming that p-s+r=2.

Induction Hypothesis: After n operations, we have a picture with p-s+r=2.

Consider a picture after n+1 operations.  Undo the last operation, leaving a picture made from n operations; by the Induction Hypothesis, this picture has p-s+r=2.  Now we execute the last operation.  There are 3 cases (we use p', s', and r' to represent the result after the (n+1)^st operation):

1. Adding a point on a segment: In this case s'=s+1, p'=p+1, and r'=r.  Easy to see that p'-s'+r' = 2.
2. Adding a new segment: In this case s'=s+1, p'=p, and r'=r+1.  Easy to see that p'-s'+r' = 2.
3. Adding a new point and new segment: In this case s'=s+1, p'=p+1, and r'=r.  Easy to see that p'-s'+r' = 2.

Since each operation results in the same formula, the formula must hold for all valid pictures.

3. (10 points) 
a. Consider the following claim. 
Claim: For all positive integers a, b, and c, it is the case that if a divides b and gcd(b, c) > 1 then gcd(a, c) > 1. 
Decide whether your think the claim is true or false and support your answer with an appropriate short proof or counterexample.

False.  Let a=2, b=6, and c=9.  In this case a|b and gcd(b,c)=3 which is > 1, but gcd(a,c)=1.

False.  Consider a=10.  It's clear that 10 | (a+10b), so (a+10b) cannot be prime regardless of b's value.

4. (15 points) 
For full credit, you must show your work. 

a. Find an integer y such that 5y = 22 (mod 91). 

We know gcd(5, 91) = gcd(5, 1) = 1.  Working backward, we have 
1 = 0(5) + 1(1) = 0(5) + 1(91 - 18*5) = 1*91 -18*5.  
Thus, the inverse of 5 (mod 91) is -18.  Multiplying both sides of the original congruence by -18, we have
y = (-18)(5)y = (-18)(22) = -396 (mod 91).  So the answer is -396 or 59 [or -396 plus any multiple of 91]. 

b. What is the last digit (i.e., the units digit) of 222³³³?

222³³³ = 2³³³ (mod 10).  Now the powers of 2 (mod 10) are: 2, 4, 8, 6, 2,...  Note that they cycle after 4 steps.  Thus, 2³³³ = 2^{333 mod 4} = 2¹ = 2 (mod 10).  The last digit is 2.

Taking the numbers mod 5, we have 4³ + (4*1*3) = 64 + 12 = 4 + 2 = 1 (mod 5).

5. (10 points) 
A proposition is said to be satisfiable if there exists a way to assign truth values so that the proposition is true. For each of the following propositions, determine if it is satisfiable. Support your answer with a short proof. 

a. not ( ( p and (not q) ) -> ( (not p) or q ) )

This is satisfiable.  Consider p=T, q=F.  In this case, the implication is false (because it's T->F); thus the proposition is true.

b. (p -> q) xor (q -> (p -> (not p) ) )

This is not satisfiable.  To show something is not satisfiable we need to show that there is no assignment of truth values that makes the statement true.  The easiest way to do this is with a truth table.

The two columns marked * agree, so when we apply exclusive-or to them, we get a column consisting entirely of F.  Thus the statement is not saticfiable.