How do we get those dang Illuminati?

Question

The Illuminati just stole our office They shot JFK and have committed numerous crimes against humanity (not really) but we usually let that slide. But for stealing our offices, we have decided to get them arrested for those crimes, take over both offices, and get our revenge. In order to do this, though, we need their names.

To state the rules here:

• Congressmen are either Knights (R), Illuminati (L), Both (B), or Citizens (C)
• No one else belongs to either group
• We are not supposed to know who any member of either group is. So no more members of either group will willing reveal themselves.
• When attending joint meetings all of us are disguised but we can count how many of each of us there are
• After the plan is put into action, there will be no communication between us
• Citizens can't join either group by any means during this time frame. If you say their name and repeatedly tap your shoulders, they just start googling mental health centers to recommend to you.
• If a person (in this case always Bob) touches his left shoulder after saying a persons name, that person becomes an Illuminati (B) if he was only a Knight (R) or loses Illuminati (R) status if he was both (B).
• If a person (in this case always Bob) touches his right shoulder after saying a persons name, that person becomes a Knight (B) if he was only Illuminati(L) or loses Knight status (L) if he was both (B).

Senator Bob has been identified as a member of only our group and will not betray us. This is certain. We have agreed to hold a meeting every day with the Illuminati where every member of each group must be present in the correct uniform. If they are in both, they must wear the robes of one and the mask of the other. Bob will hold a prayer in front of congress between each meeting in which he can touch his shoulders as much as he likes and everyone will know.

We know there are only 100 congressmen whose status we don't already know. We know only 32 of these are in the Illuminati and 32 are our men. None of those unidentified are in both. Bob and Peter are currently known to be Knight Templar and Illuminati respectively because they shoulder tapped with obvious motives.

Is there a way we can determine the names of every one of those 32 congressmen who are right now Illuminati without revealing any of our names to them?

I am willing to lie and cheat as long as they don't know we are doing it. I am a politician like you after all.

Lets assume that we have ensure Peter will not shoulder tap again and they will not sabatoge us unless they know for a fact we have identified them (for now lets assume they are dumb enough they can't do that). They are smart enough, however, to try and catch us breaking meeting rules.

Bonus's if you can do any of the following:

• Minimize the number of meetings/shoulder tapping sessions
• Compute a plan for an arbitrary number of congressmen in each group
• Have the plan allowing for the possibility that unidentified congressmen is a member of both.

Answer 1

As a first solution that doesn't out any Knights:

Each day, Bob names one congressman and touches his right shoulder.

If at the next joint meeting one more person is wearing a split uniform (B), the just-named person is outed as an Illuminati. If a citizen or Knight was named, nothing happens.

This takes at most 99 days to uncover all Illuminati. (After 99 days, if we have only changed the costumes of 31 people, the unnamed congressman must be the 32nd unknown Illuminati.)

Answer 2

To speed things up, we can use the fact that none of the unidentified are B.

Let Bob execute RLR for congressman 1, LRLR for congressman 2 and RLRLR for congressman 3.

For all possibilities, this gives us the following table:

before  after   change 
1 2 3           R  B  L  
L L L | R R B | +2    -2
L L R | R R L | +1 +1 -2
L R L | R B B |    +1 -1
L R R | R B L | -1 +2 -1
R L L | L R B | 
R L R | L R L | -1 +1
R R L | L R L | -2 +1 +1
R R R | L B L | -3 +2 +1

We can see that each assignment of memberships corresponds to a unique change in frequencies at the next secret meeting. The next day Bob does the same for congressmen 4, 5 and 6 and so on. Since we're dealing with groups of three congressmen per meeting, we can work through all hundred in 34 days, and have the Illuminati behind bars before Christmas.

Perhaps this scheme can actually be extended a little further, but not to the full 100 congressman. Since there are about $100^2$ unique frequencies, the best you can do with this strategy is to expose the Illuminati in groups of 13 (ie. in 8 days). I'll leave that for another poster to work out.

Answer 3

We won't be using the left shoulder, because that will out the Templars. The right shoulder is fine though.

Improving on aschepler's solution, we name 2 people each day while touching the right shoulder. If the number of B is unchanged at the next meeting, neither was illuminati. If B has increased by 2, they were both illuminati. If only 1, then we spend the next day identifying which: name one of the two while touching the left shoulder. If the number of B has dropped at the next meeting, this person was originally illuminati, otherwise it was the other person.

This method has a worst case when we never eliminate 2 illuminati in one day and still have 1 left in 99-100 so we spend 49 days testing pairs and 32 identifying which member of each pair was illuminati, giving 81 days.

Answer 4

Ok, let's start with an inefficient one, to set up the principle (and check that I understand the rules).

We number the unknowns 1 through 100 (or 1 though 98 if we're counting Bob and this Peter fellow). First, we call a meeting, and make a note of how many people turn up in each group.

At his first session of congress, Bob says the name of congressman 1, and taps his right shoulder, says the name and taps his left shoulder, and then says the name and taps his right shoulder (RLR). This turns Illuminati into Templar and vice versa, while members of both and citizens are unaffected.

We call another meeting and see if the numbers have changed. If we have an extra Templar, we add congressman 1 to the list.

Bob goes through all congressmen in this fashion, and after only 100 days we know whom to arrest.