This is a variation upon the Traveling Salesman Problem. We've got a greasy salesman, Harold Hill, who is going to try to con towns into buying marching band equipment. To simplify things, the n towns are represented as $K_{n}$ complete graph with the distance between each town being the same. We define a step to be the following. For each step, Hill travels to another town that he has not visited before. Each town that he has visited has another salesman come from it, going to a different random town and spreading the word that Hill is a con man. Hill will never go to a town that knows he is a con, and he will never go to a town that another salesman is going to at the same time. What is the expected number of towns that Hill will be able to visit?
For $n=2$, call the towns A and B. At $t=0$, Hill cons town A. At $t=1$, he travels to town $B$, conning them. Another salesman starts at town A. E[towns] = 2
For $n=3$ with towns A, B, and C. At $t=0$, Hill cons town A. At $t=1$, he travels WLOG to town $B$, conning them. Another salesman starts at town A. At $t=2$, Hill can only head to town C. However, the salesman at town A has a $\frac{1}{2}$ probability of going to town C, which would prevent Hill from going. Thus, E[towns] = 2.5.
For $n=4$ with towns A, B, C, and D. At $t=0$, Hill cons town A. At $t=1$, he travels WLOG to town $B$, conning them. Another salesman starts at town A. At $t=2$, Hill can head to town C or D. If the salesman goes to one of these, he goes to the other, and at that point has no more towns to go to. Probability is (2/3) and E[towns] = 3.
If the other salesman goes to town B, we say Hill goes to town C. Furthermore, as said, town B, having just been scammed by Hill, has another salesman come from it. Thus, we now have Hill at C and two salesmen at town B. Hill can only go to town D, but there is a 5/9 chance that at least one of the other two salesmen also head there, preventing him from going. Probability of Hill getting to 3 towns is (1/3)*(5/9) and probability of 4 towns is (1/3)(4/9). Thus, E[towns] = $(2/3)*3 + (5/27)*3+(4/27)*4 = 85/27 = 3.148\dots$.
The specific question that I have is to calculate E[towns] when $n = 10$. I've got a simulation running to get a decent estimation, but I would like to know if there is a better way to calculate this.