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:
- 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
- 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.)