posted 15 years ago
Hm, your second argument depends on various assumptions, stated and unstated; no matter, as the first objection is the important one - I overlooked that rule. I gather my guesses about objectives, trustworthiness, etc were valid though.
OK, so have 1 stand next to the far wall, facing it, such that he is unable to see anyone else, and everyone else can see that he's facing away. Then have 2 stand behind 1, facing the back of 1's head. 2 now cannot see anyone else in the room, and everyone can see that 2 is not turning around. And so on, with 3, 4, etc. Once 8 and 9 know who's who, one of them (selected randomly) taps 7 on the shoulder, and 7 turns around. Then they randomly select someone to tap 6 on the shoulder. And so on. Obviously they need to "scramble" their positions before each tap, so that they reveal no significant information by their positions; no biggie.
There are some possible objections here, e.g. what if one member of the group is in a noisy wheelchair and thus transmits info in her activities. Or what if the room is fully mirrored. Or what if outside observers (clearance 0) have the ability to observe approximate physical location of people in the room. Well OK, but I hope they can't also observe minuscule motions like writing, and I hope there is some reasonably reliable way to destroy all writings afterwards. A book of matches, for example. In that case, we could use a system where everyone sends a message to everyone else, repeated over several rounds.
To formalize a bit:
Person 1 announces who they are, to everyone. Great, that's solved. Henceforth "everyone" means everyone but person 1. Person 1 doesn't need to do anything else. (Though we do still need to ensure that since person 1 is still observing, person 1 cannot deduce anything significant from what he observes.)
Now, give everyone (meaning everyone except person 1, naturally) an envelope or box with their name on it. That's how they will receive messages. There are six rounds for messages. In each round, everyone will send a message to everyone else. A message will be written on a piece of paper, folded so that it can't be accidentally read by others, and placed in the recipient's mailbox. Many of these messages may well be blank, or perhaps filled with irrelevant information, as each person needs to look like they may be writing an Important Secret Message, each and every time they write a message. Call these unimportant messages "fillers".
Anyway, in round 1, person 2 tells everyone that she's person 2. While everyone else sends filler messages. In round 2, person 3 tells everyone but person 2 that he's person 3. And so on. Round 1 reveals person 2, round 2 reveals person 3, up to round 6 reveals person 7. At this point both 8 and 9 have enough info to figure out who is who, and the only thing left to do is destroy all the messages.