10
$\begingroup$

You have n students sitting in a line and you want to move them so that no student is sitting next to anyone they were originally sitting next to. What is the minimum total distance the students have to move to achieve this?

Say the students start at desks numbered 1 to n, all those desks have be filled with students at the end.

Clearly this isn't possible if n is very small so you can assume n is sufficiently large.

$\endgroup$
  • 2
    $\begingroup$ Note that $n=4$ is sufficiently large: $2,4,1,3$. $\endgroup$ – noedne May 13 '18 at 9:20
  • $\begingroup$ Of course, if the students were sitting in a line, one behind the other, they would not need to move at all. $\endgroup$ – Lee Leon May 14 '18 at 12:57
8
$\begingroup$

Here's a first attempt at a bound. I claim that:

For $n = 5k$, we may attain $6k$ total distance. (This also holds true for $n = 5k-1, 5k+1$ with minor modifications.)
To do this, we may partition in groups of 5, ordering the students $5a+1, 5a+2, 5a+3, 5a+4, 5a+5 \rightarrow 5a+1, 5a+3, 5a+5, 5a+2, 5a+4$. This requires these students to move a total distance of $6$, and furthermore two properties hold - first, within a group, no student sits next to each other, and second, since at least one of the two students at the ends moves away from the ends, there is no chance that we get an invalid matching between groups.

Finally, to describe our minor modifications:

$n = 5k-1$: We can attain $6k$: Delete the first student, shift everyone else down.
$n = 5k+1$: We can attain $6k$: simply add student $5k+1$ at the end.
$n = 5k+2$: We can attain $6k+2$: Add student $5k+2$ at the end, and then swap students $5k+1$ and $5k-1$. (e.g. $135246$ becomes $1352647$.)
$n = 5k+3$: We can attain $6k+4$: Add student $5k+3$ at the end. Now we have $13526478$. Swap students $5k-1$ and $5k+2$. Now we have $13526748$. Swap students $5k$ and $5k+1$, a zero-cost swap since it brings student $5k$ closer. Now we have $13625748$, and we are done.

$\endgroup$
  • $\begingroup$ Very interesting. $\endgroup$ – Anush May 13 '18 at 16:18
  • $\begingroup$ this bound holds for $n \in [4, 19], my program is too slow to quickly prove anything larger $\endgroup$ – micsthepick May 15 '18 at 23:44
  • $\begingroup$ not bad for a first attempt $\endgroup$ – micsthepick May 15 '18 at 23:45
1
$\begingroup$

An easy lower bound:

For $n$ students, there must be at least $\frac{1}{2}n$ moves (rounded up).

Because

For any pair of neighbours, at least one of them has to move.

We can improve this:

For $n$ students, there must be at least $\frac{2}{3}n$ moves (rounded up).

Because

As we have seen, there are at least $\frac{1}{2}n$ students that move at least one seat. Let's temporarily remove all non-moving students from the game (taking their seats with them), and join all remaining seats together. From left to right, create groups of three students.

Now,

Each remaining student is going to move at least one place (otherwise they would be non-moving). Send each student exactly one seat in their intended direction, allowing two students to sit on each other's lap if they have to. In each original group of three students there are now two students, called A and B, that ended up next to each other.

There are three possibilities:

1. A and B were neighbours before the removal of the stationary seats, and no seat was removed between their two new positions. This means that one of them has to move at least one more seat before the game ends, since they cannot end up next to each other.

or

2. A and B were neighbours, and at least one seat was removed between their two new positions. This means that either A or B (or both) has actually moved two seats already.

or

3. A and B were not neighbours. In this case, before the removal of seats, a third person C was sitting between A and B. This means that either A or B (or both) has actually moved two seats already.

In all cases,

This group of three has to make at least four moves during the game. Taking all groups together, we find that the total number of moves is at least $\frac{1}{2} n \cdot \frac{4}{3}= \frac{2}{3} n$. (If the final group only has one or two members, we can draw the same conclusion.)

$\endgroup$
  • 1
    $\begingroup$ A diagram would have been useful. $\endgroup$ – Fons May 13 '18 at 19:49
  • $\begingroup$ That's a nice lower bound. $\endgroup$ – Anush May 13 '18 at 20:22
  • 4
    $\begingroup$ There's a trivial lower bound of about $n$ moves for $n$ students by splitting into groups of $4$ consecutive students and noting that it takes at least $4$ moves to separate such a group. $\endgroup$ – noedne May 13 '18 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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