- #1
Swimmingly!
- 44
- 0
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
Last edited: