Homework 11 (assigned September 1, due September 6)

Reading: Rosen chapter 6, section 6.4; chapter 3, sections 3.4–3.6

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Let X denote the number obtained when one number is selected at random from the numbers 1, 2, 3, …, N.
   • Find E(X).
   • Find V(X).

2. Suppose we roll a die until a 6 comes up.
   • What is the probability that we roll the die n times?
   • What is the expected number of times we roll the die?

3. A restaurant gives one of 5 types of coupons with each meal, each with equal probability. A customer receives a free meal after collecting one coupon of each type. How many meals does a customer expect to need to buy before getting a free meal?

4. Use Euclid's algorithm to determine the greatest common divisor (gcd) of the following pairs of integers, and express the gcd as an integer combination of the two numbers. Show each step of Euclid's algorithm.
   • (480, 105)
   • (252, 180)

5. Prove each of the following properties of greatest common divisors.
   • For all integers a and b, gcd(a, b) = gcd(b, a) = gcd(a, −b).
   • For all integers a and b, gcd(a, b) = gcd(b, a − bq) for any integer q.
   • For all integers a and b and any nonnegative integer n, gcd(na, nb) = ngcd(a, b).

6. Solve the following congruences.
   • 3x ≡ 2 (mod 5)
   • 7x ≡ 3 (mod 10)
   • x + 6 ≡ 4 (mod 7)
   • 4x + 3 ≡ 4 (mod 5)
   • 6x + 3 ≡ 1 (mod 10)

Assigned problems (to be handed in):

1. Bob is shown a deck of 3 cards numbered 1, 2, and 3. The cards are shuffled and placed face down on the table. Bob is asked to call the order of the cards. Let X denote the number of correct calls. Consider the following possible ways that Bob might guess.
   • He chooses one number and calls it three straight times.
   • He makes three independent guesses. For example, he can roll a fair die and guess the first card is 1 if a 1 or a 2 comes up, guess the first card is 2 if a 3 or a 4 comes up, and guess the first card is 3 if a 5 or a 6 comes up. The die is then thrown 2 more times to determine his second and third calls.
   • He chooses at random one permutation from among all the permutations of the numbers 1, 2, 3 and calls his guesses in order specified by the selected permutation.
   For each of these three methods of guessing, find the following quantities.
   1. The distribution of X. (3 points)
   2. The expected value of X. (3 points)
   3. The standard deviation of X. (3 points)
   4. Which method should Bob use and why? (1 point)

2. Suppose that we flip a coin until either it comes up tails twice or we have flipped it 6 times. What is the expected number of times we flip the coin? Show your work. (5 points)

3. Suppose we have a sequence of Bernoulli trials, each with probability p of success and a probability q = 1 − p of failure. Let X be the number of trials needed to obtain a success. Assuming q < 1, calculate the variance of X. Show your work. (5 points)

4. A drunk has n keys, and only one will open the door. He tries keys at random. For each of the following models, what is the expected number of selections until he opens the door? Show your work.
   1. He selects keys in a random order without replacement until one works. (5 points)
   2. After each mistake, he replaces the key and selects randomly again. (5 points)

5. Prove each of the following statements.
   1. Any integer a is of the form 3k, 3k + 1, or 3k + 2. (2 points)
   2. One of three consecutive integers is a multiple of 3. (3 points)

6. Use Euclid's algorithm to determine the greatest common divisor (gcd) of the following pairs of integers, and express the gcd as an integer combination of the two numbers. Show each step of Euclid's algorithm. (2 points each)
   • (224, 126)
   • (299, 221)
   • (249, 37)

7. Prove the following statements for positive integers a, b, and n.
   1. If a and b are relatively prime, i.e., gcd(a, b) = 1, and a divides bn, then a divides n. (5 points)
   2. Suppose that gcd(a, b) = 1 and that a divides n and b divides n. Then ab divides n. (5 points)

8. Recall from class that the multiplicative inverse of a mod n is an integer z such that az ≡ 1 (mod n). Find each of the following multiplicative inverses, or prove that a multiplicative inverse does not exist. If an inverse exists, give the smallest positive value. Show the steps of your work. No points will be given for just stating the answer. (5 points each)
   1. 5⁻¹ (mod 17), i.e., multiplicative inverse of 5 (mod 17).
   2. 39⁻¹ (mod 403), i.e., multiplicative inverse of 39 (mod 403).

9. Suppose that Alice sleeps exactly 8 hours each day and goes to sleep at midnight on April 1. She always goes to sleep exactly 17 hours after she wakes up.
   1. Does Alice rise at each hour of the day during the month of April? Explain. (2 points)
   2. What happens if instead she always goes to sleep exactly 18 hours after she wakes up: does she rise at each hour of the day during April in this case? Explain. (3 points)