$n$ people round a circular table radius $1$m. Total distance walked by $\frac{n}{2}$ of them to the person $\frac{n}{2}$ spaces away is $\geq n\pi/2$

65 Views Asked by At

Let $n$ be an even integer $\geq 4.\ n$ people sit round a circular table with radius $1$ metre. Each person is labelled $x_0,x_1,\ldots,x_{n-1},\ $ in order counter-clockwise round the table. A number $j$ is chosen from $\{0,\ldots,n-1\}.$ They play a game where for each $k\in\{\ j\mod n,\ (j+1)\mod n,\ (j+2)\mod n,\ \ldots,\ (j+\frac{n}{2}-1)\mod n\ \},\ x_k$ walks round the table towards $x_{\left(k+\frac{n}{2}\right)\mod n}.\ $ The total distance walked depends on which $j\in\{0,\ldots,n-1\}\ $ was chosen.

Proposition: $\exists\ j\in\{0,\ldots,n-1\}\ $ such that the total distance walked is $\geq (\frac{n}{2}\pi)\ $ metres, and the max total distance walked for any $j$ equals $n\pi/2$ iff the distance walked by each $x_k$ is $\pi.$

I think this should be easy for $n=4$ by splitting into cases. However I don't see how to use induction to then solve for $n\geq 6.$ I have some ideas, like maybe for $n=4$ there are always at least two such $j'$s, but I'm not sure how to prove this. This also seems like a weird problem to me: like it should be trivial somehow.

1

There are 1 best solutions below

6
On

Let $d_i$ be the counter-clockwise distance from $x_i$ to $x_{(i+n/2)\bmod n}$.

Note that $d_i + d_{(i+n/2)\bmod n} = 2\pi$, because together they would walk around the circle once.

Consider the two partitions, each partition with $\frac{n}2$ people.

Either the total distance walked by the $\frac n2$ people $x_0,x_1, \ldots, x_{n/2-1}$ is at least $\frac n2 \pi$, i.e.

$$d_0 + \cdots + d_{n/2-1} \ge \frac{n}2\pi$$

Otherwise if $d_0 + \cdots + d_{n/2-1} < \frac n2\pi$, the total distance by the $\frac n2$ people starting from $x_{n/2}$ would be

$$\begin{align*} d_{n/2}+\cdots + d_{n-1} &= [2\pi - d_0] + \cdots + [2\pi - d_{n/2-1}]\\ &= \frac n2\cdot 2\pi - (d_0+\cdots + d_{n/2-1})\\ &> \frac n2 \pi \end{align*}$$


Preposition: the max total distance walked for any $j$ equals $n\pi/2$ iff the distance walked by each $x_k$ is $\pi.$

$\Leftarrow$: For any $j$, there are $\frac n2$ people who walks, so their total distance would be exactly $\frac n2 \pi$.

$\Rightarrow$: If the maximum total distance for any $j$ is $\frac n2 \pi$, by considering the $\frac n2$ people not selected to walk, the minimum total distance for any $j$ would also be $n\pi - \frac n2\pi = \frac n2\pi$.

Then for any person $x_i$, consider the total distances walked for the two cases $j=i$ and $j=(i+1)\bmod n$:

$$\begin{align*} \frac n2 \pi = \sum_{k = i}^{i+n/2-1} d_{k\bmod n} &= d_i + \sum_{k = i+1}^{i+n/2-1} d_{k\bmod n}\\ \frac n2 \pi = \sum_{k = i+1} ^ {i+n/2} d_{k\bmod n} &= \sum_{k = i+1}^{i+n/2-1} d_{k\bmod n} + d_{(i+n/2)\bmod n}\\ d_i &= d_{(i+n/2)\bmod n} \end{align*}$$

Together with $d_i + d_{(i+n/2)\bmod n} = 2\pi$, that shows that $d_i = \pi$.