![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
group theory and pop culture
So last night we were both in a mood to watch something not-particularly-challenging, and on a whim Turned On the Cable Box (which happens every few months in our house) and started flipping through the hundreds of channels to see if anything looked appealing. We landed on a series of back-to-back episodes of "Futurama", which we usually see only when we're staying in a motel, which hasn't happened in almost a year because covid.
One episode stands out in my mind because the resolution to the plot problems rests on a theorem of permutation theory. The professor has built a mind-swapping device, and two characters swap minds, then have second thoughts and want to swap back, but the way the device works, once a pair of minds have been swapped, that exact pair can never be swapped again. But all is not lost: they can swap through a third party: (a,b) = (a,c)(c,b)(a,c). No, wait: that repeats the (a,c) pair; maybe a fourth party? Before they can explore that possibility, the third party runs off in mid-sequence, and various other swaps happen for other motivations... eventually (IIRC) eight different characters are all in the wrong bodies, and would all like to get back home. Is this even possible?
In the penultimate scene, two black NBA players (why? because it's Futurama, of course) show up, do a bunch of figuring on a blackboard (which they still have in Futurama), and announce that no matter how screwed-up the permutation of minds and bodies, it's possible to get back to the original state with at most two "extra players". Which they do, in a dizzying montage of swaps that leaves everybody in the right body, and they all live happily ever after.
OK, so the theorem is "for any sequence of swaps on a set of n objects, there's an additional sequence of swaps (on the original set plus at most two additional objects) that inverts the original sequence, without the same swap ever appearing more than once in the combined sequence." Why is this true, and why two additional objects -- one would have expected either one or infinitely many? And how does the number of swaps grow? I guess it can't grow more than quadratically in n because there are only C(n+2,2) = (n+2)(n+1)/2 possible swaps on n+2 objects without repeating.
The n=2 case from above: (a,b) can be inverted by (a,c)(b,d)(a,d)(b,c) without violating the no-repeats rule. And it really can't be done with only one additional "player", as one can see by exhaustive search: there are only 3 possible swaps on {a,b,c}, and neither (a,c), (b,c), (a,c)(b,c), nor (b,c)(a,c) is equivalent to (a,b). (Side question: how big is this "exhaustive search"? There are only C(n+1,2) = n(n+1)/2 possible swaps, but then you have to look at all permutations of at most this many swaps... how many permutations are there of at most m objects, where m=C(n+1,2)? Let F(m) = 1 + m + m(m-1) + m(m-1)(m-2) + ... + m!; then F(0)=1, F(1)=2, F(2)=5, F(3)=16, F(4)=65, F(5)=306.... nothing obvious except that it grows at least as fast as m!. I should know this, or be able to solve it; I've taken combinatorics, thirty years ago. I'll get back to this.)
It'll be difficult to do the underlying theorem by induction because the no-repeats rule imposes a global constraint that doesn't lend itself to self-reduction. But maybe it's simpler than that: just grab the last swap in the sequence that needs to be reversed, label it (a,b), label the "extra players" c and d, do (a,c)(b,d)(a,d)(b,c) as above, and iterate. We know that nothing involving c or d was in the original sequence, so that doesn't violate the no-repeats rule, but it's not obvious that nothing involving a or b has already been used in the "undoing" sequence. We know that (a,b) doesn't appear twice in the original sequence, and if that's the only occurrence of either a or b in the original sequence, the above works, but it's likely that (a,*) and (b,*) each appears more than once in the original sequence, which could use up our allotted (a,c), (a,d), (b,c), and (b,d) swaps. I'll get back to this.
One episode stands out in my mind because the resolution to the plot problems rests on a theorem of permutation theory. The professor has built a mind-swapping device, and two characters swap minds, then have second thoughts and want to swap back, but the way the device works, once a pair of minds have been swapped, that exact pair can never be swapped again. But all is not lost: they can swap through a third party: (a,b) = (a,c)(c,b)(a,c). No, wait: that repeats the (a,c) pair; maybe a fourth party? Before they can explore that possibility, the third party runs off in mid-sequence, and various other swaps happen for other motivations... eventually (IIRC) eight different characters are all in the wrong bodies, and would all like to get back home. Is this even possible?
In the penultimate scene, two black NBA players (why? because it's Futurama, of course) show up, do a bunch of figuring on a blackboard (which they still have in Futurama), and announce that no matter how screwed-up the permutation of minds and bodies, it's possible to get back to the original state with at most two "extra players". Which they do, in a dizzying montage of swaps that leaves everybody in the right body, and they all live happily ever after.
OK, so the theorem is "for any sequence of swaps on a set of n objects, there's an additional sequence of swaps (on the original set plus at most two additional objects) that inverts the original sequence, without the same swap ever appearing more than once in the combined sequence." Why is this true, and why two additional objects -- one would have expected either one or infinitely many? And how does the number of swaps grow? I guess it can't grow more than quadratically in n because there are only C(n+2,2) = (n+2)(n+1)/2 possible swaps on n+2 objects without repeating.
The n=2 case from above: (a,b) can be inverted by (a,c)(b,d)(a,d)(b,c) without violating the no-repeats rule. And it really can't be done with only one additional "player", as one can see by exhaustive search: there are only 3 possible swaps on {a,b,c}, and neither (a,c), (b,c), (a,c)(b,c), nor (b,c)(a,c) is equivalent to (a,b). (Side question: how big is this "exhaustive search"? There are only C(n+1,2) = n(n+1)/2 possible swaps, but then you have to look at all permutations of at most this many swaps... how many permutations are there of at most m objects, where m=C(n+1,2)? Let F(m) = 1 + m + m(m-1) + m(m-1)(m-2) + ... + m!; then F(0)=1, F(1)=2, F(2)=5, F(3)=16, F(4)=65, F(5)=306.... nothing obvious except that it grows at least as fast as m!. I should know this, or be able to solve it; I've taken combinatorics, thirty years ago. I'll get back to this.)
It'll be difficult to do the underlying theorem by induction because the no-repeats rule imposes a global constraint that doesn't lend itself to self-reduction. But maybe it's simpler than that: just grab the last swap in the sequence that needs to be reversed, label it (a,b), label the "extra players" c and d, do (a,c)(b,d)(a,d)(b,c) as above, and iterate. We know that nothing involving c or d was in the original sequence, so that doesn't violate the no-repeats rule, but it's not obvious that nothing involving a or b has already been used in the "undoing" sequence. We know that (a,b) doesn't appear twice in the original sequence, and if that's the only occurrence of either a or b in the original sequence, the above works, but it's likely that (a,*) and (b,*) each appears more than once in the original sequence, which could use up our allotted (a,c), (a,d), (b,c), and (b,d) swaps. I'll get back to this.
no subject
no subject
This sounds entertaining... but I'm not going to try to solve it; I'd rather watch you. :-)
no subject
Another of my favorite questions of this sort has to do with repeating decimals. Some fractions have finite decimal expansions: 1/2 = 0.5, 1/4 = 0.25, 1/5 = 0.2, etc. while others are repeating: 1/3 = 0.33333..., 1/6 = 0.166666..., etc. One could conjecture at this point that repeating decimals consist of an initial segment and then one digit repeated infinitely, but 1/11 = 0.090909... with a period of 2, and 1/7 = 0.142856142856142856... with a period of 6. So two obvious questions are "Do all fractions have finite or repeating decimal expansions? Is everything with a finite or repeating decimal expansion expressible as a fraction?" And once those are resolved, "given a fraction m/n, is its decimal expansion finite or repeating, and if it's repeating, how many digits is its period? What periods are possible?" The questions are straightforward and accessible to a bright ten-year-old with a calculator. (That bright ten-year-old might also ask "is the answer the same in different bases?", which a moment's thought shows it isn't -- 1/7 in base 7 is 0.1 -- but one could still wonder about the periods of repetition.) The solution, as far as I know, requires group and ring theory that I learned in my third year of college, but it's conceivable that there's a solution that doesn't call for all that apparatus. It helps if you learned -- and remember -- how to do long division on paper.