Homework for the math lectures at the 2003 Governor's School

We should have some homework. I can see how I am doing and you can show me how clever you are!

The pigeons know it is true, but show me ...

We saw that there is some positive integer N so that the product of N and 12,345 when written in the decimal system only has 1's and 0's. The verification presented of this fact was not very constructive (yes, it gave a finite collection of such integers among which must be one which is divisible by 12,345, but the collection was large, and the integers involved are very very large). So: please show me an explicit integer N whose product with 12,345 has only 0's and 1's. By the way, pigeons do more than just find pigeonholes. They are an important component of the technology of the search engine, Google.
Written 7/22/2003
Daniel Wojcik was the only person who answered in the very brief time available. His number was 1111 ... (6,576 1's)...1110. I asked him how he did it, and this is most of his response:
The number is the difference between two numbers that are equivalent mod 12345.
I chose this path because of your lesson in class before.
As for finding it, I had MAPLE search through all numbers consisting entirely of 1's (up to 12346 digits because of the pigeonhole principle) for one that had a remainder of 1 when divided by 12345. It returned a number that consited of 6577 1's. Subtracting 1 from this number yields my number. Since MAPLEAnswer=1 mod 12345 and 1=1 mod 12345, MAPLEAnswer-1=1-1 mod 12345 = 0 mod 12345. Thus, the resultant number is a multiple of 12345. MAPLE confirms this both by returning an integer for the division and 0 for the mod.
This is very nice work, but of course Mr. Wojcik was a bit lucky that any number of the form 111...111 was equal to 1 mod 12,345 since our proof only guaranteed some coincidence, not that the coincidence had to occur in the "box" labeled "1". He was lucky too that Maple didn't run out of storage (in real life installations, Maple has a finite amount of storage and running time). By the way, there's a much smaller number which has the property desired and which isn't found by following the proof.

Some probability questions

NvJ
Suppose you have a fair coin. Describe how to simulate a sequence of H's and T's so that the probability of H is 2/3 and the probability of T is 1/3. Please explain why the scheme you suggest will actually "report" H's and T's with probability 1 (that is, the solutions I think of all have alternatives and some of the alternatives lead to no "report" of the simulated coin, so a brief explanation of why the "no report" event has probability 0 should be included.
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).

Answers to the NvJ question
People answering the first question included Emily Carey, Andy Hurwich, Mackenzie Esch, the team of Olivia Nnadi and Nancy Twu and Rachel Laskin, Ryan Measel, and Sudipta Bandyopadhyay. Slightly less satisfactory answers were received from the team of Joseph Gregg and Daniel Wojcik, the team of Dana Andre and Mike Cobby, and Alfred Chi.

A sum
Try to explain why the sum of n2/2n as n runs from 1 on up is 6. I think this can be done with reasoning similar to (but not identical with!) what I did in class for n/2n.

Answers to the sum question
This is a more subtle question. Such tools as Maple and the TI-89 both will return the answer 6 when the above sum is requested. However, I was careful both in class and here to phrase my request as "explain why ..." and not just as "What is the sum?" There are various ways to explain why, including some using techniques from calculus. The team of Eugene Shvarts and Moulin Chokshi gave an excellent explanation using a method similar to what I used when I analyzed the sum of n/2n. Also Jonathan Lin gave a very nice answer. Please note that (amazingly!) the sum of nk/2n is an integer for every positive integer k. I don't at all believe this is immediately obvious! You can find out much more about these numbers. Generally, the On-Line Encyclopedia of Integer Sequences is an amazing resource for looking up and investigating integer sequences.

Break some encrypted messages

Hint: Each message is the name of an animal.
The word "animal" is used with some generality. Last year, a bicycle was one of the animals.
When asked if a bicycle was really an animal, I replied, "Well, it has two wheels, doesn't it?"
Please send me e-mail with the name of the "animal" and the names of the students who worked on the problem. Also identify the message you are "breaking".

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 553086475080146500881828218426016983
What is the message? The alphabetic method introduced below in secret sharing is used to send a word.

Alice and Bob decide to use the Diffie-Hellman protocol to exchange information. This is what happens:
  • They agree to use the prime number 7902193960277

  • They agree to use 30907 as the base for their exponentiation.

  • Alice sends this number to Bob: 4375119686186

  • Bob sends this number to Alice: 4409294391128

  • Now Alice and Bob share information, namely Secret=base(Alice's exponent)·(Bob's exponent)
    They can compute this independently by repeated exponentiation.
Alice now sends Bob the message 7252269932732
The message is the sum mod their prime number of the secret and the name of an "animal" using the method described below.
What is the animal?

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 2269522818433133280959630874779136137113912799869417304710696335327
What is the message? The alphabetic method described below is used to send the name of an animal.

Remember, in cryptanalysis, you can make guesses, etc. Any "tricks" are legitimate.

Entries in the wonderful ANIMAL contest
Sudipta Bandyopadhyay entered and correctly identified Emily's animal as the radish. The team of Mustafa Engin and Matt Donahoe also correctly identified Emily's animal.

The four-person team of Daniel DeMarco, Eugene Shvartz, Jonathan Lin, and Parshant Mittal identified both Emily's animal and the fierce animal of Alice and Bob, the celery.

Finally, the team of Joseph Gregg and Daniel Wojcik identified all three of the animals (even Fred's chicken!). I congratulate them. All of their answers arrived first. Please note that a direct factoring attack on Fred's N via Maple is not practical. One must be a bit devious and look at the number. Consider that it might be a product of two numbers of the form 10n+m, and then factor 11773 (it is 61·193) and try to find the "correct" powers.

Very appropriate awards were given to all participants.

Sharing secrets, mod P

I have chosen a large prime number: P=5217811345853. All arithmetic in this problem will be done mod P.
I also carefully created a polynomial, G(x), of degree 4. So G(x) "looks like" Ax4+Bx3+Cx2+Dx+E where the constant term E is THE SECRET. I will give every student a "personal" and distinct share of the secret on Wednesday, July 2. Since G(x) has degree 4, at least five 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:

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 o.k. 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. 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.
Comment I would use Maple of course, and have Maple create and remember certain polynomials for me and do all of the arithmetic.
Written 7/1/2003

Entries in the TOAD contest
The Grand Prize winners are the team consisting of Alfred Chi, Michael Cobby, Robert Hohenstein, Jason Tchuo, and Jeff Wen who submitted the answer 2345x4+3456x3+4567x2+5678x+20150104 at 19:07:18. The constant term, 20150104, "translates" to TOAD.
There are several Less Grand Prize winners. The six member team of Ryan Measel, Eric Hu, Dipen Patel, Landon Glover, Mike Cole, and Josh Verdeck submitted their answer at 21:04:13 with the best exposition of any entry.
At 21:04:58 a team of valiant losers composed of Emily Carey, Ashley Freeman, Elizabeth Strauss, Katherine Wu, and Debra Perrone sent a message.
Other Less Grand Prize winners were the team (22:28:51) of Lucy Xu, Andreia Da Costa, Myrtha Glaude, Caitlin Costaney, and Amy Q. Lin and the team (23:19:04) of Jonathan Lin, Eugene Shvarts, Parshant Mittal, Daniel De Marco, and Frederick Hardenbrook.
The Weirdness Prize was won with the entry submitted at 00:40:01 by the team of Sarah Davies, Daniel[le] Jones, Angelica Harris, and Nancy Girgis (yes, a team of only four!) whose answer was 7.552162243·1014. Sigh.
Written 7/3/2003

Added 7/7/2003 E-mail was not perfect. Another team submitted an entry on Wed 7/2/2003 6:00 PM and hence should be considered the winners. Therefore I will today award a GrandER Prize to the team of Joseph Gregg, Chris Richards, Dan Wojcik, Ilia Izmolov, and Margeret Scholtz. I congratulate them!

Maintained by greenfie@math.rutgers.edu and last modified 8/4/2003.