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.
Comments Off on Permutation puzzle in Futurama
“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.
Comments Off on Finger multiplication
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.
Comments Off on 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 t1 of an output of W(m) by trying V(m; 1; c1), V(m; 1; c2), … for all the symbols ci in the alphabet.
We can find the second symbol t2 by trying V(m; 2; t1c1), V(m; 2; t1c2), etc.
And so on for all the symbols t3, t4, … 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
Comments Off on P vs. NP