This interesting problem appeared on the Riddler blog. Here it goes:
There are N agents and K of them are spies. Your job is to identify all the spies. You can send a given number of agents to a “retreat” on a remote island. If all K spies are present at the retreat, they will meet to strategize. If even one spy is missing, this spy meeting will not take place. The only information you get from a retreat is whether or not the spy meeting happened. You can send as many agents as you like to the retreat, and the retreat can happen as many times as needed. You know the values of N and K.
What’s the minimum number of retreats needed to guarantee you can identify all K spies? If each retreat costs \$1,000 per person, what is the total cost to identify all K spies?
To begin with, let’s assume you know that N = 1,024 and K = 17.
Here is my solution for $K=1$:
[Show Solution]
The case $k=1$
Let’s warm up with the simple case $k=1$. We’ll call $r_1(n)$ the minimum number of retreats needed to identify a single spy in a group of $n$ agents. If we choose to send $m$ of the $n$ agents on a retreat, then either a meeting took place, which means the spy is among those $m$, or no meeting took place, so the spy must be among the $n-m$ that didn’t go on the retreat. Depending on the result, we’ll either need $r_1(m)$ or $r_1(n-m)$ more retreats. We can therefore write this little (dynamic programming) recursion:
\begin{align}
r_1(1) &= 0 \\
r_1(n) &= \underset{m\in\{1,\dots,n-1\}}{\text{minimize}}\,\, 1+\text{max}\{ r_1(m), r_1(n-m) \}
\qquad\text{for }n=2,3,\dots
\end{align}The reason for the “max” is that we want a guarantee that this number of retreats will always find the spy. Therefore, we assume the spy is wherever they need to be so that it takes as long as possible to find them. From here, it’s clear that we should always split in half. Therefore,
\begin{align}
r_1(1) = 0\quad\text{and}\quad r_1(n) = 1 + r_1\bigl(\lceil \tfrac{n}{2} \rceil\bigr)
\quad\text{for }n=2,3,\dots
\end{align}Where $\lceil x \rceil$ means that we round $x$ up to the nearest integer. By inspection, we can solve this recursion and we find that:
$\displaystyle
\text{number of retreats} = r_1(n) = \lceil \log_2(n) \rceil
$
What about the cost? We can simply count the total number of retreat attendees, which we’ll call $a_1(n)$. When we split $n$ in half, we can choose to send either $\lceil \tfrac{n}{2} \rceil$ or $\lfloor \tfrac{n}{2} \rfloor$ (round up or round down) to the retreat. Both give us the same information, so we’ll choose to send fewer agents. The number of attendees therefore satisfies:
\begin{align}
a_1(1) = 0\quad\text{and}\quad a_1(n) = \lfloor \tfrac{n}{2} \rfloor + a_1\bigl(\lceil \tfrac{n}{2} \rceil\bigr)
\quad\text{for }n=2,3,\dots
\end{align}Again, by inspection, we find that the number of attendees is:
$\displaystyle
\text{number of attendees} = a_1(n) = n-1
$
Note that we could have achieved the same total cost by sending the agents one-by-one on individual retreats. By the time we’ve sent all but one agent, we must know who the spy is. However, we were asked to minimize the number of retreats, so it would be wasteful to have this many retreats.
And here is a partial solution for $K \gt 1$:
[Show Solution]
The case $k\gt 1$
The case $k=1$ was all about finding one spy. There were $n$ possibilities (each of the $n$ agents could be the spy) and each time we had a retreat, we received one bit of information (yes/no). The best we could do was use that bit to cut our possibilities by a factor of two, and this was achievable by sending half of the agents on the retreat each time.
If $k \gt 1$, we are tasked with finding $k$ spies, and there are now $\binom{n}{k}$ possibilities (choosing $k$ spies out of $n$ agents). Again, the logic is the same: the best we can hope for with one bit of information is to reduce the possibilities by a factor of two. If we call $r_k(n)$ the minimum number of retreats required to identify the spies with certainty, then this argument yields the bound:
$\displaystyle
\text{number of retreats} = r_k(n) \ge \left\lceil \log_2\binom{n}{k} \right\rceil
$
If $n=1024$ and $k=17$, this yields the bound $r_{17}(1024) \ge 122$. The question then becomes: how close can we actually come to reaching this bound? One possible approach is to be greedy: we keep track of all possible remaining subsets, then we consider all possible retreat arrangements and use the one that reduces the number of remaining subsets by as much as possible (which can never be more than than a factor of two). We continue in this fashion until we have reduced the number of possible subsets to one, and that must be our set of spies.
While this greedy approach would likely be optimal, it’s computationally intractable. There are $\binom{1024}{17} \approx 3.68\times 10^{34}$ possible subsets of spies and there are $2^{1024} \approx 1.8\times 10^{308}$ possible retreats we could arrange at every step. So there is no hope of computing the optimal greedy strategy and seeing how well it performs compared to our lower bound.
We can think of this as a game, where I’m trying to guess the spies and the adversary is trying to arrange the spies such that it’s as difficult as possible for me to guess. So this becomes a philosophical question: if I pick a split such that there is a slight advantage for my adversary to say “yes, there was a meeting”, then as long as they keep saying “yes”, the solution is recursive and easily computable. But if my adversary knows that the problem gets very hard whenever they say “no, there was no meeting”, they they might just do something “suboptimal” with the goal of running me out of memory.
Suboptimal heuristic
The greedy heuristic seems out of reach, so here is another heuristic, which was truly a team effort — discussions with my colleague Alberto Del Pia, comments on this post by Jim Crimmins, Adam, and Jason Weisman, as well as a little bit of effort on my end. The idea is to split the $n$ agents into $m$ groups of roughly equal size, where $k+1 \le m \le n$. Let’s number the groups $1,\dots,m$. Here is the plan:
- Take
- Group 1 stays home, all other groups go on a retreat.
- If there was a meeting, then Group 1 has no spies in it.
- If there was no meeting, then Group 1 has at least one spy in it.
- Return to step 1, but this time, Group 2 stays home and all other groups go on a retreat.
- Keep going in this fashion until we have identified all groups with at least one spy in them. There can be at most $k$ such groups. Merge these groups (this becomes our new $n$), discard all other groups, and repeat the entire process with the new smaller group: picking $m$, dividing into groups, etc.
Note that we do not need to try all $m$ possible retreats in each round! As soon as there are $k$ retreats with “no meeting”, then we can stop and immediately proceed to the next round, since we now know which $k$ groups contain spies. In the worst case, this won’t happen. We will always be forced to have as many retreats as possible. By the time we have done $m-1$ retreats, two things can happen:
- We have identified $k$ spies, in which case we can carry over our $k$ spy-containing groups to the next round immediately.
- We have identified $k-1$ spies, in which case we can just carry over the last group to the next round without testing it.
In either case, we only require $m-1$ retreats and we always send $k$ groups to the next round. So there is never any need to have all $m$ retreats in a given round. To see what happens at each round, note that if we divide $n$ into $m$ groups, then to figure out the group sizes, let $q$ and $r$ be the quotient and remainder, respectively, when we divide $n$ by $m$. So $n = qm + r$, with $0\le r\le m-1$. Then $n$ will be divided into $m$ groups as follows:
\[
n = \underbrace{q+\cdots+q}_{m-r} + \underbrace{(q+1) + \cdots + (q+1)}_{r}
\]But which groups carry over to the next round? Since we get to choose the order in which we schedule the retreats, and not all groups are of equal size, we can ensure that the last group (corresponding to the last retreat that never happens) is as small as possible. But it’s also possible that our $(m-1)^\text{th}$ group gets sent to the next round instead. So our best bet is to keep the two smallest groups for last. Ultimately, the worst case will see the $k-1$ largest groups and the $2^\text{nd}$ smallest group sent to the next round. Let’s call $g(n,m)$ this number. It’s somewhat annoying to compute $g(m,n)$, since it depends on the relative size of $k$ and $r$, but it’s approximately equal to $kn/m$. Here is what the recursion looks like:
\[
r_k(k) = 0\qquad\text{and}\qquad
r_k(n) = \underset{m\in\{k+1,\dots,n\}}{\text{minimize}}\,\, \left( m-1 + r_k( g(n,m) ) \right)
\]The recursion can be solved in a straightforward manner using recursion. Here is some Julia code along with the full computation of $g(n,m)$ that does the job:
nmax = 1024
k = 17
memo = -1 + zeros(Int,nmax)
# if n agents are divided into m groups, pick k-1 largest and 2nd smallest
function g(n,m,k)
# n = q*(m-r) + (q+1)*r
q,r = floor(Int,n/m), rem(n,m)
if m == k+1 # we must pick the k largest in this case
(r >= k ? k*(q+1) : r*(q+1) + (k-r)*q)
else # pick the k-1 largest and the 2nd smallest in this case
(r >= k-1 ? (k-1)*(q+1) : r*(q+1) + (k-1-r)*q) + (m-r >= 2 ? q : q+1)
end
end
function rk(n)
if memo[n] != -1
memo[n]
else
memo[n] = ( n == k ? 0 : minimum([m-1+rk(g(n,m)) for m=k+1:n]) )
end
end
rk(1024)
In the first round, we have $n=1024$ suspects. The optimal thing to do is to choose $m=43$ groups, leaving us with $407$ suspects. Then we choose $51$ groups to get down to $136$ suspects. Then choose $46$ groups again to get down to $50$ suspects. Finally, we choose $50$ groups and we’re down to $17$ suspects, which must be our spies. So the total is $(43-1)+(51-1)+(46-1)+(50-1)=186$ total retreats. Interestingly, if we use the approximation $g(n,m) \approx \lceil \tfrac{kn}{m} \rceil$, we also get the result of $186$. Together with our previously derived lower bound, we obtain:
$\displaystyle
\text{number of retreats}:\quad 122 \leq r_{17}(1024) \leq 186
$
The lower bound means that it’s impossible for any strategy to do better than this, but there may not be any strategies that are this good. The upper bound says it’s definitely possible to do this well using a particular strategy, but other strategies might do better. In this case, the ratio between our upper and lower bounds is about 1.52. This sort of ratio is used in approximation theory to quantify the quality of a proposed solution when the problem is hard to solve exactly.
How about the cost? We will approximate. For each round, in the worst case, we have $m$ retreats, where $k$ of them have meetings and $m-k$ do not. Whenever there is a meeting, the group that stayed home can be excluded forever after (since we know it contains no spies), so we don’t need to send that group on subsequent retreats. The most expensive thing that can happen is that our $k$ retreats with meetings come last. So the total number of attendees will be approximately:
\begin{align}
a(n,m) &\approx (m-1-k)\left(n-\tfrac{n}{m}\right) + \sum_{j=1}^k \left(n-j\tfrac{n}{m}\right)\\
&\approx \frac{n \left(k-k^2+2 (m-1)^2\right)}{2 m}
\end{align}So if we end up choosing $m$ groups when there are $n$ attendees, we should add $a(n,m)$ to our running count of attendees. Incorporating this using the solution found above, we obtain the result that the strategy will require sending about $65484$ attendees to retreats. At a cost of \$1,000 per attendee, this means it will cost at most \$65.48 million to find all the spies.
For the curious, here is a plot showing the maximum number of retreats required to sniff out 17 spies, as a function of the total number of agents:
As we can see, the upper and lower bounds start close together but end up spreading apart as $n$ increases.
Minimizing cost instead?
The problem statement asked us to minimize the number of retreats, which led us to 186 retreats at a cost of \$65.48 million. If instead we attempted to minimize dollars using a similar strategy of dividing into groups and keeping one group home, we can formulate a similar recursion to the one above, except this time we perform the minimization over cost rather than retreats. The result in this case is 220 retreats at a cost of \$54.46 million. This makes sense. We can lower the cost if we want, but only at the expense of adding more retreats.
Even better!
It turns out the upper bound can be reduced to $131$ by instead singling out one spy at a time! This turns out to have a much better worst-case performance than splitting the remaining agents into equally-sized groups as I described in my solution. As one might expect, the worst-case cost in dollars goes up dramatically. The solution, due to Tim Black, can be found here. It still remains to be seen whether there exists a simple strategy that can further close the gap between the lower bound of 122 and the new upper bound of 131.
Let’s assume we try groups of size 2^m to start and test all N/2^m non-intersecting groups, replacing ones that have spies on the next retreat, and discarding those that don’t. Worst case we have K groups left of size 2^m after this round. If we divide the group size in half each round, until size =1, we will have at most m+1 total rounds and the maximum total number of retreats will be R=2*k*m +N/m^2 -1. We can optimize over m and find that m=ln((Nln(2)+1)/2K)/ln(2). For N=1024, k=17, m=4 (rounded) (initial group size is 16, 64 groups) and we see a testing program like:
Total Groups Members Left
1024 64 16 272
272 34 8 136
136 34 4 68
68 34 2 34
34 34 1 17
$1,533,000.00 199
Where we subtract one from total number of tests for last round where group size is one.
This is assuming the worst case where we have k groups with spies after each round of testing.
Perhaps I’m misunderstanding, but I don’t think this strategy works. You don’t get to know whether there is spy at the retreat or not — the only information you get is whether all spies were at the retreat or not. So when no meeting takes place at the retreat, you don’t actually know whether your retreat group had any spies in it or not. It could have $0,1,\dots,k-1$ spies and all would give the same answer of “no meeting”.
So you start with all N. Then you systematically extract groups and hold a meeting opportunity. If the meeting takes place you discard the extracted group for the next retreat and move on to extracting the next group, if the meeting does not take place you replace the extracted group and move on to extracting the next group.
The reason you do this is exactly as you say. You can only get information by extracting groups and seeing if not all spies are there. If there are spies in your test group you need to replace them to test the next group.
Ah I see! I was confused because you wrote about “testing” a group of size 2^m. So what you mean by this is that you leave this group home and send everyone else to the retreat? If so then I think I follow. I’ll think about this some more and update my solution (w credit) if I can work it out!
The only twist here is that K+1 may not be the optimal number of groups to start with.
Jim is correct that Laurent’s answer is too high, and Laurent is correct that Jim’s answer is too low. Reason is that with Jim’s scenario, he is running 5 sets of retreats but only counting each participant once per retreat, when really you need at least K people at each retreat and thus need to keep re-sending people within each set.
My answer came in at 56.08 million dollars. I was wondering if I could get it even lower. Here’s how I got it: Like Jim, I’m running multiple sets of retreats, with each set of retreats having a goal of clearing some number of suspects. Each set has a number of retreats R = ceiling(N/X), where X is the number of people excluded and N is the total number of suspects. In the worst case, each of the first K-1 retreats has exactly one spy in the excluded group, the next R-K retreats feature a meeting of spies (allowing me to clear the excluded group and leave them out of all subsequent retreats), and the last retreat has exactly one spy in the excluded group. This means that I have N-X participants in each of the first K-1 retreats, and N-iK participants in each of the subsequent retreats (except the last one), where i increases from 1 to R – (K-1). For the last retreat of the set, I’m probably excluding less than X (because N/R is probably not an integer). Instead I’m excluding x’, so I have (N-(R-(K-1))X)-x’ participants. At the end of a set, I have cleared N-((K-1)X+x’) people at a cost of $1,000 per aggregate number of retreat participants. I can add up these terms for decreasing values of X until I find the X that yields the minimal cost per cleared person.
For N = 1024, I found X=26 and R=40 for a cost (33134) per clear (598) of 55.4. I now only have 426 suspects. I repeat with X=10 to get to 166 suspects, X=4 to get to 66 suspects, and X=2 to get to 34 suspects. At 34 suspects, I run 34 retreats clearing one person at a time. Total cost is 33134 + 14528 + 5564 + 1870 + 984 = 56,080 retreat participants or 56,080,000 dollars.
I minimized X for each set of retreats. My next step would be to see if slightly less efficient values of X would lead to a lower over-all cost, but since the submit deadline has past, I guess I’ll stop here. Curious to hear your thoughts on this approach.
Re-reading my post, I noticed a couple typographical errors. The phrase “only counting each participant once per retreat” should have read “only counting each participant once per set of retreats.” The statement “N-iK participants in each of the subsequent retreats” should have read “N-iX participants in each of the subsequent retreats”
I also should have been clear that the strategy was to maximize the number of people cleared of being a spy at the lowest per-clearance cost. I wasn’t sure how to mathematically do this minimization, but the numbers were small, so I wrote a snippet of code to run all the possible integer values and return the values that produced the lowest per-clearance cost.
The number of retreats in each of the phases are 40, 43, 42, 33, and 34. The phases clear 598, 260, 100, 32, and 17 people, respectively. Because each retreat within a phase would omit people cleared in earlier retreats in the phase, the number of participants per retreat goes down within the phase as I described above. The total number of retreat participants in each phase is 33134, 14528, 5564, 1870, and 984. Thus the cost is 56,080,000 dollars.
I used a greedy algorithm that assumed minimizing the cost of each phase would minimize the total cost. I have not proven that assumption to be correct, and I’m not entirely sure that it is. The question I didn’t resolve is whether paying more to clear a different number of people earlier would pay off with a lower cost to clear people later. For example, I could have cleared 644 people using 45 retreats in the first phase at the cost of paying for 36052 retreat participants. If I did that, and then used my original scheme for the remaining 380, my cost goes up to 56,309. But maybe there’s some more optimization that would be better?
Cool, yo. As proposed the idea is min(max(retreats)). What is that?
Hi – same kind of idea. Your group size / group number is just a bit non integral. So you have 26/10/4/2/1 members (I have 16/8/4/2/1, really picked just cause the numbers are integers) and your total number of retreats I see as ~193 vs 199 (maybe). Not sure if you work out the non-integer stuff what happens but really same idea! I think your 50mm is not right? I see yours as 1.737mm.
Cheers.
Jim
If you look at my optimal expression up top:
m=ln((Nln(2)+1)/2K)/ln(2).
It comes out to m=~4.4, which would be an initial group size of 21.5. I just rounded it to 4 and picked 16 because the numbers were easy!
Cheers,
Jim
Apologies to Adam he is correct about total testing costs! But I think we are close on number of retreats.
I see # of retreats with 16/8/4/2/1 as 199 and with non-integral or different (group) numbers of 21/10/4/2/1 as 194 ish.
Optimizing just over intial size of groups (see above):
m=ln((Nln(2)+1)/2K)/ln(2)
For N=1024, K = 17 gives m = 4.42, initial group size = 21.5. I just picked round numbers….
Thank you all for the insightful comments! I updated my solution to reflect the improved strategy of adaptively choosing $m$ at every step. I found a minimum of 191 retreats at a cost of \$65.6 million.
I used exact integers when computing the number of retreats, so that number should be exact, though I used an approximation to compute the cost. Some of the comments note that we can bring the cost lower… This is true, but only at the cost of having more retreats. The problem asks about minimizing retreats, not minimizing dollars. I tried minimizing dollars instead and I found 229 retreats at a cost of \$57.17 million (again using approximate cost in the minimization).
I updated my solution — comments welcome!
Thanks Laurent!
How do you like Julia compared to say, Python?
I find Julia to have more intuitive syntax (similar to Matlab), yet it’s just as fast as Python — often much faster. It’s also compatible with Jupyter notebooks, which I really like.
The main downside to using Julia, in my opinion, is that it’s still a very new language. So it doesn’t have any of the nice things that Matlab does, like a debugger or a profiler, or a decent IDE… The language is also constantly changing and there isn’t much in the way of online resources to get help.
Laurent, I think you can do slightly better by noticing that for each round with m groups you only need to organize at most m-1 retreats. The the final retreat m is unnecessary since by that time if you have not yet learned about the Kth spy meeting in that round you will automatically know that it would occur without actually holding the final retreat. So in the given example with N=1024 and K=17 the minimum number of retreats necessary to guarantee you can identify all the spies is 37+50+50+50=187.
I’m not so sure about that. When you keep a group home and send everybody else on a retreat, if there is a meeting, you can eliminate the group that stayed home, since it can’t contain a spy. If there is no meeting, then you know the group that stayed home has at least one spy in it, so you keep it around.
It’s true that if “no meeting” occurs k times, then you can stop and immediately go to the next round (and pick a new m), since you’ve definitely identified k groups with at least one spy in each. Since there are only k spies, that means each group contains exactly one spy. But what if one of your groups has two spies in it? Then there will be fewer than k retreats with “no meeting”! In fact, if after m-1 retreats you find that “no meeting” occurred fewer than k times, you still can’t conclude anything about the final retreat because you don’t know how many spies are in each of your groups.
I still don’t think you should ever hold the final m’th retreat in any round.
This is easy to see in the last round where, since there is only one agent per “group”, if you have not identified the K’th agent after the (m-1)th retreat in that round then you automatically know the final agent/m’th group is a spy.
Similarly, as you suggest assume there are two spies in one of the groups. After the (m-1)th retreat in that round it is correct that you still can’t conclude whether or not there is a spy in the last group. However, irrespective of this the optimal strategy is to keep the final group and refrain from holding the m’th retreat in that round.
In preferable configurations where, for example, you have identified (K-2) groups containing agents with still two groups remaining in the round, follow the same strategy – keep the final two groups and reduce the number of retreats held by two.
Given the goal of minimizing the number of retreats guaranteeing identification of all the spies even in the worst case configuration – I think the best you can do for certain is reduce by one the number of retreats in each round versus your solution. So for N=1024, K=17 it should never be necessary to hold more than 187 retreats.
You’re absolutely right. There is never a need to do the mth retreat; we can just skip directly to the next round. Interestingly, I obtained 186 retreats with this strategy (not 187). The difference might be because I assumed that we would order our groups such that we save the two smallest groups for last. That way, in the worst case, the $k-1$ largest groups and the $2^\text{nd}$ smallest group graduate to the next round. This makes a small difference in the outcome, since it avoids having to send the $k$ largest groups to the next round.
I updated my solution (again!) and included a plot comparing the upper and lower bounds. Thanks again for all the help and insight!
My intuition tells me that the optimal number of trips will be at least “a few” above 122.
Consider the case of N=6 agents, K=2 spies. Six choose two is 15, and 15 < 16, so the theoretical lower bound is 4 retreats. BUT, how many agents will you send on the first retreat? There is no option that guarantees the search space will be reduced to 8 or fewer possible spy pairs. The most information you can guarantee you will gain is ~0.737 bits.
Even with the much less "blocky" numbers of N=1024,K=17, the most information you can guarantee from the first retreat is ~0.9898 bits. That's a loss of 0.0102 bits, and even if you manage to keep the "waste" to such low levels for each decision, by the back of the envelope that would still tip us over 123 guesses.