July 26, 2004

Unfair from fair: expectation

What is the expected (average or mean) number of coin flips that would be required in order to simulate one unfair 1/3-2/3 coin in the protocol mentioned below?

HINT Maple reports that in 1,000 random trials of the protocol below, the mean number of flips required is 2.672. In 10,000 trials, the mean number is 2.653.

What happened?

The team of Dhruv Maheshwari and Norman Yao solved this problem. Their solution is here. And so did Edward Fu, whose short and neat solution follows:

It will end after 2 flips with a probability of 3/4. It will end after E + 2 flips with a probability of 1/4. E = 3/4 * 2 + 1/4 * (E+2) = 3/2 + E/4 + 1/2 = 2 + E/4 3E/4 = 2 E = 8/3, or 2.667 flips

Written 7/28/2004

July 23, 2004

Unfair from fair

Describe a protocol with a fair coin which will simulate a 1/3-2/3 unfair coin.

What happened?

A number of people described protocols which I think will correctly answer this question. The team of Ivan Vo and Sivan Kenig, the individual Kaitlin Renaud, the team of Stephany Tzeng and Elissa Dunn, the individual Edward Fu, and the team of Laurie Drews and Neeta Shroff all gave variants of the following:
toss the fair coin twice. If it lands TT, repeat. If it lands HT or TH, declare tails, and it lands HH, declare heads.

Norman Yao and Dhruv Maheshwari gave a protocol which involved three flips. Then: if HHH or TTT, repeat; if HTH or HTT, declare heads, and otherwise (4 combinations), declare tails. I think this also works.

I don't know any protocol which works with only a bounded number of flips.

Note If you are really clever, you should be able to generalize this question: given a fair coin, how could you simulate a coin with probability of heads equal any number between 0 and 1 (try 1/sqrt(5), for example).

Written 7/26/2004

Square rewards!

The gambler flips a fair coin, and will pay you n2 dollars if the first head occurs on the nth flip. What is the expectation (average winning) amount of this game? In effect, I am asking for the sum: 1·(1/2)+22·(1/22)+32·(1/23)+42·(1/24)+52·(1/25)+...

HINT Maple reports (after 30 digit accuracy is requested!) that the sum of the first 100 terms is 5.99999999999999999999999999179 which might help you to guess an answer. But the question will only be answered if you explain how you got your answer: why you know it is true.

What happened?

Elissa Dunn appeals to authority: "Maple says it is 6."

Sivan Kenig and Ian Vo give a discussion I can't understand, but which concludes, "Thus the answer of six becomes palatable."

No one has provided me with an explanation of why the sum is 6 and therefore the problem is still OPEN!

Written 7/26/2004 What then happened?

A nice discussion by Norman Yao and Dhruv Maheshwari was sent, with the remark, "hey, its 2:40 so the solution might be hard to understand." Their solution is similar to what follows, which is Elissa Dunn's solution:

I think I found a way to prove that the sum of n^2/2^n as n goes from one to infinity is equal to 6. It is modeled after the way we solved the series in class for a winning of n. First, I qualitatively noted the sum in question: 1/2(1)+1/4(4)+1/8(9)+1/16(16)... Then, I added series whose solutions I knew, so that the sum was equal to n^2/2^n:
1/8=1/2^4+1/2^5..., etc.
The initial sum has each fraction (1/2, 1/4, 1/8, etc.) multiplied by the next consecutive square. The differences between successive squares increases by two each time. I.e., 4-1=3, 9-4=5, 16-9=7, etc. So there should be 1(1)+3(1/2)+5(1/4)+7(1/8), etc. The series that equals one contains a 1/2, and there is only one 1/2 in the initial series (n^2/2^n). So I began the next series with 1/4. I only needed three series starting with 1/4, because there was already a 1/4 in the first series. In the first four series listed above, 4 1/8ths are added, so 5 more are needed. Then in the first nine series, 9 1/16ths are added, and 7 more are needed. Hence the sum n^2/2^n equals 1(1)+3(1/2)+5(1/4)+7(1/8)..., which equals the sum of (2n+1)/2^n as n goes from 0 to infinity. I repeated the process with this sum, equal to (2n+1)/2^n as n goes from 0 to infinity:
There must be two more of each fraction (1/2, 1/4, 1/8), since the amount of each successive fraction in the series increases by two. Separating the first series from the rest, this is equal to: two plus the sum of (2/2^(n-1)) as n goes from 1 to infinity. The two can be factored out, so this is equal to: 2+2*E((1/2)^(n-1)) as n goes from 1 to infinity. The formula for the solution to an infinite geometric series is S=(t1/(1-r)). t1 is 1, because (1/2)^(1-1) is 1, and r is (1/2). S=(1/(1-1/2))=2. (Or, I can borrow the result when we did this sum in class on July 23.) The entire sum, then, equals 2+2*2, or 6.

Written 7/28/2004

July 15, 2004

Break RSA

Emily uses RSA. Her public key includes the following:
  • Her N (the product of two large primes) is 761306210631950785511156679429580883

  • Her encryption exponent is 23

An encrypted message sent to Emily is 493963282190864398820004321017680706

What is the message? The alphabetic method introduced below in secret sharing is used to send the name of a prize.

Fred uses RSA. His public key includes the following:
  • His N (the product of two large primes) is 10000000000000000000000000000000803000000000000000000000000000011773

  • His encryption exponent is 123456789

An encrypted message to Fred is 7201982439767275938964208220144077999154093423879102903899915907244

What is the message? The alphabetic method introduced below in secret sharing is used to send the name of a prize.

What happened?

The team of Dhruv Maheshwari, Adam Shapiro, Andrew Bulthaupt, Andy Ogden, and Norman Yao got the messages (which were Peanuts and Pistachios). They supplied this explanation. As I remarked in class, &^ will ask Maple to use clever exponentiation, and so they will not run into some of the difficulties they list. The consolation prize (Almonds) winner, Monika Young, also ran into this problem. The winning team factors Fred's message using brute force, as in Emily's message. I did think that something more subtle and easier could be done. The N is 1[lots of 0's]803[lots of 0's]11773. Now 11773 is the product of 61 and 193. This suggests that N is the product of 1[lots of 0's]61 and 1[lots of 0's]193, which is in fact true. You can count the 0's by hand to get them!

Written 7/26/2004

July 9, 2004

A minor challenge:

I asked students to tell me the sum of 1+(1/2)+(1/3)+...+(1/50), exactly. This can be done with the following one line in Maple:
The answer is


The first people to submit a correct answer were "Joe and Angel" (no last names were given [later identified as Joseph Abatemarco and Angel Irizarry]) at Fri, 9 Jul 2004 15:49:43, during class! The same answer was sent to me by Theodore Moskalenko at Fri, 9 Jul 2004 15:57:20 and by David Polley at Fri, 09 Jul 2004 16:39:21. Also, Elissa Dunn supplied the correct answer at Fri, 09 Jul 2004 16:49:38.

Both Christine Grispino (at 9 Jul 2004 15:59:53) and Sabrina Moran (at Fri, 9 Jul 2004 13:19:57 [time set?]) supplied the answer 4.9920533833, although Ms. Moran had somewhat fewer decimal places. This answer is a floating point approximation to the exact answer requested.

A major challenge:

Sharing secrets, mod P

I have chosen a large prime number: P=74921203450111234637. All arithmetic in this problem will be done mod P.
I also carefully created a polynomial, G(x), of degree 3. So G(x) "looks like" Ax3+Bx2+Cx+D where the constant term D is THE SECRET. I will give every student a "personal" and distinct share of the secret on Friday, July 9. Since G(x) has degree 3, at least four students will need to combine the information they have to find THE SECRET.

The secret, although a number, also represents an English word. I have made a word using a simple process which the following table may help explain:

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

The English word SMILE becomes 19 13 09 12 05 which is more usually written 1913091205. This isn't a very convenient way of writing words, but it will be adequate for what we do. Notice that you should always pair the digits from right to left, so that the number 116161205 will become 01 16 16 12 05 which is APPLE. The "interior" 0's will be clear but we need to look for a possible initial 0.

How to win this contest and get a valuable prize
Tell me the secret word: send me e-mail as soon as possible. Please also identify all members of the group who have contributed to your solution of this problem. I would prefer e-mail because the earliest solution wins. Please give me a short description of the process you used.
Prizes to the first three correct entries!
Comment I would use Maple of course, and have Maple remember all of the relevant numbers and polynomials for me and do all of the arithmetic. If you need to retype a number, you are doing too much work!
The secret word is the name of something edible.

What happened?
What follows is a message sent to me at Sat Jul 10 13:19:21 2004. It contains tbe full details of one solution of the secret-sharing problem. I am happy to note that the solution sent to me, which uses Maple, is not done the way I expected. I thought that people would construct the interpolating polynomial, Q(x), as I had on page 4 of the notes (and as I had done in class during the first meeting) and then the secret would be Q(0). This can be done and is not difficult, but instead a group of students used the msolve command of Maple to solve directly four linear equations in four unknowns (all arithmetic done mod P, of course!). So here is the message, which I have edited slightly:

> # this problem was solved using the msolve() function
> # Our ordered pairs were:
> (234276, 95106838147999873)  - Dhruv Maheshwari
> (252542, 111347852922570823) - Norman Yao
> (247266, 106405201511676883) - Andrew Bulthaupt
> (258641, 117324597171167383) - Andy Ogden
> x1 := 234276;
                             x1 := 234276
> x2 := 252542;
                             x2 := 252542
> x3 := 247266;
                             x3 := 247266
> x4 := 258641;
                             x4 := 258641
> G1 := 95106838147999873;
                       G1 := 95106838147999873
> G2 := 111347852922570823;
                       G2 := 111347852922570823
> G3 := 106405201511676883;
                       G3 := 106405201511676883
> G4 := 117324597171167383;
                       G4 := 117324597171167383
> # now solving a system of equations...
> msolve({G1 = A*x1^3+B*x1^2+C*x1+D,
> G2 = A*x2^3+B*x2^2+C*x2+D,
> G3 = A*x3^3+B*x3^2+C*x3+D,
> G4 = A*x4^3+B*x4^2+C*x4+D},P);
             {D = 30815031512012005, C = 7, B = 6, A = 5}
> # 03 08 15 03 15 12 01 20 05 = CHOCOLATE
I presume that the value of P (74921203450111234637) was "told" to Maple earlier in the session. I think this is a very neat solution.

Written 7/12/2004

July 7, 2004

I gave each student a share of a secret. In fact, there were two secrets, ALPHA and BETA.
About secret ALPHA
I used the polynomial f(x)=5x2-16x+205. I used Maple to create a collection of points on the curve y=f(x) with the command: seq([-x+1,f(-x+1)],x=-25..25); which gave as output a collection of ordered pairs. The first ordered pair was (26,3169) and the last ordered pair was (-24,3469). I had to remember to discard (0,205) (or else one participant would have had the secret itself!). Then I printed out each ordered pair with the word ALPHA> Probably the hardest part was cutting the paper and not losing any of the slips.
About secret BETA
Similar to ALPHA except that the quadratic polynomial here was f(x)=3x2+4x-200.
What happened?
I asked students to get together and "solve" for ALPHA's secret (which was 205) and BETA's secret (which was -200). Then two of the trios would need to add their secrets and tell me as soon as possible the sum, 5. The winners were a group with names Andy and Siven and Dhruv and Andrew and Neeta and Mike. I thank them very much.

Written 7/7/2004

Maintained by greenfie@math.rutgers.edu and last modified 7/7/2004.