• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Security Clearance

 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.



 
Rancher
Posts: 4803
7
Mac OS X VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sounds like an induction proof. Show true for 1. Show how if true for N, then true for N+1

 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Are you okay? You look a little big. Maybe this tiny ad will help:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic