Minimal transfer

Logic Level 3

There are 16 secret agents who each know a different piece of secret information. They can telephone each other and exchange all the information they know. After the telephone call, they both know everything that either of them knew before the call. What is the minimum number of telephone calls required so that all of them know everything?

The answer is 28.

1 solution

Brian Charlesworth
Jul 14, 2015

For $n \gt 4$ secret agents the answer is $2n - 4$ calls, as proved here .

For $n = 16$ we thus have $2*16 - 4 = \boxed{28}$ calls.

Moderator note:

Nice link. Thank you!

Thank you so much for the link! I just solved it by finding a pattern from studying n > 4 agents and finding the minimal links equation to be 2n - 4. I'm glad that there's a proof!

A Former Brilliant Member - 5 years, 10 months ago

Lol, I assumed the last bit of arithmetic would be an addition of 4 when it was actually 8 and so I missed my last chance :/ Anyway, this is how you would do it with just logic. Divide the 16 agents into groups of 4 and have them make minimal calls amongst each other (which would be 3) so that 2 people in each group would have each group's information. Since there are 4 groups, there would be 4*3=12 calls made. Then, divide the 4 groups in 2 groups of 2 groups and have two people (who each have his or her own group's entire information) call each other amongst their new groups of 2 groups of 4. Then, there are two people in each new group that have the information of their respective 8 people groups. In this process, two calls were made and therefore our total calls are now 12+2=14. Now take those 4 people who each have 8 people's worth of information and divide the group into 2 groups of 2. Have each group exchange information and we now therefore have 4 people with everyone's information after 2 more calls (which makes the total call count 16). Have each person call another person who doesn't have total information and we now have 8 people with total info (call count 16+4=20). Have each person call another and now we're done with call count at 20+8=28.

Steven Lee - 5 years, 11 months ago

All that you have shown is 28 is possible. You have not shown why 28 has to be the minimum. That is often the much harder part of such a question.

Calvin Lin Staff - 5 years, 11 months ago

Amazing question ;)

Abhishek Singh - 5 years, 2 months ago

ANSWER MUST BE 120

Pulastya Sau - 4 years, 8 months ago

That's maximum.

Abhigyan jha - 2 years ago

I’m sorry, but you are wrong. If 8 agents call each other then only 4 need to call each other next so we’re at 12 calls. Now 2 call each other and that’s 14. Now 2 need to call each other making one more call. That is 15 calls with all agents knowin what the previous one knew.

Lukas Carmen - 3 years ago

" If 8 agents call each other" -> Do you mean that each of these 8 agents calls each of the other 7 agents? IF so, there is already $\frac{8 \times 7 } { 2 } = 28$ calls.

Note that the calls do not last infinitely long. IE They make a call and exchange all of the information, stop the call, and then call another agent. In particular, we're not asking for the minimum number of edges in a graph that connects 16 vertices, which is my interpretation of your current writeup.

Calvin Lin Staff - 3 years ago

consider the equation with 2 agents then, 2*2-4=0 how can it be possible?

Aswin Satheesan - 1 year, 1 month ago

This is entirely wrong answer.

Pulastya Sau - 4 years, 8 months ago

Minimal transfer

The answer is 28.

1 solution

Moderator note:

0 pending reports