Band of thieves - escape locations if some of them are compromised

Question

I am currently reading a book in which we follow a band of 5 thieves which are about to do something big and some of them might be captured.

They would like to meet up afterwards but have to expect that some of their previously shared locations are compromised by being pried out of the caught ones of their group. All of them would know which ones of them have been caught.

While the book certainly does not solve this problem mathematically how could the band of thieves make sure the locations are distributed in a way that they can not be compromised by losing some of their group. Things that don't work:

Have each thief only know 2 locations like here:

In this case if thieves A, C and E would be caught thieves B and D would not have a shared set of locations to check anymore and could not meet up.

What about greater groups of thieves? How many locations would they have to share beforehand?

Answer 1

It seems to me that $\binom n2$ should suffice and is minimal, giving a distinct location to every pair.

Clearly you need at least that many, as it is possible that any designated pair of thieves might be the only ones standing.

To see that this number suffices, suppose a larger group, $A_1,\cdots, A_k$, of thieves survives. Then $A_1, A_2$ meet at their private spot, from which they go off to meet $A_3$ at the secret spot known only to $A_2,A_3$ (say) and so on.

To add more detail: the $n$ thieves must agree on an ordering in advance. Then, of course, every subset is ordered so the thieves all know who is $A_1$ who is $A_2$ and so on. Then, to fix a system, $A_1,A_2$ agree (in advance) to meet in their spot. And for $i>1$ $A_i$ goes to wait in the spot known to him and to $A_{i-1}$.

Should say: the rules are not entirely clear to me.

Answer 2

Given $n$ thieves, $T_1$ through $T_n$, they would need to know a separate hideout for each possible arrangement of thieves being caught or not caught, except they wouldn't need to worry about a hideout if they were all caught. For instance, if $\{T_2, T_4,T_5\}$ were caught, they would need a special hideout that everyone else knew about (so they could get there) and none of those three thieves knew about (so they couldn't give that information out).

So, in general, that is a total of $2^n-1$ different hideouts. In your example with just five thieves, they would need $31$ different places to hide.

(To make things a little simpler, the cases where there was just one successful thief wouldn't be shared among the group obviously, so that would lead to $n$ fewer cases.)

Answer 3

Let each subset of size $2$ or more have a secret location known only to that subset. For $n$ thieves, this requires $2^n-n-1$ locations.