## Fun little math problem

I love math and logic puzzles that seem like they could require a lot of thinking but turn out to be answerable in 30 seconds if you think about them the right way. Here’s one Jake Wildstrom recently posed that I liked:

Take a random permutation of the n integers from 1 to n. On average (that is, we’re asking for the mean), how many elements will be in their “correct positions” (e.g,. 3 in the third slot)?

Tags: math

May 17th, 2010 at 11:03 pm

1 over n. Because it’s obvious for the cases of n=1 and n=2, and pretty straightforward for the case of n=3. And because you said it was simple, so it must not be some combinatorial factorial mess that just happens to simplify down to 1/n for those 3 cases. But can I call a friend to confirm before giving my final answer?

May 17th, 2010 at 11:50 pm

I’m not sure I can concoct a more rigorous 30-second argument than:

A random element in a random permutation has a 1/n probability of being in correct position, so — cue hand-waving — with a total of n elements, the number of correct ones is expected to be n*1/n = 1.

May 18th, 2010 at 5:28 am

Heh, that is fun. It’s amazing how the hint that there’s a trick makes it easier to spot the trick.

I was going to post my answer, but on second thoughts let’s avoid spoilers.

May 18th, 2010 at 8:06 am

I’m a nonmathematician, so it’s not a spoiler if I post the answer, is it?

The answer is 1.

Of course, I figured that out by brute force, generating all the permutations for n = 3 and n = 4 and counting. Figuring out

whythe mean is 1 is the interesting part. Intuitively, it obviously has something to do with the fact that it’s easy to generate lots of permutations by leaving one digit in place and scrambling the rest. I don’t really have time right now to confirm it, but I’m guessing that all the others balance out because at any time you can take two numbers that are both in their correct positions and swap them to get two numbers that are both in their incorrect positions, balancing a two-right-numbers case against a zero-right-numbers case. With three right, you can shift-right, shift-left, reverse, reverse-shift-right and reverse-shift-left, and get one case of three right and two of zero right balanced against three of one right. (With n numbers, you canneverhave n − 1 right.) And it ends up being one of those things we learned in numerical analysis class years ago, where if you can prove that it’s true forkand you can prove thatifit’s true fork, it’s also true fork+ 1, then it’s always true.May 18th, 2010 at 9:08 am

Looks like a new interview question….

May 18th, 2010 at 10:57 am

I just wanted to point out that nanotone’s method is almost not hand-waving. There are n elements, and each one is left fixed by exactly (n−1)! permutations. So there are a total of n·(n−1)! fixed points among the n! permutations, for an average 1 each.

May 18th, 2010 at 11:20 am

My own actual 30-second solution is pretty much the same as what Mark said, just restated a little.

Of all n! permutations, 1/n of them have the correct element in the first slot, 1/n have the correct element in the second slot, etc. (of course many of these overlap but we don’t care). Summing over all slots, we get an average of 1/n * n = 1.

The key is not to worry about what any given permutation looks like and just look at the properties of the collection as a whole.

May 19th, 2010 at 1:15 pm

“Of all n! permutations, 1/n of them have the correct element in the first slot,”

But how do you know this without looking at what permutations look like?

My solution to this part of the problem involves noticing that there’s nothing special about the “correct slot”. You can just as easily ask about, say, “how many permutations are there where item X is in the Y slot”. Because there’s nothing to distinguish the slots, the answer must be the same no matter what Y is, therefore the chance that X is in the X’th slot is 1/N (because the sum of all the possible Ys must be 1).

Once you *know* that X is in the correct slot 1/N-th of the time, I wouldn’t have thought there was much interesting to say… I wasn’t even aware there was a “trick” to that part of it.

May 19th, 2010 at 1:27 pm

“Of all n! permutations, 1/n of them have the correct element in the first slot,”But how do you know this without looking at what permutations look like?

Because the first element has to have an equal chance of being in any slot, by a trivial symmetry argument. This is basically what you said too, although for me it fell below my threshold of interestingness.

Once you *know* that X is in the correct slot 1/N-th of the time, I wouldn’t have thought there was much interesting to say… I wasn’t even aware there was a “trick” to that part of it.Yeah, I guess you immediately jumped to the idea of thinking about the entire set of permutations as a collection, rather than by adding up lots of different individual rows with differing properties. That is not an obvious step to a lot of people.

Apparently our ideas of what constitutes a trick and what is obvious are complementary…

June 14th, 2010 at 11:58 am

My solution was to make things *much* more complicated than they have to be.

Look at the cycle containing 1 (of course, just talking about “cycles” in the first place means making things complicated).

There’s a 1 in N chance that the cycle consists of 1 alone (in which case 1 is fixed), and the remaining N-1 elements are expected to have another 1 fixed element by induction. There’s another 1 in N chance that the cycle contains all N elements, so there are no fixed elements. On average between these two cases (which are equiprobable) there is 1 fixed point.

The remaining probability is that the cycle contains K elements, 1<K<N, and the remaining N-K elements have an average of 1 fixed point by induction. So the overall average is to have 1 element fixed by the permutation.