How many mailmen are needed to connect all cities in a random delivery system?

[spock0149]

Hey folks,

This isn't a homework problem (I finished school years ago) so please don't move this.

Here is my problem:

I have:

n cities

x mailmen where each mailman delivers to k cities where k<n and selected at random.

Here is an example:

Lets say I have 250 cities (named according to there number). Mailman 1 drives between city 86 to city 211 (as that happens to be his route), and then goes on from city 211 (as he is already there) to city 16. These routes are selected completely randomly.

So, how many mailmen would I need so that ALL cities were connected by a mailman to all other cities.

Help request: You don't need to answer this for me, I just need guidance as to what sort of formula/stats is used for this. I have advanced math skills, but stats is very much lacking.

Any sort of guidance here is very much appreciated!

Spock

 

[Rogerio]

As the cities are selected at random, maybe there is no mailman delivering to city 1, for instance.

 

[CRGreathouse]

You need to find out how many total paths you need (actually, this isn't clear to me from the description -- does every city need to connect to every other city in one jump, or any number of jumps? Are you looking for a complete graph or a spanning graph?). Then you need to find the distribution for k given n: you say "randomly", but does that mean uniformly (k = 1, 2, ..., n are equally likely) or some other random distribution? And are the endpoints included?

Then, working from that information, you need to find how likely it is that at least one of the needed links is missing. The chance that a given path (out of P total paths) is missing is something like (1 - 1/P)^(Ma) where there are M mailmen each traveling an average of a paths. You'd then see what the chance are that every path is hit and set that equal to a sufficiently high number (0.95, perhaps).