1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Minimum Combinations problem, n detectives with unique clues. Min. no. of phonecalls?

  1. Dec 27, 2012 #1
    1. The problem statement, all variables and given/known data
    We have n detectives. At the start each has a single unique clue.
    The aim is for all the n detectives to obtain all the n clues.
    If detective A knows clue 1 and 33; and B knows, 1, 2 and 4. If A phone calls B they share their clues. i.e. A will know 1, 2, 4 and 33 and B the same.

    Q: Whats the minimum number of phone calls for all detectives to know all clues?

    2. Relevant equations
    P(n)= minimum number of phone calls for n detectives.

    3. The attempt at a solution
    I represent this with a polyhedra with n vertices, and with links representing calls.
    A simple strategy is for A to call (n-1) people, then go in reverse order and call (n-2) people.
    P(n)≤ (n-1)+(n-2) =2n-3

    For a value under I use a bit of a guess of something that grows fast. Like this. So if we have 8 we get to 2 knowing all with 1+2+4 calls. 1+2+4=8-1 Therefore P(n)>n-1. (n≠2)

    How to solve:
    Find an algorithm for round numbers (2^m or even 2m). Introduce corrections for non round numbers.
    Prove the algorithm is the best with symmetry arguments mainly.
    This works I think but it looks a bit extensive.

    One algorithm I use is basically:
    Divide the people into n/2 pairs, with the left L and the right R person of pair p.
    Link L of pair p with R of pair p+1.
    Link L of p with R of p+2.
    Repeat: Link L of p with R of p+k. Repeat until all know all.

    For odd numbers an easy fix that's not necessarily the optimal is this: Take A away to make it an even group. Link A with a random element. Run even algorithm. Link A again with a random element.

    A list of values P(n) for n, some may be wrong:
    Last edited: Dec 27, 2012
  2. jcsd
  3. Dec 27, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: Minimum Combinations problem, n detectives with unique clues. Min. no. of phoneca

    I couldn't figure out that list until I 'quoted' it. That revealed gaps at 7 and 9.
    The suggestion to look at powers of 2 is a good one. That reveals an alogorithm that takes n log2(n) / 2 if n is a power of 2, though I haven't proved it's optimal. Fits your P(8) = 12.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook