[Lecture] Mathematics and Magic Tricks
Apr. 26th, 2006 03:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
magidLast night was a lecture by Persi Diaconis, sponsored by the Clay Mathematics Institute, in the ever-bizarre Stata Center at MIT.
Those who know math and/or were at the lecture, please correct anything I've gotten wrong.
He started with a card trick, taking a deck of cards, shuffling it (well, apparently shuffling it), tossing it into the audience, and having that person toss it farther back. The one who caught it cut the deck, passed it right, the next person cut, passed it right, and a third cut. Then the person with the deck took the top card, and the four people to the left took the top card when the deck passed to them. He had the people with red cards stand up, then told everyone what their cards were. Correctly.
Of course, the deck was stacked, and the shuffling was likely not that (though he wouldn't confirm this one way or the other; no giving out magician tricks), and there were only 32 cards in the deck. With 32 cards, it's stackable so that the red-black pattern is unique no matter where in the sequence it is, and this is what much of the rest of the talk was about.
Since there are only two options for card color, binary math models this situation, and it's possible to stack a deck so that for any n, each n-tuple appears only once.
Looking at the situation of 3-tuples, consider the four binary possibilities, 00, 01, 10, 11. Put counterclockwise around a circle, consider the paths from one to another. If the last digit of one is the first of the next, there's a path between them. So the path from 00 to 01 is 001, the path from 11 to 10 is 110, and so on. There are paths around the circle, through the middle of the circle to opposite sides, from 00 to itself (000), and from 11 to itself (111). This generates all the three-digit binary numbers. And each 2-digit vertex has the same number of paths in (in-degrees) and out (out-degrees). So much easier with a diagram; I don't have the energy to figure out how to make non-text.
Eulerian circuit theorem: A connected graph with all in-degrees equaling out-degrees has a path traversing each edge only once.
So there's a path that connects all the 2-digit binary numbers, and traversing the path generates a binary string that includes all the 3-digit binary numbers (if you loop around). So there's a way to stack a deck of 8 (23) cards so that you can know what each card is given the pattern of red/black. Cutting the deck makes no difference, since it's a looping string.
Similarly, a path can be made for all the 4-digit binary numbers, making a binary string that includes all the 5-digit binary numbers, which makes stacking a deck of 32 (25) appropriately to be able to tell, given which cards are red/black, what the cards are. Neat.
These strings are called de Bruijn sequences, and there are a lot of interesting applications of them.
About here is where things started to go faster than I could quite absorb, so my notes aren't quite as clear.
One can make a rule to generate strings. For example, for k = 4, xn = xn - 1 + xn - 4 (All of this mod 2). Starting with 0001, this generates all the 4-digit binary numbers in a long string (except 0000, since that would kill the generating rule). The associated polynomial for this rule is f(x) = 1 + x2 + x4. This polynomial is primitive if it divides 1 - x2^k - 1 but not 1 - xany exponent smaller than that.
There's a number, Euler's phi, which is (2k - 1)/k.
And what we did with this, I don't remember. Probably because it was moving quickly over very unfamiliar ground.
Theorem: Given a length k, there are 22 ^ (k - 1) - k de Bruijn sequences.
This lead to discussion of universal cycles, with four applications.
He's an excellent speaker, very engaging. I'm still wondering how much the magicians in the audience got out of the more intricate math bits, though.
ETA, (2020)
Now I'm starting to think about how to stack non-standard decks, like the 0-10 five-color Lost Cities deck (if one handshake/multiplier is left in per color), or half of a Gang of Four three-color deck. Hmmmm.
Those who know math and/or were at the lecture, please correct anything I've gotten wrong.
He started with a card trick, taking a deck of cards, shuffling it (well, apparently shuffling it), tossing it into the audience, and having that person toss it farther back. The one who caught it cut the deck, passed it right, the next person cut, passed it right, and a third cut. Then the person with the deck took the top card, and the four people to the left took the top card when the deck passed to them. He had the people with red cards stand up, then told everyone what their cards were. Correctly.
Of course, the deck was stacked, and the shuffling was likely not that (though he wouldn't confirm this one way or the other; no giving out magician tricks), and there were only 32 cards in the deck. With 32 cards, it's stackable so that the red-black pattern is unique no matter where in the sequence it is, and this is what much of the rest of the talk was about.
Since there are only two options for card color, binary math models this situation, and it's possible to stack a deck so that for any n, each n-tuple appears only once.
Looking at the situation of 3-tuples, consider the four binary possibilities, 00, 01, 10, 11. Put counterclockwise around a circle, consider the paths from one to another. If the last digit of one is the first of the next, there's a path between them. So the path from 00 to 01 is 001, the path from 11 to 10 is 110, and so on. There are paths around the circle, through the middle of the circle to opposite sides, from 00 to itself (000), and from 11 to itself (111). This generates all the three-digit binary numbers. And each 2-digit vertex has the same number of paths in (in-degrees) and out (out-degrees). So much easier with a diagram; I don't have the energy to figure out how to make non-text.
Eulerian circuit theorem: A connected graph with all in-degrees equaling out-degrees has a path traversing each edge only once.
So there's a path that connects all the 2-digit binary numbers, and traversing the path generates a binary string that includes all the 3-digit binary numbers (if you loop around). So there's a way to stack a deck of 8 (23) cards so that you can know what each card is given the pattern of red/black. Cutting the deck makes no difference, since it's a looping string.
Similarly, a path can be made for all the 4-digit binary numbers, making a binary string that includes all the 5-digit binary numbers, which makes stacking a deck of 32 (25) appropriately to be able to tell, given which cards are red/black, what the cards are. Neat.
These strings are called de Bruijn sequences, and there are a lot of interesting applications of them.
- repeated measurements: when asking people for data (comfortable loudness over the telephone, for instance), it's known that in a sequence of questions, the answer to the previous question can influence the answer to the current question. Using a de Bruijn sequence for the questions helps control for this effect.
- cryptography: put the message into binary, then add a corrupting string mod 2 (ie binary) to encrypt it. (Bleh; I'm missing a mental link here.)
- robot vision: instead of having a robot ping central computers to figure out its location, put a de Bruijn sequence of two colors along the path, and it can figure it out for itself. If it's moving on a surface, not a line, there are 2-D patterns so it can do the same thing.
- breaking and entering: there are combination-type locks with five buttons, 1-5, that require a 3-digit code to enter. If the three digits pressed aren't right, try one more, and the last two digits of the first attempt are 'remembered' by the lock. Apparently thieves got quite quick at trying the combinations...
- reading rain gauges, signal processes
- DNA: helping to reconstruct long sequences of DNA after they've been snipped up for study/testing.
About here is where things started to go faster than I could quite absorb, so my notes aren't quite as clear.
One can make a rule to generate strings. For example, for k = 4, xn = xn - 1 + xn - 4 (All of this mod 2). Starting with 0001, this generates all the 4-digit binary numbers in a long string (except 0000, since that would kill the generating rule). The associated polynomial for this rule is f(x) = 1 + x2 + x4. This polynomial is primitive if it divides 1 - x2^k - 1 but not 1 - xany exponent smaller than that.
There's a number, Euler's phi, which is (2k - 1)/k.
And what we did with this, I don't remember. Probably because it was moving quickly over very unfamiliar ground.
Theorem: Given a length k, there are 22 ^ (k - 1) - k de Bruijn sequences.
This lead to discussion of universal cycles, with four applications.
- A variant on the original card trick, again having five people take the top card (after whatever cutting, etc), but this time having the person with the highest card, second highest card, then third highest card stand up (wave a hand, whatever). Just as there can be stacking to make unique red/black patterns, one can stack the deck to have unique high-medium-low patterns within any five-card span.
- Bell numbers: the number of ways to put n things into partitions. For 3 things, there are 5 ways: (1)(2)(3), (12)(3), (1)(23), (13)(2), or (123). This goes up very quickly, since the Bell number for 5 things is 52... which of course leads to thoughts of card tricks. In this case, have the five people cluster by suit, after stacking the deck appropriately, of course. (This means taking one card out of the deck, to be a 51-card deck, because there's no possibility of a partition with the five people all separate, there being four suits.)
- 2-D binary square, where all the 2-squares are unique within the 4-square (including wrapping side-to-side and top-to-bottom (ie, making it a sphere)):
1101
0001
1000
1011 - A multiplying situation, arranging the deck so that the color pattern and the high-medium-low pattern for three cards is unique. This allows for a 48-card deck, being the number of ways there can be high-medium-low (= 3(2)(1) = 6) times the number of ways there can be red/black (= 23 = 8). (Or, for k-tuples, it requires a deck of k!2k cards.
He's an excellent speaker, very engaging. I'm still wondering how much the magicians in the audience got out of the more intricate math bits, though.
ETA, (2020)
Now I'm starting to think about how to stack non-standard decks, like the 0-10 five-color Lost Cities deck (if one handshake/multiplier is left in per color), or half of a Gang of Four three-color deck. Hmmmm.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-04-26 07:16 pm (UTC):(
I was busy last night, but I've literally tried to go to a Persi Diaconis lecture on-and-off for the last 10 years. I can't believe I missed a chance to do so.
Disappointedly,
Hyoun
no subject
Date: 2006-04-27 12:19 am (UTC)At least you had plans, rather than having a lazy night at home or something...
I hope it works out soon, hopefully this year.
no subject
Date: 2006-04-26 11:17 pm (UTC)The SST, though, commented afterwards that now she understood why Charlie Brown's teachers always said "Wa wa wa wa wa wa". :-)
no subject
Date: 2006-04-27 12:21 am (UTC)Does the SST have more of a humanities background...?
Good to see you. And on a school night, even :-)