People trade problems at math conferences for math teachers. This one, which I picked up last week, I liked a lot. See what you think.

Ten people are seated on a stage, in a row of ten seats. They get up, run around, and sit back down… and all end up in the seat they started in, or just one away from the seat they started in. How many ways could this happen?

August 13, 2009 am31 10:20 am 10:20 am

Very neat problem with a solution that took me by surprise. Maybe you should have rabbits instead of people :-)

2. August 14, 2009 pm31 4:42 pm 4:42 pm

Completely agree with the last commenter. Oh, that’s *pretty*.

For anybody here coming to check their answer: I make it 89.

3. August 14, 2009 pm31 7:29 pm 7:29 pm

I also got 89.
It took me 15 minutes winding down a completely wrong path, and then the method of attack hit me and it took me just 5 minutes to complete it. A nice problem.

4. August 14, 2009 pm31 7:44 pm 7:44 pm

And that would be it.

Any insights on method of attack? (solving a series of smaller problems was mine)

Any insights on explaining why the answer should take this particular form? (I have something inductive that I thought was cute. I’ll share it after I see some of yours.)

5. August 14, 2009 pm31 8:01 pm 8:01 pm

I first just trying to find the solution for 3 ppl, 4ppl, 5ppl — brute force. I got bored of it, and I would only find conjectures this way, and I’d still have to prove them. Then I tried to make tree diagrams to see if there was a visual pattern. I didn’t find a good one. But I then thought: recursion.

So I said: let S(n) be the ways for n people to sit down in their own chairs or the chairs next to their starting place. Let’s try to find S(n+2).

There are only two things that could happen with n+2 people.
Case I: The last person (the n+2 person) could either be in his own seat after the shuffling
Case II: The last person (the n+2) is in the second to last seat.

We simply have to find how many ways ppl could sit, assuming the last person is in his own seat, and add that to how many ways ppl could sit, assuming the last person is not in his own seat (hence in the second to last seat).

Let’s consider Case I. If the last person is in his own seat, then the remaining n+1 people have S(n+1) ways to order themselves. Easy!

Let’s consider Case II. If the last person is not in his own seat, then he must be in the n+1st seat. That means that the n+1 person is in the n+2 seat. In other words, the n+1st and n+2 nd person must have just switched places. That’s the only way that the n+2 nd person will not be in his original seat. Hence, the remaining n people have S(n) ways to order themselves.

So we know that S(n+2)=S(n+1)+S(n).

Calculating S(3)=3 and S(4)=5 by hand, you just get this recursion.

Which as @Clueless alludes, gives us Fibonacci numbers!

I guess the only thing I don’t know about my thought process is why I immediately jumped to S(n+2) and tried to calculate it, instead of S(n+1). Obviously that’s the right way to go about it, but I can’t seem to remember my thought process as to why I went straight there…

Thanks for the great problem, again. I might use it in our math club this year.

August 15, 2009 am31 3:11 am 3:11 am

The recursion approach is excellent. Here is how I did it, after some initial hemming and hawing; it’s not as slick, but I think there’s also some pay-off to its credit.

First I realized that I could frame the movements of the people in terms of swaps (two adjacent people switching seats), and that two swaps couldn’t overlap (because that would carry someone two seats from where they started). So in fancy language, disjoint transpositions.

How many ways can 0 transpositions happen? 1
How many ways can 1 transpositions happen? 9 (the lead swapper can be from any of the slots 1-9)
How many ways can 2 transpositions happen 7-triangle, or 28.

So that requires a little explanation. Put the first swap for the first two people. Then the second swap can be lead by 3-9 (which is seven people). Then slide the first swap over one, and the second swap has 6 possible leads. And so on. So the total is the seventh triangular number. This kind of counting procedure was familiar to me from previous counting problems.

And so already there’s a pattern forming and I expected to find
How many ways can 3 transpositions happen? 5-tetrahedron, or 35
Which is exactly how it turns out if you map out the cases.
And then, How many ways can 4 transpositions happen? 3-pentatope, or 15
How many ways can 5 transpositions happen? 1-hexawhatever, or 1

I actually just wrote down the names of the numbers and then looked up their values in Pascal’s triangle. Summing them, I got 89.

The pay-off, though, is that this combined with the recursive approach yields (if one was as yet unaware) a connection between (slash conjecture about) the Fibonacci numbers and Pascal’s triangle / figurate numbers!

Nice problem.

6. August 17, 2009 pm31 11:55 pm 11:55 pm

I discovered the recursion approach while doing a brute force on 3, 4, 5 seats. I agree with everyone else that this is a surprising and cool result!

7. August 18, 2009 pm31 4:57 pm 4:57 pm

I started out by doing five by hand – and very quickly the induction became obvious to me. I viewed it as follows:

The person in seat n could be person n; In which case the other seats must be (any) one of the solutions for n-1 people.

Otherwise, it can only be person n-1 in seat n and vice versa; and the other seats can be any of the solutions for n-2 people.

Fin :). (This is exactly Sam Shah’s solution rephrased, though I would hand-calculate s(1) and s(2) to base it rather than s(3) and s(4)!)

8. August 18, 2009 pm31 6:55 pm 6:55 pm

Thanks for all the replies! Indeed, each recursion has a slightly different flavor. Here’s mine.

Assume that for p people there are a(p) arrangements. Assume for p-1 people there are a(p-1) arrangements.

What will happen when we move to p+1 people?

Let’s assume, wlog, that the last person is seated rightmost. Then we have a(p) arrangements with the last person still in his correct seat. There are also arrangements with the rightmost and the next to rightmost people reversed. How many such arrangements? Well, there are p-1 people left to permute, so a(p-1).

Therefore, for p+1 people there are a(p-1) + a(p) = a(p+1) arrangements.