$16$ people around a round table

Question

There are $16$ people around a round table for a meeting. Every hour there is a new session. In each session, the people whose neighbors in the previous session are both sitting or standing will sit, and the people whose neighbors were in opposite state (one sits, one stands) will stand up.

how many sessions do we need to guarantee that everyone will be sitting at the table?

I tried for the case with $4$ people. The answer seems to be $3$. but I cannot generalize to $16$ people...

Answer 1

The important thing to realize is that each person's position on the next round is the XOR of the neighbors on this round. Because of the linearity of XOR, the result of having several people standing is the XOR of the results of having each of them standing. If you find how many rounds it takes with just one person standing in the first round, it will finish in at most that many rounds from any position.

I then made a spreadsheet to do the calculations. For $16$ people it takes $9$ rounds. I would guess the general rule is that for $2^n$ people it takes $2^{n-1}+1$ but I haven't proven it.

Answer 2

Here is an addition to the problem. Suppose that there are $N$ people in the meeting. I will show that it is always possible to make everybody sit at some point if and only if $N$ is a power of $2$.

The proof proceeds similarly to Ross Millikan's answer. Identify the states "sit" and "stand" as the elements $0$ and $1$, respectively, of the Galois field $F=\operatorname{GF}(2)$. Suppose that at the $k$th session, the $i$th person is in state $x^k_i$. Define $\mathbf{x}^k$ to be the column vector $(x^k_1,x^k_2,\ldots,x^k_N)\in F^N$.

Consider the $N\times N$ permutation matrix $$\mathbf{P}_N=\begin{pmatrix}0&0&0&0&\cdots&0&1\\1&0&0&0&\cdots&0&0\\0&1&0&0&\cdots&0&0\\ 0&0&1&0&\cdots&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&0&\cdots&0&0\\0&0&0&0&\cdots&1&0 \end{pmatrix}.$$ Note that that $\mathbf{P}_N^{-1}=\mathbf{P}_N^T$. Then we see that $$\mathbf{x}^k=\mathbf{A}_N\mathbf{x}^{k-1}$$ for every $k>1$, where $\mathbf{A}_N=\mathbf{P}_N+\mathbf{P}_N^T$. Hence $$\mathbf{x}^k=\mathbf{A}_N^{k-1}\mathbf{x}^1.$$ Therefore, for any starting point $\mathbf{x}^1$, $\mathbf{x}^k$ is the zero vector for some $k$ if and only if $\mathbf{A}_N$ is nilpotent.

However, $$\mathbf{A}_N=\mathbf{P}^T_N+\mathbf{P}_N=\mathbf{P}_N^{-1}+\mathbf{P}_N=\mathbf{P}_N^{-1}\left(\mathbf{I}_N+\mathbf{P}_N^2\right).$$ Since $\mathbf{P}_N^{-1}$ is invertible and commutes with $\mathbf{I}_N+\mathbf{P}_N^2$, $\mathbf{A}_N$ is nilpotent iff $\mathbf{I}_N+\mathbf{P}_N^2$ is nilpotent. However, as $$\mathbf{I}_N+\mathbf{P}_N^2=\mathbf{I}_N-\mathbf{P}_N^2,$$ we see that $\mathbf{A}_N$ is nilpotent iff $\mathbf{P}_N^2$ has only one eigenvalue $1$ in the algebraic closure $\overline{F}$ of $F$.

However, the characteristic polynomial of $\mathbf{P}_N$ is $\lambda^N-1$. Suppose that $$\lambda^N-1=\prod_{j=1}^N(\lambda-\omega_N^j)$$ for some $\omega_N^1,\omega_N^2,\ldots,\omega_N^N\in \overline{F}$. Therefore, if $p_N(\lambda)$ is the characteristic polynomial of $\mathbf{P}_N^2$, then we see that $$p_N(\lambda)=\prod_{j=1}^N\left(\lambda-(\omega_N^j)^2\right).$$

Hence $1$ is the only eigenvalue of $\mathbf{P}_N^2$ if and only if $(\omega_N^j)^2=1$ for all $j=1,2,\ldots,N$. As a result, $\omega_N^j=1$ for each $j$. That is, $$\lambda^N-1=(\lambda-1)^N.$$ This happens if and only if $N=2^n$ for some non-negative integer $n$ due to Lucas's theorem.

Suppose $N=2^n$ for some $n\geq 0$. Let $\mathbf{e}_j$ be the column vector $(0,0,\ldots,0,1,0,\ldots,0)$ where $1$ occurs at the $j$th position. We have $\mathbf{P}_N^r\mathbf{e}_j=\mathbf{e}_{r+j}$ where indices are considered modulo $N$. $$(\mathbf{I}_N+\mathbf{P}_N)^\ell\mathbf{e}_1=\sum_{j=0}^\ell\binom{\ell}{j}\mathbf{P}_N^j\mathbf{e}_1=\sum_{j=0}^\ell\binom{\ell}{j}\mathbf{e}_{j+1}.$$ For $\ell<N$, the coefficient of $\mathbf{e}_{\ell+1}$ is $1$. Therefore, $(\mathbf{I}_N+\mathbf{P}_N)^\ell\mathbf{e}_1$ is non-zero for all $\ell=1,2,\ldots,N-1$. Also, obviously $(\mathbf{I}_N+\mathbf{P}_N)^N=\mathbf{O}_N$. This means $\mathbf{I}_N+\mathbf{P}_N$ is nilpotent of index $N$.

Finally, when $N=2^n$ and $n>0$, we see that $\mathbf{A}_N^{k}=\mathbf{O}_N$ iff $$(\mathbf{I}_N+\mathbf{P}_N^2)^k=(\mathbf{I}_N+\mathbf{P}_N)^{2k}$$ is the zero matrix $\mathbf{O}_N$. By the previous paragraph, this can happen if and only if $2k\geq 2^n$ and so $k\geq 2^{n-1}$. Thus for $N=2^n$ where $n$ is a positive integer, the least number of meetings required so that it is guarantee that at the end, everybody sits is $2^{n-1}+1$.