7 Students, 7 Exercises: Min Phone Calls Needed?

[jmprada]

7 University students have to solve 7 hard exercises. In order to save time, they have decided to share them, so that each of them solves exactly one exercise. Then they will communicate via telephone, so as to share the solutions to the rest of the exercises. What is the minimum number of phone calls they need to exchange, so that each student has all 7 solutions? Note that each phone call is exactly between 2 students only (and they cannot communicate by any other means).

 

[Opalg]

7 University students have to solve 7 hard exercises. In order to save time, they have decided to share them, so that each of them solves exactly one exercise. Then they will communicate via telephone, so as to share the solutions to the rest of the exercises. What is the minimum number of phone calls they need to exchange, so that each student has all 7 solutions? Note that each phone call is exactly between 2 students only (and they cannot communicate by any other means).

Suppose that one of the students acts as a coordinator. She phones each of the other six in turn to obtain their solutions. Once she knows all the answers, she can then phone each of the others again to give them the solutions. That gives 12 calls in all. But by a very small adjustment you can reduce the number to 11.

I don't know if that is the best possible strategy, but it gives you a starting point to test other strategies against.

 

[Evgeny.Makarov]

This is called the gossip problem, and the minimum number of calls is $2n-4$ where $n$ is the number of students. This number is achieved with four coordinators.