April 2011 - mathfun@mailman.xmission.com

[math-fun] Timber!
by Bill Gosper 14 Apr '11

14 Apr '11

(One of the few entries where Apple OS-X's built-in Oxford American Dictionary beats the PC MW Unabridged, which neglects the interjection. Though it does have gardyloo!, which OAD lacks.) Once Neil seemed safely distracted by Minskyspace and sliding piece puzzle enumeration, I asked him how long it took for a pole at angle alpha from vertical to fall flat onto a nonskid surface, but he recognized it immediately as just another pendulum and we didn't work out the details. Once I was safely distracted by Neil's investigations, I forgot the factor of 2 on the pendulum equation of motion, and imagined the answer would be a pretty difference of complete EllipticKs. In truth, (measuring g as >0) T==Sqrt[2/3]*Sqrt[L/g]*(2*EllipticK[Cos[α/2]^2] - EllipticF[Pi/4, Sec[α /2]^2]*Sec[α/2]) 2 L α 2 Pi α 2 α T == Sqrt[-] Sqrt[-] (2 EllipticK[Cos[-] ] - EllipticF[--, Sec[-] ] Sec[-]) 3 g 2 4 2 2 (Because a stick pendulum acts as if all its mass were 2/3 of the way to the free end.) This, of course, raises the question of whether EllipticF[Pi/4,...] has nice special values. --rwg

1 3

[math-fun] Euler characteristic puzzle
by Dan Asimov 14 Apr '11

14 Apr '11

PUZZLE: Let EC(X) denote the Euler characteristic of X. Solve for X: EC(X) = X --Dan P.S. Thanks to Evan O'Dorney for pointing out a case I had overlooked. Sometimes the brain has a mind of its own.

3 3

Re: [math-fun] Fwd: Euler characteristic puzzle
by Dan Asimov 13 Apr '11

13 Apr '11

Ah, very cute. That includes (up to homotopy) two additional solutions. --Dan Bill T. wrote: << It's true with roman numerals (considered as topological blobs on paper, and as numerals) that EC(I) = I EC(II)=II EC(III)=III >> Sometimes the brain has a mind of its own.

1 0

[math-fun] Fwd: Euler characteristic puzzle
by Bill Thurston 13 Apr '11

13 Apr '11

Sent this earlier from the incorrect address that was bounced: It's true with roman numerals (considered as topological blobs on paper, and as numerals) that EC(I) = I EC(II)=II EC(III)=III Bill Thurston On Apr 13, 2011, at 4:28 PM, Dan Asimov wrote: > I just got some perplexed requests to clarify how such a > trans-categorical equation could even mean anything. > > This is a genuine puzzle, but maybe not 100% serious. > That's all I'll say. > > --Dan > > << > PUZZLE: Let EC(X) denote the Euler characteristic of X. > > Solve for X: > > EC(X) = X >>> > > Sometimes the brain has a mind of its own. > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] Euler characteristic puzzle
by Dan Asimov 13 Apr '11

13 Apr '11

I just got some perplexed requests to clarify how such a trans-categorical equation could even mean anything. This is a genuine puzzle, but maybe not 100% serious. That's all I'll say. --Dan << PUZZLE: Let EC(X) denote the Euler characteristic of X. Solve for X: EC(X) = X >> Sometimes the brain has a mind of its own.

1 0

[math-fun] A neat video relating nature to numbers
by quad 12 Apr '11

12 Apr '11

This video will be pedestrian to most of you, and will have few mathematical things you don't already know about, but it's beautifully presented nonetheless. I like showing it to people to explain why math isn't about doing calculations or solving equations. http://vimeo.com/10584463 Enjoy! -Robert

1 0

[math-fun] Nerd wisdom of the day
by Henry Baker 11 Apr '11

11 Apr '11

I thought this was stupid, but it also made me chuckle: There are 10 kinds of people those who know binaries and those who don't.

5 4

[math-fun] A cipher challenge
by Adam P. Goucher 11 Apr '11

11 Apr '11

Dear all: I have developed a new cipher, which is an involution between strings. That is to say, the enciphering process is identical to the deciphering process. I designed the cipher to be relatively quick to encipher and decipher by a human (6 characters per minute), yet difficult to crack, even with the help of a computer. This makes it preferable over: * Vigenere and monoalphabetic ciphers, which are crackable. Certain monoalphabetic ciphers, such as Noah John Rondeau's code, can elude most people, including T. Rychlik (which is not the Linnaean name for a bacterium! : ). Nevertheless, Dave Greene cracked it in a couple of days, and I also managed it in a similar amount of time. Consequently, it is not secure enough to use for protecting secret information. * Enigma, Feistel etc., which require a machine to encipher. Moreover, the Feistel cipher only has 2^56 keys, so is within the reach of a brute-force computer search. Enigma also has inherent Achilles' heels, making it possible to decipher with computer assistance. -------- Anyway, here is a description of my crypto-system: To begin with, a key is required. The key can be any string with 32 or fewer characters; longer keys are more secure. For this example, we will use the key MATHFUN. Firstly, each alphabetic character in the key is converted into a number in the interval [1,26], like so: A = 1, B = 2, ... , Z = 26. Hence, MATHFUN = (13,1,20,8,6,21,14). This sequence is used to generate the encoding matrix. The encoding matrix is an 8 * 4 array of squares, like so: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The first number is 13, so we place 'A' in the 13th box: _ _ _ _ _ _ _ _ _ _ _ _ A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 1, so we place 'B' in the next box along: _ _ _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Then 20. 'C' goes in the box 20 spaces ahead, like so: (There is a helical-toroidal-style wrap-around effect.) _ C _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 8: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 6, so we move 6 *unoccupied* spaces ahead: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ And 21: _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ Finally, 14, so we move 14 unoccupied squares ahead and add 'G': _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ G _ _ _ _ _ _ Now, we fill in with the rest of the alphabet, starting at the top-left, and moving *vertically* downwards: H C L P T W Z F I D M Q A B ! J E N R U X . ? K G O S V Y , - Note that the 'alphabet' is augmented with " .,!?-", to make the total of 32 characters necessary. Indeed, my cipher works for any power of two, but 32 is the next power of two above 26. With each element, associate a binary string, like so: H = 00000 C = 00001 L = 00010 ... F = 00111 I = 01000 D = 01001 ... A = 01100 ... G = 11001 ... , = 11110 - = 11111 To encode a string, we separate it into blocks of five characters. Each block is encoded with a 5*5 array of bits. For example, let's consider the string GAUSS. G = 11001, so fill in the first column of a 5*5 array with 11001: G 1 _ _ _ _ 1 _ _ _ _ 0 _ _ _ _ 0 _ _ _ _ 1 _ _ _ _ And the next column with A = 01100: G A 1 0 _ _ _ 1 1 _ _ _ 0 1 _ _ _ 0 0 _ _ _ 1 0 _ _ _ Eventually, we will have: G A U S S 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 The first row, 10111, corresponds to ?: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 And 11011 corresponds to S: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 Proceeding in this manner yields: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 A 0 0 0 1 1 P 1 0 0 1 1 R So, GAUSS enciphers to ?SAPR. You can verify that ?SAPR enciphers to GAUSS, and indeed that encipherment is self-inverse in the general case. -------- Eight Enjoyable Exercises (in ascending order of difficulty): 1. Decipher CIHTXG ZYGRI BU with the key MATHFUN. (15 characters; the two spaces are important.) 2. How many possible encoding matrices are there? (Ignore the fact that certain matrices do not correspond to actual keys.) 3. Find the encoding matrix for the key FERMATSLASTTHEOREM. 4. Decipher Z?TQN with the key FERMATSLASTTHEOREM. 5. Of the 33554432 possible five-character strings, how many map to themselves? (This is irrespective of the key.) 6. Give an example of a five-character string which maps to itself with the key MATHFUN. 7. Decipher this with an unknown key: (420 characters; it is easiest to view in a monospaced font such as in Notepad.) BNXUHJIG!RFSKRDQBBFI KIOYCLOQS.SAMLPDV?UXHE,STV?IL?FVXBX.QHF N.I!RKZ?CO AFUKMIW!UKR,KYU,MVXS?E.XO,CVU?LCLI-TMXIX-K.FTVVWN C-WTI TASD!OQM ? KYYZWBN-Z-NACLGHMJYVQWSQCU GJBBOG MIOYFN?EJ U,MVXJCU.GZFFLQL.FHTOGIZUVFMORMVHCU-FBANWTJROO.I!QNTB ,.NIOC NDVZRCUNTJT,EM.FIJC-QVC!U -OA RMGOB!KMP-O!CZS,DEGMSCP VMRYAV RC,CM ?BU?IYQDSAOBLS-PAKMW!FFZCQPREY ,FU?ZWSWUP-WRDKNX,VBN- A-XPM,LKY!LRF,!I.HAIO !ILUVINO!ALEK!DLEZJ-UOQDFFGHTY DS?OCGE 8. What was the original key used for the message in exercise 7? -------- Have fun! Sincerely, Adam P. Goucher

3 2

Re: [math-fun] [uk-imo-squad] A cipher challenge
by Andrew Carlotti 11 Apr '11

11 Apr '11

Incidentally, does anyone know how to calculate the mean value of the standard deviation of set of n values if the n values are determined by a multinomial distribution. What I mean is, given a random sting of n characters of length l, is there an easy way to work out the expected standard deviation of the frequencies of the letters? (This is somewhat relevant to my attempted attack on Adam's cipher.) Andrew -----Original Message----- From: Andrew Carlotti <andrew(a)carlotti.me.uk> To: Adam P. Goucher <apgoucher(a)gmx.com> Cc: math-fun <math-fun(a)mailman.xmission.com>, uk-imo-squad(a)lists.maths.bath.ac.uk, Dave Greene <david.m.greene(a)gmail.com> Subject: Re: [uk-imo-squad] A cipher challenge Date: Sun, 10 Apr 2011 21:00:38 +0100 An interesting idea. I'm not sure about the practicalities of it - are you intending to draw out a grid for every set of five letters, or do you think it is something that you could do in your head. I think I've found one weakness already (although whether it can be put to use is another matter). There should be a positive correlation between the standard deviation of the binary digits or a character, and the standard deviation of the frequency of the character in each of the five positions mod 5. This occurs due to fact that in each of the five positions in the binary representation of a character, the two digits will usually not occur with equal probability, creating a bias towards characters with more of the more common digit, for that location in the ciphertext mod 5. That probably sounds a bit confusing, and I still need to check the technicalities. I also intend to see whether my conclusions from this are correct. (I won't say what they are here, in case someone doesn't want to know them.) Andrew -----Original Message----- From: Adam P. Goucher <apgoucher(a)gmx.com> To: math-fun <math-fun(a)mailman.xmission.com>, uk-imo-squad(a)lists.maths.bath.ac.uk, Dave Greene <david.m.greene(a)gmail.com> Subject: [uk-imo-squad] A cipher challenge Date: Sun, 10 Apr 2011 17:39:05 +0100 Dear all: I have developed a new cipher, which is an involution between strings. That is to say, the enciphering process is identical to the deciphering process. I designed the cipher to be relatively quick to encipher and decipher by a human (6 characters per minute), yet difficult to crack, even with the help of a computer. This makes it preferable over: * Vigenere and monoalphabetic ciphers, which are crackable. Certain monoalphabetic ciphers, such as Noah John Rondeau's code, can elude most people, including T. Rychlik (which is not the Linnaean name for a bacterium! : ). Nevertheless, Dave Greene cracked it in a couple of days, and I also managed it in a similar amount of time. Consequently, it is not secure enough to use for protecting secret information. * Enigma, Feistel etc., which require a machine to encipher. Moreover, the Feistel cipher only has 2^56 keys, so is within the reach of a brute-force computer search. Enigma also has inherent Achilles' heels, making it possible to decipher with computer assistance. -------- Anyway, here is a description of my crypto-system: To begin with, a key is required. The key can be any string with 32 or fewer characters; longer keys are more secure. For this example, we will use the key MATHFUN. Firstly, each alphabetic character in the key is converted into a number in the interval [1,26], like so: A = 1, B = 2, ... , Z = 26. Hence, MATHFUN = (13,1,20,8,6,21,14). This sequence is used to generate the encoding matrix. The encoding matrix is an 8 * 4 array of squares, like so: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The first number is 13, so we place 'A' in the 13th box: _ _ _ _ _ _ _ _ _ _ _ _ A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 1, so we place 'B' in the next box along: _ _ _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Then 20. 'C' goes in the box 20 spaces ahead, like so: (There is a helical-toroidal-style wrap-around effect.) _ C _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 8: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 6, so we move 6 *unoccupied* spaces ahead: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ And 21: _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ Finally, 14, so we move 14 unoccupied squares ahead and add 'G': _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ G _ _ _ _ _ _ Now, we fill in with the rest of the alphabet, starting at the top-left, and moving *vertically* downwards: H C L P T W Z F I D M Q A B ! J E N R U X . ? K G O S V Y , - Note that the 'alphabet' is augmented with " .,!?-", to make the total of 32 characters necessary. Indeed, my cipher works for any power of two, but 32 is the next power of two above 26. With each element, associate a binary string, like so: H = 00000 C = 00001 L = 00010 ... F = 00111 I = 01000 D = 01001 ... A = 01100 ... G = 11001 ... , = 11110 - = 11111 To encode a string, we separate it into blocks of five characters. Each block is encoded with a 5*5 array of bits. For example, let's consider the string GAUSS. G = 11001, so fill in the first column of a 5*5 array with 11001: G 1 _ _ _ _ 1 _ _ _ _ 0 _ _ _ _ 0 _ _ _ _ 1 _ _ _ _ And the next column with A = 01100: G A 1 0 _ _ _ 1 1 _ _ _ 0 1 _ _ _ 0 0 _ _ _ 1 0 _ _ _ Eventually, we will have: G A U S S 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 The first row, 10111, corresponds to ?: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 And 11011 corresponds to S: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 Proceeding in this manner yields: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 A 0 0 0 1 1 P 1 0 0 1 1 R So, GAUSS enciphers to ?SAPR. You can verify that ?SAPR enciphers to GAUSS, and indeed that encipherment is self-inverse in the general case. -------- Eight Enjoyable Exercises (in ascending order of difficulty): 1. Decipher CIHTXG ZYGRI BU with the key MATHFUN. (15 characters; the two spaces are important.) 2. How many possible encoding matrices are there? (Ignore the fact that certain matrices do not correspond to actual keys.) 3. Find the encoding matrix for the key FERMATSLASTTHEOREM. 4. Decipher Z?TQN with the key FERMATSLASTTHEOREM. 5. Of the 33554432 possible five-character strings, how many map to themselves? (This is irrespective of the key.) 6. Give an example of a five-character string which maps to itself with the key MATHFUN. 7. Decipher this with an unknown key: (420 characters; it is easiest to view in a monospaced font such as in Notepad.) BNXUHJIG!RFSKRDQBBFI KIOYCLOQS.SAMLPDV?UXHE,STV?IL?FVXBX.QHF N.I!RKZ?CO AFUKMIW!UKR,KYU,MVXS?E.XO,CVU?LCLI-TMXIX-K.FTVVWN C-WTI TASD!OQM ? KYYZWBN-Z-NACLGHMJYVQWSQCU GJBBOG MIOYFN?EJ U,MVXJCU.GZFFLQL.FHTOGIZUVFMORMVHCU-FBANWTJROO.I!QNTB ,.NIOC NDVZRCUNTJT,EM.FIJC-QVC!U -OA RMGOB!KMP-O!CZS,DEGMSCP VMRYAV RC,CM ?BU?IYQDSAOBLS-PAKMW!FFZCQPREY ,FU?ZWSWUP-WRDKNX,VBN- A-XPM,LKY!LRF,!I.HAIO !ILUVINO!ALEK!DLEZJ-UOQDFFGHTY DS?OCGE 8. What was the original key used for the message in exercise 7? -------- Have fun! Sincerely, Adam P. Goucher

2 1

[math-fun] "gradual" sequences
by Marc LeBrun 10 Apr '11

10 Apr '11

I¹ve been calling an integer sequence X0, X1, X2,... ³gradual² when 0 <= Xn <= n. I was wondering, is a ³standard² (or better) name for this property? Obviously the gradual sequences are closed under min, max and so on. The motivating application was to define a convention for submitting orderings of the integers for the OEIS. Gradual sequences give a natural bijection: Xn is the index of n when you sort [0..n] according to the given ordering relation. Thus 0,1,2,... gives the normal < ordering, while 0,0,0,... is the > ordering (n Xn is the inverted ordering), and so on. (Given gradual X and Y, what ordering is X min Y?) This often enables interesting orderings like lexicographic, Sharkovsky etc to be encoded as a gradual sequence in a more suggestive way than just giving some initial terms in order. Gradual sequences also appear in other contexts, so I¹d like to adopt a standard (or better) name, if there is one. Thanks! --MLB

2 1