Most efficient way for people along the edges of a grid to move to the center

Question

I'm considering a $2k\times 2k$ square grid ($k\in\mathbb Z^+$) with $8k$ highly rational people standing along the vertices forming the perimeter. All of these people want to go to the centre of the square. Within a unit of time, each person can either decide to stay on their vertex or walk to an adjacent vertex, however each road connecting two adjacent vertices can only have one person walking at a time. What is the most efficient way (and corresponding complexity) to get everyone to the centre if:

1. all vertices (except the centre) can only hold one person, and with two more sub-cases of a. multiple people can walk into the centre at the same time, and b. only one person can walk into centre at a time; and
2. all vertices can hold any number of people.

I first thought of the base case for the $2\times2$ grid.

• For case 1a. the people in the middle of each edge immediately move to the centre while the people on the corners move to the vertex on e.g. their right, before moving to the centre on the next step. Total time taken: $2$.
• For case 1b. the people in the middle of each edge queue to move to the centre, taking $4$ units of time, during which the people on the corners can simultaneously move to middle of the corresponding edge in the next step to populate the queue. Total time taken: $8$.
• Case 2. takes the same time as 1a. Total time taken: $2$.

However I can't figure out a way to generalise this; is it possible to do so? Maybe this involves dynamic programming? All insights are appreciated! :) (NB: I'm not too sure if this can become overly technical, so please let me know if it is and I'll migrate it to the maths stackexchange.)

Answer 1

An obvious lower bound for 1 is

The number of steps needed to get any person to one of the four spots directly feeding into the center, plus a quarter of the total number of people, $2k$, in 1a, to walk the maximum of four people into the center at each step, or the total number of people, $8k$, to walk each of them into the center in turn.

It is not hard to see that

This can actually be achieved, e.g. by subdividing into four equilateral triangles of $2k, 2k-2, \ldots,4,2$ vertices from base to top (so the center will be right above one of the top two vertices). Within this space, everybody who can moves up, the two at the extremes move inward. Repeat this for $k-1$ steps until you are in the situation above.

Graphically for $k = 3$:

The central position is indicated with a black dot, the four triangles all have a constant tone, but brighter at the initial positions.

After $k - 1$ steps, we would have

So the answers are

1a

$3k - 1$

1b

$9k - 1$

When all vertices can be multiply occupied, as @KyleParsons pointed out in the comments, no edge can be traversed by two people at a time (I had overlooked this in an earlier version).

2

a lower bound now is the number of steps needed to get the four positions around the center occupied, after which at most four can move to the center in each step. This means that we get the same answer as in 1a.