I finally got around to watching last week’s Futurama late last night, and there’s an interesting permutations puzzle involved. The puzzle itself is a minor SPOILER, so stop now if 5 days isn’t enough time for you.

Puzzle: There’s a machine that can swap minds between bodies, but can’t swap two people if it’s already swapped that pair of bodies. A group of people use the machine to perform an arbitrary sequence of swaps among themselves. How can this group and two outsiders use the machine to restore everyone’s mind and body?

My solution is here.

I wonder if this is a recasting of a classic swapping puzzle I’m not familiar with.

“Finger multiplication” is an old trick for using the bottom-left (easier to memorize) quadrant of the times table to do multiplication in the top-right quadrant. It’s easy to work out why it works, but unsatisfying, but I found rederiving the technique gave more insight.

How might we do this? To go from one quadrant to the other, we subtract from 10, or generally from the base b: (b-x)(b-y) = b²-bx-by+xy
Well, there’s our xy term, to get it alone we want to subtract off b²-bx-by = b(b-x-y), which we can do by adding -b(b-x-y) = b(x+y-b). The factor of b is trivial to deal with, just use place value, so that leaves us with x+y-b. That’s easy enough to calculate on its own, but we can distribute the -b half to each number as (x-b/2)+(y-b/2). We have the numbers b-x and x-b/2 to do arithmetic on, these sum to b/2, the number of fingers on a hand, so if you hold up x-b/2 (x-5 for us pentadactyl folk) fingers on a hand, then the down fingers number b-x. And that’s how you do finger multiplication, hold up x-5 on one hand, y-5 on the other, put the sum of the up fingers in the tens place and the product of the down fingers in the units place et voilà.

Now that we’ve reverse engineered it for the existing use case, can we come up with something like it for others? How about the case where only one term is > 5 ?
We want to move this from the top-left to the bottom-left of the times table, so x∙(b-y) = bx-xy. So, put the smaller number in the tens place, and subtract off the product of it and the “down fingers” from the large number. 3×7? 7 has 3 down fingers, so 30-9 = 21. 4×8? 8 has 2 down fingers, so 40-8 = 32.

I’ve never seen Simpson’s paradox explained by showing the distributions, which I found to be very helpful in understanding what’s going on. So, take a look at these two distributions I made from calls to random():

The cyan distribution has a larger mean than the magenta one, but anyone worth their salt should recognize them as mixtures of unimodal distributions (indeed, that’s how I made them) and look for a binary factor to separate the subpopulations. Upon separating them, in both cases the magentas’ means are higher than the cyans’, Simpson’s paradox.

So, Vinay Deolalikar has a purported proof that P ≠ NP here. But there must be some error, because I just came up with this simple proof that P = NP !
(If you think “joke proof” sounds like an oxymoron, you can stop reading here.)

Let W(m) ➙ s be a member of NP.
Let X(m; n) ➙ s be the first n symbols of W(m). X is obviously in NP.
So, X has a verifier V(m; n; s) in P.
We can find the first symbol t₁ of an output of W(m) by trying V(m; 1; c₁), V(m; 1; c₂), … for all the symbols c_i in the alphabet.
We can find the second symbol t₂ by trying V(m; 2; t₁c₁), V(m; 2; t₁c₂), etc.
And so on for all the symbols t₃, t₄, … in the output of W(m).
Finding each symbol takes c calls to V, where c is the alphabet size, a constant. Each call of V takes polynomial time, so we can calculate each individual symbol in polynomial time.
The length of the output of W(m) is necessarily polynomial in ∥m∥, so we have a polynomial number of symbols, each calculable in polynomial time, so we can calculate the entirety of W(m) in polynomial time, so W ∈ P.
P=NP. QED

When explaining conditional probability, the “two child” puzzle is often brought in, which is too bad because it’s a terrible example. Case in point, this recent blog post by Keith Devlin.

I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have two boys.

(In a model where children’s sexes are independent and equiprobable,) he applies conditional probability to calculate the probability of them being the same sex at 1/3, in contrast to the “wrong” “intuitive” answer of 1/2. Let’s run with this 1/3 answer for a bit. The same analysis will show that if he tells us that one is a girl, the probability that the other is a girl is 1/3. He’s going to tell us either that he has a boy kid or he has a girl kid, and in both cases the probability of both children being the same sex is 1/3, so the unconditional probability of his children being same sex is 1/3, which is crazy. Where’d we go wrong?

The problem in the analysis is that him telling us he has a boy is not the same as conditioning the probability space on him having a boy. If you like calculating conditional probabilities, the proper condition to apply when he tells us he has a boy isn’t “he has a boy” but “he tells us he has a boy”. For the puzzle, we can assume he’ll be honest, so if he has two boys he’ll say he has a boy, and for two girls he’ll say he has a girl. The interesting case is if his children are mixed. Maybe he’ll say “boy” and “girl” half the time each in that case — but then, the probability of two boys turns out to be the intuitive 1/2 after all. Maybe he’ll always say “boy” then — this gives 1/3 for the quoted puzzle, as it “should”, but having the boy always trump the girl is unappealing and it’d give a 100% chance for two girls if he says he has a girl.

More importantly though, conditional probability is just trotted out there, with no consideration if it’s appropriate to the model. Is it appropriate? In the puzzle (“I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have two boys.”) a reasonable model is he picks a kid of his at random and tells us its gender. He’d say he has a boy 50% of the time, and half of that time his other kid will also be a boy, as the kids’ genders are independent. Conditional probability doesn’t enter into this model. What would be the model where conditional probability was appropriate? It’s hard to come up with one which matches the wording of the puzzle, which is why I think using this puzzle for showing how conditional probability works is a mistake.

Keith Devlin’s article goes on to analyze the new “Tuesday birthday” puzzle:

I tell you I have two children, and (at least) one of them is a boy born on a Tuesday. What probability should you assign to the event that I have two boys?

once again blindly trotting out conditional probability. But let us first ask ourselves if it’s appropriate, what the proper model is. The least surprising model IMHO is that he picks one of his kids at random and tells us that child’s day-of-week and gender. In this model, independence between the children again applies and the probability of two boys is 1/2. What model could have conditional probability apply? Conditional probability applies when the other possibilities in the probability space are removed from consideration, so that’d be something like… a majordomo at a large gathering of parents of two children flips a coin to choose a gender (boy) and spins a spinner to select a day of week (Tuesday), sends away all the parents who don’t have a Tuesday-born son, and selects one of the remaining to tell you that they have a Tuesday-born son. The conditional probability of a second son is indeed 13/27, but models where conditional probability applies to the puzzle are farfetched, so applying conditional probability is an error. In this puzzle intuition is correct after all, the proper answer is 1/2.

[Update: Keith Devlin has pre-emptively addressed some of my criticism in his next post, The Problem with Word Problems, by saying that “I tell you X” is word-problem code for “the probability space is conditioned on X”. I still don’t like equating conditioning on “X” with conditioning on “he said X”: As above, if you have “One of my two kids is a boy, therefore the probability of my children being the same sex is 1/3.” then you can’t have “One of my two kids is a girl, therefore the probability of my children being the same sex is 1/3.”. I find the embrace of this asymmetry absurd.]

In the third century BC, Archimedes calculated an amazing approximation to π, bettering the old value of 3 ¹³⁄₈₁ worked out by 17^th century Egyptians.
How did he do it? He circumscribed and inscribed a hexagon around a circle, then bisected each hexagon’s central angles to make a dodecagon, then a 24-gon, 48-gon, and finally a 96-gon. The perimeters of the polygons bound π above and below, and each pair of perimeters is related to the ones before.
Consider a pair of polygons being bisected:

If the radius AO = 1, then AB = tan α and AC = tan ½α.
If it has n sides, the outer perimeter P = 2n tan α and the new polygon has perimeter P’ = 4n tan ½α. The inner perimeter is p = 2n sin α, with the new polygon’s perimeter being p’ = 4n sin ½α.

Now, 1/P + 1/p = 1/(2n tan α) + 1/(2n sin α) = (sin α + tan α)/(2n sin α tan α) = (1 + sec α)/(2n tan α) = (cos α + 1)/(2n sin α) = (cos² ½α – sin² ½α + 1)/(4n sin ½α cos ½α) = (2 cos² ½α – 1 + 1)/(4n sin ½α cos ½α) = (1/2n) cot ½α = 2/P’
And, P’ p = (4n tan ½α)(2n sin α) = 16n² tan ½α sin ½α cos ½α = 16n² sin² ½α = p’ ²
So, we have easy ways to calculate successive perimeters from our basic hexagons, with p = 6, P = 4 √3, using only simple arithmetic and square roots.

which puts 3.1427 > π > 3.1410.

Now, Archimedes didn’t have trigonometric functions to utilize in his calculations, so he calculated the perimeters using similar triangles, a much more complicated process. But it gives the same values. He also lacked decimals, so he worked with rationals instead, producing the bounds 3 ¹⁄₇ > π > 3 ¹⁰⁄₇₁.

I recently was amused by the “song chart” meme, so decided to give it a try.

If you try and find out how you compute the distance between points on a sphere, you’ll get a bunch of sites which offer to calculate it for you if you enter the coordinates. If you search harder, you can even get the formula. But no one seems to be offering a derivation. So here you go.

First, some preliminaries. The half angle formulas give us 2 sin² ½ψ = 1−cos ψ. (Easily derivable from cos 2α = cos² α − sin² α.) The straight-line distance (cutting through the inside of the sphere) between two points on a unit sphere with an angle ψ between them is 2 sin ½ψ. (Bisect the triangle formed by the two points and the center of the sphere.) Together, these mean that the square of the straight-line distance is 2 − 2 cos ψ.

Consider A and B to be our two points we want to get the distance between, with latitudes φ_A and φ_B, and longitudes which differ by Θ. We’ll operate mostly on the disk formed by the parallel through B. The point where it intersects the pole is D, and the projection of A onto it is C. Let EB be perpendicular to DC.

The radius of the parallel through A is r_A = cos φ_A = DC; the one through B is r_B = cos φ_B = DB. Angle CDB is Θ, so EB = r_B sin Θ and ED = r_B cos Θ.
EC = CD − ED = r_A − r_B cos Θ.
BC² = EC² − EB² = r_A² − 2 r_A r_B cos Θ + r_B² cos² Θ + r_B² sin² Θ = r_A² + r_B² − 2 r_A r_B cos Θ.

AC = |sin φ_A − sin φ_B|.
AB² = BC² + AC² = r_A² + r_B² − 2 r_A r_B cos Θ + sin² φ_B − 2 sin φ_A sin φ_B
   = cos² φ_A + sin² φ_A + cos² φ_B + sin² φ_A + sin² φ_B − 2 r_A r_B cos Θ − 2 sin φ_A sin φ_B
   = 2 − 2 r_A r_B cos Θ − 2 sin φ_A sin φ_B.

If ψ is the angle AOB (which is also the along-surface distance between A and B), then
AB² = 2 − 2 cos ψ, from the “preliminaries”.
So, 1 − r_A r_B cos Θ − sin φ_A sin φ_B = 1 − cos ψ.
ψ = arccos(cos φ_A cos φ_B cos Θ + sin φ_A sin φ_B).

Everyone knows the number of ways you can choose k items out of n without replacement is _nC_k = n!/k!(n-k)!. Often forgotten is that the number of ways to choose k items from n with replacement is _n+k-1C_k. I think this is because a) it doesn’t come up as much, and b) there’s a clear intuitition behind the first formula but not so the second. So, why is the value _n+k-1C_k? Proving it with induction is a simple matter, but doesn’t shed much light.

Let’s look at it differently… We can number our items 1, 2, …, n and order the k chosen items accordingly, making a non-decreasing sequence. So the problem becomes counting the non-decreasing sequences a₁ ≤ a₂ ≤ … ≤ a_k. Turn each sequence into a bar graph, so that for n=7, k=4 the sequence [3,5,5,6] becomes

We can make the graph into a path from (0,1) to (k,n)

This path has n-1+k steps, n-1 vertical and k horizontal. Choosing one such path is choosing the k horizontal steps from the n+k-1 total, hence _n+k-1C_k.

Another way to think about it is to consider the items chosen to be bins to fill with balls: Choosing at item becomes putting a ball in the bin, and the number of balls in a bin represents how many times that item was chosen. So the problem becomes count the number of ways you can put k identical balls in n bins. Start with bin 1. At each step you can put a ball into the current bin, or move to the next bin. You’ll place balls in k of the steps, and move bins in n-1 of them, so it’s a matter of choosing the k steps out of the k+n-1 total in which to place balls.

So, can spokes help hold our Orbital (see below post) together? After all, internal tension acts mostly transverse to the centrifugal force whereas a spoke would act mostly along it. How about attaching the spoke to its opposite point on the Orbital?

Well, centripetal acceleration at a distance r from the center we already worked out to be a = r·4π²/d². If the spoke has linear density σ, then the mass of a bit of spoke Δr long would be ΔM = σΔr and have weight Δw = aΔM = r·(4π²/d²)·σΔr. So the total weight of the spoke half would be w = ∫dw = ∫r·(4π²/d²)·σdr = (4π²/d²)·σ∫r dr = (4π²/d²)·σ·(r²/2) = (2π²/d²)·σr²   (integrating from 0 to the Orbital’s radius).

The tension on the spoke just from its own weight is that of both halves, or T = (4π²/d²)·σr². This gives a T/σ of (4π²/d²)·r² just for the spoke to be strong enough to support itself. With d = 86400 s and r = 2×10⁹ m, we’d need a strength of 2×10¹⁰ m²/s², which is as much as we’d need for the Orbital to support itself with internal tension anyway! Tweaking values won’t help, as in both cases the equations work out to T/σ = a·r. I think this means that diametric spokes can only be less effective than a band at holding a spinning structure (of any size) together.

What if we add a hub? Then the tension on the spoke is halved, but we have the problem of holding the hub together. We can also vary the spoke thickness, because tension is not uniform over it: Near the Orbital, it’s only carrying the support load, but at the hub it has the load from its own weight as well. With constant specific material strength S = T(r)/σ(r) and support load s, and Orbital radius R, we get the integral equation T(r) = s + ∫_r^R dw = s + ∫_r^R r·(4π²/d²)·σ(r) dr, or σ(r)·S = s − ∫_R^r r·(4π²/d²)·σ(r) dr.

This gives the differential equation σ’(r)·S = −r·(4π²/d²)·σ(r) with initial condition σ(R) = s/S. At this point, I had to go and dust off my old math books. In standard form, the diff. eq. is σ’(r)+(4π²/Sd²)·rσ(r) = 0. This has solution σ(r) = (s/S)·exp(−A(r)) where A(r) = ∫_R^r (4π²/Sd²)·r dr = (4π²/Sd²) ∫_R^r r dr = (2π²/Sd²)·(r² − R²).

This simplifies to σ(r) = (s/S)·exp((2π²/Sd²)·(R²−r²)). At the hub r=0, so we have σ(0) = (s/S)·exp(2π²R²/Sd²). So the tension on the hub is T(0) = s·exp(2π²R²/Sd²). Kevlar has a S = 2500 MPa/(g/cm³) = 2.5×10⁶ m²/s². So, for each pound the Orbital supports, this would place exp(4000) = 10¹⁸⁰⁰ lb of tension on the hub. That’s farther beyond scrith’s capabilities than scrith is beyond ours. How about that miracle nanotube cable? S = 37 GPa/(g/cm³) = 3.7×10⁷ m²/s², so T(0)/s = exp(286) = 10¹²⁴. Trying to hold it together with a hub makes the problem much harder, not easier.