All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Sitting rearrangement (Posted on 2019-08-13) Difficulty: 3 of 5
A group of n people sit at a circular table. They all stand and then sit back down in their original chair or in one next to it. In how many ways can this be done?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Same answer, different write up: Comment 3 of 3 |

First, let's get the answers for n=1, 2, 3, 4, 5

It is not hard to see that the answers are: 1, 2, 6, 9, 13 respectively

OK. Next, let’s talk about the Fibonacci Sequence.  The standard indexing is

(F(0) = 0)     (Sometimes this term is omitted)

F(1) = 1

F(2) = 1

F(3) = 2

F(4) = 3

F(5) = 5

F(6) = 8

With the sequence defined recursively, for n > 1, F(n)=F(n-1) + F(n-2)

-----------

Answer to the problem of a round table:

R(1)=1

R(2)=2

R(n)= F(n+1) + F(n-1) + 2, for n>2 

or equivalently:

R(n)= F(n) + 2 F(n-1) + 2, for n>2

or equivalently:

R(n) = 3 F(n-1) + F(n-3) + 2, for n>2

etc.

 This gives: R(i)=1, 2, 6, 9, 13, ... (i=1 , ...)

So, why is this the answer?

First, let's solve a simpler problem: n people are seated along one side of a rectangular table with n chairs. They are in a line so we use "L". They stand up and sit down. They can more one or no places. (The people on the ends of the table can exchange with the person next to them or not at all.)

L(n)  are the number of ways n people can rearrange (reseat) themselves on one side of the rectangular table. It is not hard to see that: 

L(1)=1, L(2)=2, L(3)=3, L(4)=5

Note that L(4) = L(3)+ L(2). Why?  Start with 3 people. Add one more person to the end. If she stays in her seat, the others can swap in L(3) ways. If she swaps with the person next to her, there are two chairs used up, and the others can swap in L(2) ways. So, L(4) = L(3) + L(2). This recursion holds for all n.  Either n-1 or n-2 people are able to rearrange:

L(n) = L(n-1) + L(n-2)

This is also the definition of the Fibonacci Sequence, except that the index is off by one. 

L(n) = F(n+1)

Now consider the round table. Three more things can happen:

The end two people can exchange seats. This adds L(n-2) = F(n-1) new possibilities for the remaining n-2 people. Also, all can rotate left and all can rotate right. Thus 2 more possibilities are added. 

So R(n) = F(n+1) + F(n-1) + 2 for n>2  

QED

(Yes, this is the exact method of B. Smith. I rewrote it for a young math student who has trouble with English, so as to be as readable as possible. Cheers - SL) 


Edited on August 26, 2019, 7:32 am
  Posted by Steven Lord on 2019-08-25 23:39:23

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information