The setting:
- There are 9 people.
- There are 3 locations.
- At any time, there are 3 people at each location.
- People can only swap locations at the same time.
The goal:
- Every person visits each location once.
- Every person meets each person at least once.
- At each swap, one person stays at the location.
Example:
The numbers in the table below represent which person is at which location. e.g. in iteration 1, persons 1, 2, and 3 are at location 1. All goals are met in this example, but can it be done in fewer iterations?
| Iteration | Location 1 | Location 2 | Location 3 |
|---|---|---|---|
| 1 | 1, 2, 3 | 4, 5, 6 | 7, 8, 9 |
| 2 | 4, 2, 9 | 1, 5, 7 | 3, 8, 6 |
| 3 | 4, 1, 8 | 2, 6, 7 | 3, 9, 5 |
| 4 | 4, 3, 7 | 2, 5, 8 | 1, 9, 6 |
| 5 | 5, 6, 7 | 3, 8, 9 | 1, 2, 4 |
No, it is not possible to do it in fewer iterations. There are $\binom 92=36$ pairs of people, and each round allows at most $9$ of the pairs to meet, so you need at least four rounds. However, we can show four rounds are impossible.
Without loss of generality, the first round is $123\mid 456\mid 789$. Every location needs someone to stick around for the second round, WLOG the people who remain are $1,4,$ and $7$. Since $1$ needs to visit every location, $1$ needs to visit locations $2$ and $3$ during rounds $3$ and $4$. WLOG, $1$ visits location $2$ first.
So far, we have the following partial schedule:
At some point, $1$ and $4$ need to meet. They cannot meet in round $3$, since then $4$ would only have time to visit two locations. So they must meet in round $4$. This means that the group that meets at round $4$ and location $3$ is $\{1,4,x\}$ for some $x$.
Since every round causes at most $9$ new pairs of people to meet, and there are $36$ pairs of people who need to meet, there cannot be any repetitions of pairs of people meeting, else the schedule would not be efficient enough for all pairs to meet. Since each pair of people can only meet once, $x$ cannot be $2$ or $3$ (since $1$ met $2$ and $3$ in round $1$), and $x$ cannot be $5$ or $6$ (since $4$ met $5$ and $6$ in round $1$), so $x$ must be $7$, $8$ or $9$. However, if $x$ was $7$, then $7$ would visit at most $2$ locations, so $x$ must be $8$ or $9$. WLOG, $x=8$. Let us update our partial schedule:
At last, we get our contradiction. Consider the location of $8$ in round $2$.
If $8$ is in location $1$ in round $2$, then $1$ and $8$ would meet twice.
If $8$ is in location $2$ in round $2$, then $4$ and $8$ would meet twice.
If $8$ is in location $3$ in round $2$, then $7$ and $8$ would meet twice.
There is no possible place for $8$ in round $2$, so no four-round schedule is possible.