wood burning stoves
The moose likes Programming Diversions and the fly likes Security Clearance Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Security Clearance" Watch "Security Clearance" New topic

Security Clearance

David O'Meara

Joined: Mar 06, 2001
Posts: 13459

Hopefully others find this problem interesting as I did when I thought of it. Inspired by an episode of 'Bones'.

9 people are in a room and have been pre-assigned a security clearance from one to nine (ie one person with the lowest '1', one person with '2' up to the last having '9')
The rule is that you can only divulge your clearance level to someone with a higher level, but obviously they can't tell you theirs first.
No one is allowed too leave the room, but you can assume that you can use 'mundane' (call them 'supermarket') items such as pens and paper, but no electronics or specialised items.

Also consider two things:
8 is allowed to deduce who has clearance 9 without being told, but otherwise lower levels should not be given knowledge about higher levels other than 'they are higher'

I have a secondary question based on my solution, but that depends on what solutions other come up with.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3028
I see a list of restrictions, but no goal. What's the objective? Does everyone share that objective? Can everyone be trusted to tell the truth?

If the goal is for everyone to transmit all the info that they are allowed to, to everyone they're allowed to, and everyone can trust everyone, then this seems simple. The 1 just tells everyone that his clearance is 1, then leaves the room. The 2 then tells everyone else that she's a 2, then leaves. Then the 3 tells everyone else he's a 3, and leaves. And so on, up to the 8 who tells the one other person in the room that she's an 8 (and obviously the other guy is 9, but doesn't actually say so).

Note that whenever anyone leaves, they must not be seen b any other lower-clearance people. Everyone must leave to different places.

Perhaps it's easiest to do this with nine rooms in a row, accessible from a shared hallway. Number the rooms 1-9. Person 1 goes into room 1, closing the door. Then person 2 goes into room 2, closing the door. Etc. Once we get to the end, and 8 and 9 are revealed, they go back and open each door in reverse order.

If not everyone is trustworthy, and/or if they don't share the same objective, then I doubt a solution is possible.
David O'Meara

Joined: Mar 06, 2001
Posts: 13459

But no-one is allowed to leave the room, and being able to observe people leave the room (from the outside) would allow someone to gather information about the order of the security clearance
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3028
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.

Pat Farrell

Joined: Aug 11, 2007
Posts: 4659

Sounds like an induction proof. Show true for 1. Show how if true for N, then true for N+1

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1044
Not adding anything new to Mike's solution except the way to transmit information.

Since the people have access to "supermarket" equipment...
- Each person gets a pad of paper and a pencil.
- For (i=1; i<9; i++)
- - Two things happen simultaneously:
- - - The person with security clearance i writes 9-i notes describing/naming himself and giving his security level ("I'm the gentleman with a red bow tie and glasses. I have Sec Lvl 1." and i-1 giberish notes. He delivers the giberish notes to anyone that whose security level he already knows and the "real" notes to any that has only ever given him giberish notes so far.
- - - Everyone else writes 8 giberish notes and delivers them to the other people in the room.

Am I missing anything?
I agree. Here's the link: http://aspose.com/file-tools
subject: Security Clearance
It's not a secret anymore!