In 1996, Jon Haugsand posted the Paranoid Spy problem on rec.puzzles. I decided recently to revisit my solution to that problem.
In short, the spy has a secret message that he needs sent at some time in the future. He arranges this by planting copies of the message among a network of confederates, with the instructions they need to ensure the message is transmitted at the right time.
The Black Hats who oppose the spy wish to intercept the message or to prevent the message from being sent - either of these two events mean that the spy fails. The black hats act by turning confederates / infiltrating his organization. All of the turned confederates will oppose the best interests of the spy, as best they can.
For the purposes of this puzzle, we're not particularly interested in the specific implementation details, so we'll use a simple abstraction of the idea of sharing the secret. We suppose that [ABC] represents a copy of the secret that can be decoded if confederates A, B and C cooperate together.
In other words, if conspirators A, B, and C all betray the spy, then [ABC] is intercepted by the black hats. If any of these three conspirators betray the spy, then [ABC] is blocked.
The spy can use as many different copies of the message as he likes. For instance, he might choose to depend on [ABC] and [ADEFG]. If the black hats turn A,B and C, then the spy loses when that message is intercepted; likewise if the black hats turn A,D,E,F, and G. In addition, the spy will lose if both messages are blocked: if A turns, or one of BC turn and one of DEFG turn.
We can see a few things straight off.
Longer messages (messages that require more conspirators), are harder to intercept, but they are easier to block.
Using more messages makes it harder to block, but provides the black hats with more chances to intercept.
Assuming that the spy as 10 confederates (ABCDEFGHIJ) and for each confederate there is a 10% chance that the black hats will be able to turn the confederate, what is the optimal messaging strategy that the spy should use? How likely is it to succeed?
Spoilers under the fold.
Solution: the optimal strategy for the spy turns out to be very easy to describe, and generalize. If the spy has N=2k confederates available, then he first randomly chooses one confederate (call this confederate A), and then he uses all messages which require the cooperation of exactly k confederates, none of whom is A. In total, the spy ends up using
(2k-1 C k)
different copies of the message.
The spy wins if the black hats turn fewer than k confederates, or when they turn exactly k confederates including A (which is precisely half the cases where they turn k confederates).
We had specified ten confederates, so the spy will be using 126 different messages of length 5.
Proof:
First, a demonstration that we are really using half of the cases of length k. We started from 2k choices, but decided that we should never pick A, which gives us 2k-1 elements to choose from. We still need to pick k elements from this smaller group, so (2k-1 C k) is the right starting point...
( 2k - 1 C k )
= (2k-1)(2k-2)...k / k(k-1)...1
= k/k * (2k-1)(2k-2)...(k+1)/(k-1)(k-2)...1
= (1/2) 2k/k * (2k-1)(2k-2)...(k+1)/(k-1)(k-2)...1
= (1/2) 2k(2k-1)(2k-2)...(k+1)/k(k-1)(k-2)...1
= (1/2) (2k C k)
That result shouldn't be a suprise; if you are picking half the guys, any specific guy should be in the group you pick half the time.
On to the bulk of the proof. I found that thinking about complements made things much easier to work with - the complement is all of the confederates not in the group you are considering. With 10 confederates, the complement of ABCDE is FGHIJ, the complement of ACEGI is BDFHJ, and so on.
Complements are a quick way to demonstrate two facts. First, consider that if the black hats have turned ABCDE, they have also blocked all 5 length messages except for the complement FGHIJ. This means that we never want to use a message and its complement - either they have both been blocked, or one of them is intercepted - the redundancy hasn't improved our success rate.
On the other hand, it can only improve our chances to use at least one of them. Again, suppose ABCDE have been turned. If we haven't sent either ABCDE or FGHIJ, then all the messages we have sent are blocked. If we have sent both ABCDE and FGHIJ, then a message has been intercepted, and we lose again. Our winning case is ABCDE when we have sent FGHIJ, or the other way around; and so on for each pair of complements.
By the recipe above, the set of messages the spy chooses to use is the complements of the sets including A.
First check - can the black hats intercept a message by turning fewer than k conspirators? No, and this is pretty trivial - since all of the messages in use require k conspirators to cooperate, no smaller number is going to work.
Second check - can the black hats block all of the messages by turning fewer than k conspirators? Again no, but this is because we choose the set of messages carefully. The proof goes something like this. Choose any shorter group you like; if that group does not include A, add A to the group. Now pad the group with any conspirators you like not already part of the group until there are k conspirators in your group. The result here is a set of length k that includes conspirator A. Therefore, this group can't block all of the messages, because one of the messages went to the complement of this group.
Applying this ideal to our case of 10 confederates; no matter what group of 4 you choose, I can always find at least one group of 5 that doesn't overlap the group of 4, and that can decode the message.
Can we improve our chances by adding a longer message? No. If there are 6 conspirators including A who are not turned (necessary for the message to get through), then there are 5 conspirators excluding A who are not turned, and we already had that case won.
Can we improve our chances by adding a shorter message? No. The shorter message only protects us if all of our regular messages get blocked. It's only possible for all of those messages to be blocked if k confederates not including A turn, and that group of confederates can intercept one of the messages we've already sent.
In short, a solution of this type cannot be improved by adding another message to the mix.
There's an important hint in the analysis of shorter messages that helps to understand why this construction really is going to be the best one. To illustrate this, let's instead consider the N=4 case, with conspirators ABCD. Now, using the solution above, we should be using BC, CD, and BD. How do the solutions that use all of the conspirators compare?
Well, we could try AB, BC, CD. Just like the previous case, there are three pairs of confederates that can intercept the message. But in addition to this, there are two pair (AC or BD) who together can block all of the messages, even if they can't intercept them.
We might also try AB, AC, AD. This case is even worse, as A can block all of the messages on his own.
But with our solution - there are no combinations of 2 confederates that can block without also being able to intercept. That's the trick - our solution starts with no blocking combinations; all of our losses come on interceptions.
For the most part, a well executed campaign by the conservative base of the Republican party.
Their inexperience betrayed them in one way, I think; they didn't quite manage to get the timing of Scozzafava's withdrawal correct. Delay that decision by a few more days, and the political machine won't have time to back the conservative candidate and screw things up. The blame for this one clearly falls to the leadership of Michael Steele et al. If you can shut him out from supporting your candidate, you can regain control of the party and start collection seats. Win-win.
Non-spoiler review: Sanderson acquits himself well. Big Shit Happens.
Snark and spoilers below the fold; no promises that it will make sense until you have turned the pages for yourselves.
OK, so isn't it about time that Belgarion and the rest of the League of the Scroll figure out that Tarmon Gai'don is about misdirection?
Graendal's exit was... abrupt. Not a satisfactory resolution to her line, but the trick with the canary in the coal mine was a nice touch.
Verin... OK, we've got a lot of Verin chapters to reread. And a note to worry about - where the hell did that come from?
I usually put special marks on Mat's chapters so that I can find them again easily, but I don't think that's going to happen here. Nothing but treading water.
Masema... wow, what was the point of all that?
12 books in, and I still can't decide if I'm more annoyed by the MadLibs sword forms [ Animal Verbs the Noun ], or the Iuventus Stultorum Blade Magistere. For those of you who can't get to Vegas, the current betting lines are
The Goddamn Bat-Lan; no odds
Punk Hayseed kids; 2:1 against
Anybody that actually has a heron on their blade; 1000:1 against.
The ultimate role of Callandor got telegraphed just a little bit too heavily, in my opinion.
I really hope we get to see Moridin's reaction to the news about the Chodean Kal.
The usefulness of the Atha'an Miere is measured in milli-Aquamans.