1

There are n colleagues and each has a unique document.These documents need to be shared through emails. An email can be sent only to one person at a time (so no cc/bcc is allowed) although an email can have multiple documents attached. What is the minimum number of emails required to be sent so that everyone has every document. Is there a better solution than $2(n-1)$?

K.K.McDonald
  • 3,127
Amit Trivedi
  • 11
  • Hi and welcome to MSE. Please use MathJax for writing mathematical equations. What efforts have you conducted toward solving this problem? and why optimization, it is more like combinatorics to me. ā€“ K.K.McDonald Mar 18 '20 at 06:58
  • Hi. I'll keep that in mind. I worked it with 2,4,6 people and so on as a graph problem and realised that the graph had to be connected and once the vertex at the end of the chain received all the documents the same had to be sent back to other vertices so that makes $2(nāˆ’1)$ edges in total. I'm not sure though it seems as if there's a better solution. ā€“ Amit Trivedi Mar 18 '20 at 07:09

1 Answers1

2

For a document to be owned by other than the original owner, at least one email need to be sent.

Now let us use extrema principle, suppose $A$ is the first person to obtain all documents. For him to obtain other $n-1$ documents, at least $n-1$ emails need to be sent.

When $A$ first have all documents, the other $n-1$ person still have incomplete documents (since $A$ is the first to have complete documents) and at least an email to each of them is required. Another $n-1$ mails. Total is $2(n-1)$ minimum

acat3
  • 11,897