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
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
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=1/2+1/2^2+1/2^3+1/2^4... 1/2=1/2^2+1/2^3+1/2^4... 1/2=1/2^2+1/2^3+1/2^4... 1/2=1/2^2+1/2^3+1/2^4... 1/4=1/2^3+1/2^4... 1/4=1/2^3+1/2^4... 1/4=1/2^3+1/2^4... 1/4=1/2^3+1/2^4... 1/4=1/2^3+1/2^4... 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: 2=1+1/2+1/4+1/8+1/16... 1=1/2+1/4+1/8+1/16... 1=1/2+1/4+1/8+1/16... 1/2=1/4+1/8+1/16... 1/2=1/4+1/8+1/16... 1/4=1/8+1/16+1/32...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
Emily uses RSA. Her public key includes the following:
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:
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
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.
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:
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 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
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