Imagine there is a group of 12 friends who are traveling somewhere with 3 cars. They are arguing over which person should sit in which car. What is the minimum number of times they should stop along the way and change their seats until each passenger's had a chance to sit with everybody else during the journey? The driver can't change his/her car and stays in the same car until the end. So the driver of each car can't sit with other drivers inevitably.
(Each car has room for 4 people)
I was wondering if this kind of problem could be solved by graph theory or any other algorithm.
( General case: n vehicles and (capacity of vehcile*n) people )
Let's call the drivers A, B, and C, and the passengers $1,2,3,4,5,6,7,8,9$. If we could ignore the drivers, we could make a useful diagram $$ \matrix{1&2&3\cr4&5&6\cr7&8&9\cr} $$ and then go $123\ 456\ 789$ for the first part of the journey, then $147\ 258\ 369$ for the second part, $159\ 267\ 348$ for the third and $168\ 249\ 357$ for the fourth, so with three stops every passenger has been with every other passenger (exactly once, as it happens). When we try to assign drivers to the cars, it doesn't work out as well.
Without loss of generality, we can assume the first part of the trip goes $A123\ B456\ C789$. Now, who drives $147$ for the second part? $1$ has already been with A, $4$ has been with B, and $7$ has been with C, so it shouldn't matter; let's let B drive $147$. Now $4$ has been with B twice, so if we're going to try to do the whole thing with three stops, $4$ has to go with A once and with C once.
Suppose we do $C348$ in the third part, and $A249$ in the fourth. Now $1$ has gone with A and B, so has to go with C, but we already have $C348$ in the 3rd part, so we need $C168$ in the 4th part. But now $8$ has been with C three times, so three stops won't be enough.
So let's backtrack and do $A348$ in the 3rd part, and $C249$ in the 4th. Now $1$ needs to go with C, but C is already occupied in the 4th part, so we must have $C159$ in the 3rd. But now $9$ has been with C three times, and we lose again.
So it's going to take four stops. It's not hard to work out a way to achieve this, in fact there is a fair bit of flexibility in the assignments of passengers to drivers.
As for the general problem with different numbers of cars and people, there are some theorems around, but there is also a lot of trial-and-error, as already illustrated above. "Combinatorial designs" is a good search phrase if you want to get deeper into this sort of problem.