1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So a "move" is an arbitrary permutation of all the $n^2$ people? $\endgroup$ – hmakholm left over Monica Apr 30 '17 at 13:02
  • $\begingroup$ Isn't $2$ the answer for $n=2$? If you start with $(A,B),(C,D)$ then let move $1$ be $(A,C),(B,D)$ and move $2$ is $(A,D),(B,C)$. Maybe you count the initial state as a move, but then for $n=1$ the answer should be $1$. Or am I misunderstanding? $\endgroup$ – lulu Apr 30 '17 at 13:13
  • $\begingroup$ @Henning Makholm: Well, it is certainly a permutation, but some permutations wouldn't be a move, e.g. rotating the position of people already at a location. $\endgroup$ – Jens Apr 30 '17 at 13:15
  • $\begingroup$ @lulu: You are right. Fixed. $\endgroup$ – Jens Apr 30 '17 at 13:16
  • 1
    $\begingroup$ @Jens It wouldn't really change the problem to consider that a move. It would just be a stupid move to do. $\endgroup$ – Arthur Apr 30 '17 at 13:39
2
$\begingroup$

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\}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fascinating stuff! Can't say I completely understand how it works, but the solution for $n=3$ is certainly given as a Steiner triple system here. Though you technically didn't provide an answer for all $n$, it's close enough. Thanks. $\endgroup$ – Jens May 2 '17 at 17:46
  • $\begingroup$ Thanks. I'm still looking into the other cases. Block design seems to be the general subject. $\endgroup$ – nickgard May 3 '17 at 5:22
  • 1
    $\begingroup$ Apropos of nothing except demonstrating weird places to end up while investigating this... a real world example for $n=4$ from speedway:https://www.pzm.pl/pliki/zg/zuzel/2015/regulaminy/65.500.04_eng_-_sgp_2015.pdf. Page 23 (page 26 of 44 in the PDF). $\endgroup$ – nickgard May 3 '17 at 19:26
  • $\begingroup$ Very nice! Looking at that chart, it appears that for $n=4$ the requirement I left out from the original question, i.e. that everyone must visit every location, is indeed fulfilled. I now wonder if this is possible for all Steiner solutions? $\endgroup$ – Jens May 3 '17 at 19:47
  • $\begingroup$ Actually, I think it's impossible for everyone to visit every location, and is why I asked the question before posting my answer. Don't be confused into thinking that the helmet colours define locations. Each heat is equivalent to a location. Locations are distinguished by whether they're the first, second, third or fourth heat in each group of four heats. This even applies for $n=2$. Try rearranging the $n=2$ system so that each letter appears at least once in the left-hand subsets and at least once in the right-hand subsets. It can't be done. $\endgroup$ – nickgard May 3 '17 at 20:08

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.