0
$\begingroup$

Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair. My attempt For example, if there are 4 players sitting around a circular table there can be 9 distinct arrangements.

  1. F1,F2,F3,F4
  2. F2,F1,F3,F4
  3. F2,F1,F4,F3
  4. F4,F2,F3,F1
  5. F1,F3,F2,F4
  6. F1,F2,F4,F3
  7. F4,F1,F2,F3
  8. F2,F3,F4,F1
  9. F4,F3,F2,F1

Now, I am stuck here. How can calculate this and what about larger values of N such as 50?

I tried using vectors and pushing back every element and do the reverse operators and swap elements but I am not sure whether this is correct or not.

$\endgroup$
10
  • 2
    $\begingroup$ Do you want to enumerate the arrangements or simply get the number? What have you tried? $\endgroup$ Jan 4, 2021 at 20:34
  • $\begingroup$ Can you credit the source where you originally encountered this task? $\endgroup$
    – D.W.
    Jan 4, 2021 at 20:36
  • 1
    $\begingroup$ @D.W. No I cant this is a competetive programming question that was asked in a contest $\endgroup$ Jan 4, 2021 at 21:59
  • 1
    $\begingroup$ Is the contest currently ongoing? When was the deadline for the contest? What prevents you from providing a link and/or reference to the programming contest? Sometimes helping us see the original statement of the question helps us understand what you are asking better. Also, please don't leave clarifications in the comments (such as regarding enumerating vs counting): instead, edit the question to clarify it. $\endgroup$
    – D.W.
    Jan 4, 2021 at 22:08
  • 1
    $\begingroup$ Please edit the question to make it clear whether the desired chairs of different players can be the same or not. $\endgroup$
    – John L.
    Jan 6, 2021 at 6:09

1 Answer 1

1
$\begingroup$

Consider the variant of the problem in which the people are arranged in a segment instead of circle and let $S(n)$ be the number feasible arrangements for $n$ people.

Now lets go back to your original problem, and let's name $C(n)$ the number of feasible arrangements of $n$ people.

Clearly $C(0)=C(1)=1$ and $C(2)=2$, so we will henceforth suppose that $n \ge 3$.

Let's name the people $p_1, \dots, p_n$ where the assigned position of $p_i$ is $i$. If $p_1$ is sitting in position 1 then the number of possible arrangements of $p_2, \dots, p_n$ is exactly $S(n-1)$. Otherwise, $p_1$ is sitting either in position $2$ or in position $n \neq 2$. We will only consider the former case since the latter one is symmetric. Clearly $p_2$ cannot sit in position $2$, so he/she must either sit in position $1$ or in position $3$. If $p_2$ is sitting in position $1$, then the number of possible arrangements of $p_3, \dots, p_n$ is exactly $S(n-2)$. Otherwise, $p_2$ must be sitting in position $3$, which means that $p_3$ must be sitting in position $4$ (since position $2$ and $3$ are occupied) and, in general, $p_i$ must be sitting in position $(i \bmod n) + 1$. Since this completely determines everyone's position, this case only contributes $1$ to the total number of configurations.

To summarize, we have that: $$ C(n) = S(n-1) + 2(S(n-2)+1) = S(n-1) + 2S(n-2) + 2. $$

We are left with figuring out what $S(n)$ is. Clearly $S(0) = S(1) = 1$, so we consider $n \ge 2$. In this case $p_1$ can only sit in position $1$ or $2$. If $p_1$ is sitting in position $1$ then there are $S(n-1)$ possible arrangements of $p_2, \dots, p_n$. If $p_1$ is sitting in position $2$, then $p_2$ must be sitting in position $1$ (as it is the only other person that can sit there) and there are $S(n-2)$ possible arrangements for $p_3, \dots, p_n$. We hence have: $$S(n) = \begin{cases} 1 & \mbox{if } n \in \{0,1\} \\ S(n-1) + S(n-2) & \mbox{otherwise} \end{cases} = \mathcal{F}_{n+1},$$ where $\mathcal{F}_{i}$ denotes the $i$-th Fibonacci number. Substituting back, we obtain:

$$ C(n) = \begin{cases} 1 & \mbox{if } n \in \{0,1\} \\ 2 & \mbox{if } n = 2 \\ \mathcal{F}_n + 2 \mathcal{F}_{n-1} + 2 & \mbox{otherwise} \end{cases}. $$

$\endgroup$
2
  • $\begingroup$ we can also say that C(n) = F_(n+1) + F_(n-1) + 2 since C(n) = S(n) + S(n-2) + 2 $\endgroup$ Jan 6, 2021 at 13:51
  • $\begingroup$ Sure, they are equivalent :) $\endgroup$
    – Steven
    Jan 6, 2021 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.