Puzzle/maths problem

[glenatron]

Emperor Alexius of Barzantium has six most trusted advisors in his cabinet: Bericus, Constantine, Davidius, Esquilinus, Fabius and Gesius. One of them however is a traitor, spying for the rival empress Zoe of Foobia. Alexius knows that any of his own agents that empress Zoe is aware of will be executed, but as a question of security he likes to keep the identities of his agents secret from everyone. He knows he will have to give away some of them in order to identify the spy. What is the smallest number of agents he can betray to definitely identify the spy?

This isn't a standard puzzle question really (or at least, it is, but I'm not setting it as a puzzle ) it's more a fundamental maths/computer science question that I feel should be intuitively obvious to me and is probably about the underlying principles behind bitmasking or parity that I've never really explored far enough to master. So assuming this is a standard question does anyone know what it is called? If it is not a standard question does anyone have any interesting answers to it? I feel there should be a solution that gives away no more than three spies, but I haven't yet found my way to it.

Comments

[thewhitespider.livejournal.com]

I'm unclear on how betraying one of his spies gives Alexius any information, or what sort of information it can give. That's probably not helping...

[glenatron.livejournal.com]

Any of the agents Zoe is aware of will be executed. So if he tells, say the first three people the identity of one agent and one of those is the traitor then the traitor will report back this information and the agent will be executed. If the agent is not executed, none of those informed is the traitor.

This all happens before the complex games of intrigue and double bluff that are as old as politics were invented, when people lead lives of simple intrigue and single-bluff.

[thewhitespider.livejournal.com]

I assume we're not allowed to give six names of people we don't like in Zoe's court, and employ one genuine spy to see which dies...

If that's true, then the obvious solution is that n spies allows you to find the traitor among 2^n people, halving the numbers every time until there's only one left.

There's probably a more elegant solution using overlapping sets, but I don't see what it is.

[glenatron.livejournal.com]

This overlapping sets approach is the one I'm thinking of.

I now realise that it depends on whether you know the outcome of each round of information before starting the next one as well.

If each round we know the answer to the previous one you can quickly eliminate people. If you have to plan ahead a complete scheme it's obviously much more complex. Intuitively I feel it should be doable in n attempts where the number of untrustworthy advisers <= 2^n.

[thewhitespider.livejournal.com]

Yeah, that's a difference between this test and parity checking.

You might need to start thinking about eight or sixteen bits of data, to see how it scales.

[stu-the-elder.livejournal.com]

A typical emperor's solution is to get paranoid and have all his friends killed off.. is that the answer you wanted? Stabby stabby?

[glenatron.livejournal.com]

But then the promotion of further advisors to the cabinet opens up new avenues of potential deceit. Barzantium is a sizeable empire and Alexius does not have the time or the inclination to involve himself with every facet of it's administration.

[stu-the-elder.livejournal.com]

Well, that's what he gets for being fond of Machiavellian intrigue, the great tit.

[silks-ic.livejournal.com]

Kill them all, identify nobody
The answer is zero
You didn't say the smallest number without hurting anybody...

[glenatron.livejournal.com]

Although historically accurate, an emperor may also need to be practical and training up new Trusted Advisors is a tricky and time consuming job. More expensive even than recruiting new agents.

[life-of-tom.livejournal.com]

Yeah, I'm having a hard time understanding the question. Do you mean that no-one's ID is publicly known, if they are publicly known then she'll kill anyone who isn't her man?

In which case, I can't see myself how 'betraying' one person gives you any more information than 'that person is or is not the spy,' and the corresponding information about the others.

[glenatron.livejournal.com]

Alexius does not know who the traitor is, but he does know who his spies are. His advistors, including the traitor, do not know who his spies are. If the traitor hears about a spy they will inform the Empress Zoe and the spy will be executed.

For some reason Alexius is more interested in preserving the secrecy of his spies identities than he is in their survival, so he is willing to sacrifice several spies to identify the traitor rather than identify six spies and have a simple one-to-one correspondence and have the identities of five spies known by people other than himself. He is very much of the opinion that information is power. But not information gained from living spies, apparently

[life-of-tom.livejournal.com]

Oh, right, understand now. Traitors and spies are different.


You could luck out, I guess.

a)If you tell three, have the spy survive, then the traitor's in the other other three.

You tell two of those guys about the same spy (still only one spy mentioned)and then either he'll die or live. die and you have to sacrifice a second spy, live and you know the traitor's the odd one out.

b) If you tell three and the first spy dies, then you tell two from that group about a second, and if that spy lives you've nailed the traitor with one, if he dies you spend a third spy.

Luck of the draw, there.

[life-of-tom.livejournal.com]

what if you tell four people?

then either he dies, and you're searching a group of four or he lives and you're searching a group of two.


group of two- tell one of them. Bada bing, you get to use just one spy.

group of four- tell two about a second spy, you might be lucky and only have to give him away or you might need to sacrifice the third?

No way like that apart from hoping you get lucky.

[sultan-vinnegar.livejournal.com]

If I've understood this correctly (big if), then I'd do the following:

Tell B that C is a spy
Tell C that B is a spy
Tell D that C and B are spies
Tell E that D is a spy
Tell F that B and D are spies
Tell G that C and D are spies

We've given up the identity of C, B and D as spies. Whoever ends up dead can be uniquely traced back to the person we told.

This should hold true more generally, we are looking for the minimum number of items required to generate a unique set for each item involved.

I'm only halfway though my first cup of coffee, might be talking rubbish.

[life-of-tom.livejournal.com]

Clarification needed. You're betraying other people to b,c,d,e,f and g. One of them is a 'spy,' They will report on your 'agents.'

That's a pretty cool and very well worked-out answer to a different problem.

[hopkinssj2000.livejournal.com]

Sultans solutions still works for the above as well if you work it as telling them 3 different spies. Of course you have still essentially 'lost' 3 spies as although only 1 or 2 will be dead, all 3 will no longer be secret. If you combine Sultans and Toms group of 4 and 2 idea, you have a chance of only losing 1, and only give 2 identities away-

Advisors A, B, C, D, E, F
Spies 1, 2,
Tell Advisors A+B that 1 is a spy, tell C+D that 2 is a spy
If 1 dies, tell A that 2 is a spy to find out which of A+B is traitor
If 2 dies tell C that 1 is a spy to find out which is traitor
If none die, tell E that 1 is a spy to find out which is a traitor

Or alternatively, tell them all that 1 is a spy, and use spies 2-7 to find out which goes to the empress - that way you only lose the identity and life of 1 spy.

[glenatron.livejournal.com]

If we assume a turn-by-turn scenario, this seems like an ideal solution. I think this may be something like a formulation of the 12 marbles problem, but different in some respects.

I'm still trying to think my way through the overlapping sets approach where one exposes the minimal information in a single "turn" to expose the traitor. I think the sets would look like this:

Spy | group
1 | B C D
2 | D E F
3 | C E

So if 1 is executed our spy is B, if 1 & 2 are executed it is D if 1&3 are executed it is E and if 2 alone is executed it is F. If all spies survive the traitor is G. This square would extend to 7 suspects easily, add an eighth and one would , I fear, have to expose four spies. Others may know better.

[life-of-tom.livejournal.com]

Of course, the real life ploy would be to tell each of them all that someone different who worked with 1 was a spy, and get 1 to plant evidence on those people. That way you find out who the traitor is and your spy gets to seem like the decent, reliable type.