Solving the Min Phone Calls Needed to Share Clues Problem

[Swimmingly!]

Homework Statement

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?

Homework Equations

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

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:
n____2_3_4_5_6_8__10
P(n)._1_3_4_5_9_12_16

 

[haruspex]

A list of values P(n) for n, some may be wrong:
n 2 3 4 5 6 7 8 9 10
P(n) 1 3 4 5 9 12 16

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 log₂(n) / 2 if n is a power of 2, though I haven't proved it's optimal. Fits your P(8) = 12.