Problem 1: Number Theory

a)

Write down an algorithm to determine the greatest common divisor of two integers. You may assume that they non-negative and are not both 0.

b)

Imagine you have two buckets. The first holds 42 cups and the second holds 18 cups. Assuming you have an unlimited reservoir of water (say a faucet) but need to measure precisely, so can only move water by completely filling or emptying buckets, what is the smallest amount of water you can measure into a tub? Note that as well as adding water to the tub from the buckets you may also use them to remove water.

c)

Two joggers are running laps around the same island, starting from the same location. The first jogger takes 42 minutes to do a lap, and the second takes 18 minutes. If they both start at the same time and place, how long will it be before they return to the start line simultaneously?

d)

What is the prime factorization of 63?

e)

If a | b and b | c is it necessarily the case that c | ab ? If so, prove it. Otherwise, provide a counterexample. 

Problem 3: Probability

a) Assume that A and B are independent events with nonzero probability. What can you say about the relationship between P(A) and P(A|B)?

b) Consider a game called “Roll Even” in which you roll a fair six sided die and are paid as follows: If you roll an even number X, you are paid X dollars. If you roll an odd number, you are paid nothing.

What is the expected value of this game? (This is shorthand for “what is the expected value of the random variable whose value at an outcome is the number of dollars won?”). Show your work.

c) There is a well-known story that a person named Santa Claus delivers presents to every child in the world on a certain day of the year. The quality of the gifts is supposed to depend on the behavior of the children. It is in fact observed that many children receive gifts on this day, so one may wonder if Santa Claus is a real person.

Formalize the following argument using Bayes®bsp;rule:

1: If Santa Claus exists, it seems very likely that children of rich and poor parents would receive gifts of roughly similar expense on average (since their average behavior is presumably similar). That is, gifts would be distributed fairly with respect to social class.

2: If Santa is not real, it is plausible that childrenænbsp;gifts are provided instead by their parents, in which case it is most likely that children of wealthier parents would typically receive much more expensive gifts.

3: Children of wealthier parents typically receive much more expensive gifts.

4: This provides evidence that Santa is not real.

d) Briefly discuss the limitations of naively applying Bayesian reasoning. Explain how these limitations apply to the argument in the previous part. (Hint: the intended answer involves the prior probability of Santaænbsp;existence. There are other possible answers; for instance, in part 2 only one alternative explanation is taken into account. Generally, it can be difficult to calculate the normalization factor P(E)).