3
$\begingroup$

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

$\endgroup$

1 Answer 1

9
$\begingroup$

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$:

subdivided grid 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 after k - 1 steps

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.

$\endgroup$
5
  • 1
    $\begingroup$ I don't think your answer for (2) is correct because even though vertices can be multiply occupied, we're still restricted to one person traversing a particular segment during each time unit. $\endgroup$ Oct 21, 2021 at 17:45
  • $\begingroup$ @KyleParsons thanks, I missed that restriction! I'll edit. $\endgroup$
    – doetoe
    Oct 22, 2021 at 5:49
  • $\begingroup$ @doetoe I think it would be better if you simply edit your answer so the incorrect part is no longer shown, and credit Kyle via past errata like "thanks to Kyle, prior version of this answer incorrectly assumes that an edge can hold multiple people" $\endgroup$
    – justhalf
    Oct 22, 2021 at 6:57
  • $\begingroup$ @doetoe Hi could you sketch the equilateral triangles if possible? $\endgroup$
    – Ice Tea
    Oct 25, 2021 at 18:50
  • $\begingroup$ @IceTea I uploaded two images $\endgroup$
    – doetoe
    Oct 26, 2021 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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