Minimum moves needed for everyone to meet

235 Views Asked by At

There was an interesting question here a few days ago which now seems to have disappeared. Here is my version:

There are $n$ different locations with $n$ people at each location. In a move, people can move from their current location to any other location, as long as the number of people leaving a location equals the number of people entering that location.

If people only meet each other when they are together at a location, what is the minimum number of moves needed for everyone to have met everyone else?

For $n=1$ the answer of course is $0$ moves. For $n=2$ the answer is $2$ moves. But what's the answers for larger $n$?

EDIT

I thought it might be helpful to find lower and upper bounds of the minimum moves $M$. We know that the total number of unique meetings we need is:

$$\binom{n^2}{2}=\frac{n^2(n^2-1)}{2}$$ In a given location there are $n$ people and if they all meet each other for the first time, there will be $\binom{n}{2}$ new meetings. Assuming this is the case for all $n$ locations, a "perfect" move would give $$n \binom{n}{2} =\frac{n^2(n-1)}{2}$$ new meetings. Assuming every move is perfect and remembering that the initial placement of people is itself perfect, a lower bound for $M$, where $n \gt 1$, would be $$L(M) = \frac{\binom{n^2}{2}-n \binom{n}{2}}{n \binom{n}{2}}=n$$

To find an upper bound, let us look at a method of generating all meetings using $n=3$ as an example.

enter image description here

We start with $3$ people at each of our locations A, B and C. We now move the first person at each location to its neighbouring location to the right (wrap around at C). We do this twice. At this point, persons $1$, $4$ and $7$ have met everyone except each other. Using the starting configuration as reference, we now do the same moves but with the second person at each location. At this point, persons $2$, $5$ and $8$ have met everyone except each other. We then do the same thing again, but with the third person at each location. At this point, persons $3$, $6$ and $9$ have met everyone except each other. In the final move, we move the people who have not yet met together.

Generalizing from this example we see that an upper bound for $M$ would be: $$U(M)=n(n-1)+1$$

1

There are 1 best solutions below

7
On BEST ANSWER

We can create a Steiner System $S(2,n,n^2)$ for any $n$ where an affine plane exists. By the definition of a Steiner Sytem, each unique pair of elements will appear exactly once.

Each person needs to meet $n^2-1$ others. They will meet $n-1$ other people after each move. $n^2-1=(n-1)(n+1)$ so the Steiner System will consist of $n+1$ sets of $n$ blocks, each block containing $n$ elements. This corresponds to $n$ moves from the starting position.

Here is the system for $n=2$: $$\{AB\}\{CD\}$$ $$\{AC\}\{BD\}$$ $$\{AD\}\{BC\}$$ However, such systems do not exist for all $n$. An affine plane exists iff a projective plane of the same order exists. It is known that a projective plane exists for all orders that are a power of a prime: $2, 3, 4, 5, 7, 8, 9, 11,\dots$ (OEIS A000961 without the first term). It is conjectured but not proven that these are the only orders for which a projective plane exists. It has been proven that projective planes do not exist for orders $6$ and $10$.

I don't know the best configurations for the values of $n$ not covered above.

As a further illustration, here's a solution for $n=3$: $$\{ABC\}\{DEF\}\{GHI\}$$ $$\{ADG\}\{BEH\}\{CFI\}$$ $$\{AEI\}\{BFG\}\{CDH\}$$ $$\{AFH\}\{BDI\}\{CEG\}$$