Homework Number Three

1. (10 points) Recall that R^n is the set of all n-tuples of real numbers. Prove that for any elements a and b of R^n, the length of a + b is at most the length of a plus the length of b. Hint: estimate the square of the length of a + b.
2. (30 points) Consider a coin which when tossed, comes up heads with probability p and tails with probability q. Of course p + q = 1. We model the experiment of tossing the coin $N$ times as follows: the space of outcomes is all sequences of H's and T's with length N, and the probability of getting a particular sequence X is

   p^(number of H's in X) q^(number of T's in X)

   1. Find the probability of getting exactly M many heads.
   2. For N=2 and N=3 find the expected value of the number of heads. What do you think happens for N larger?
   3. The frequency of heads in a sequence of length N is defined to be the number of heads divided by N. Let p=1/3 and q=2/3. For each of the values N = 10, N=100, N=1000 use Maple to draw a graph containing the points (M/N, probability of getting M heads in N trials) as M runs from 0 to N, that is to say a graph showing the probability of seeing a given frequency. What do you notice? Your graphs should be included in your solution.

      Maple hint: execute "with(plots);" and then "?pointplot" to see how to do this. When you save your Maple output as latex you will also get a PostScript file (with extension .eps), this will automatically be included when the TeX code generated by Maple is processed by TeX.

3. (20 points) Nonzero integers a and b are said to be coprime if their gcd is 1. Let a and b be coprime integers.
   1. Show that for any integer X, there exist integers M and N with M a + N b = X.
   2. Suppose that M a + N b = X for integers M, N, X. Show that if P a + Q b = X for integers P and Q then there exists an integer Y with P = M + Y b, Q = N - Y a. Hint: how can you rearrange the equation P a + Q b = M a + N b?
4. (10 points) A "register machine" is described as follows. We are given N many registers R_1, R_2 ...... R_N where each register can contain an arbitrary integer.

   A register machine is programmed using the following simple language. A statement in the language has one of the forms

   1. R_i = j (put the integer j in the register R_i)
   2. R_i = R_j + R_k (put the sum of the contents of R_j and R_k in R_i)
   3. GOTO n (jump to the n-th statement in the program)
   4. IF(R_i = R_j) THEN [some statement]
   5. IF(R_i < R_j) THEN [some statement]
   6. STOP
   Write a program for a register machine which, if it is started with a positive integer A in R_2 and a positive integer B in R_3, stops with the product A B in R_1. You can use as many registers as you wish.
5. (15 points) (One to make you think) Suppose that I have a large English plaintext of length 2 million characters. Both I and the intended recipient have a copy of a one time pad X, which no one else knows, but unfortunately X is only 1 million characters in length. So I decide to encrypt my message using a one time pad consisting of 2 copies of X and send the result to my recipient. Is this
   1. Completely secure ?
   2. Somewhat insecure but not as bad as just sending the plaintext ?
   3. Completely insecure ?
   Your answer should be justified.