Interview Question

Junior Trader Interview

-

Susquehanna International Group (SIG)

A bunch of people sit down at a circular table. How many combinations are there or certain people sitting down next to others?

AnswerAdd Tags

Interview Answers

4 Answers

7

It's (N-1)! There are N! ways of situating N people in a line, but since the ends are now connected we have translational invariance, i.e. person 1 could be in any of N spots. Therefore, we are actually overcounting by N, so there are N!/N=(N-1)! combinations. To Sherry, just because it works for one case, doesn't mean it's the general formula!

Anonymous on

0

I guess to guarantee that two certain people sit beside each other, we have to bundle them to each other. That means the possible combinations around the table would be (N-2)!. However, for the bundled group of two people, there is a 2! combination. Therefore the final answer would be (N-2)!*2!.

Farzi on

0

Seems incorrect. Suppose we have two people and of course they are required to sit together, there would be only 1 way to arrange which is not (2-1)!*2. To complete the process: get one of the "friends" seated on an arbitrary chair, his or her friend can be seated at the next chair either clockwise or counter clockwise if the two chairs are not identical (which is true when N=2). After this, seats are no longer indistinguishable, and the number of ways to arrange the rest of the people would be (N-2)! Hence, result =1, if N=2, and result=2*(N-2)!, if N>2. Simple check, suppose there are three people A, B, C, and A B must be together. Permutation: ABC ACB BAC BCA CAB CBA Because table is round, ABC=BCA=CAB, ACB=CBA=BAC. And in this case, both ABC and ACB allow AB sitting together. Hence, result=(3-2)!*2=2, the answer is correct.

Sherry on

0

I guess it's 2*(N-1)! ?? Thought of people sitting in a line, then it should be N!. But now it's a round table so consider the start and end position are bundled. So it's (N-1)!, but since this tie has two people so should be (N-1)! * 2.

Delusion on

Add Answers or Comments

To comment on this, Sign In or Sign Up.