Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a dormitory building with $N$ rooms $R_1$ to $R_N$. The $i^\text{th}\text{ resident }(i \in [N])$ has a key $K_i$ to his own room $R_{i}$. Let $L_{i}$ be the lock on room $R_{i}$. Naturally, $K_i$ and $L_i$ are one-to-one mapped; key $K_i$ cannot open lock $L_j$ unless $i = j$.

The administrator has a master key $K'$ capable of opening all locks $L_i, i \in [N]$.

Also, the dormitory has a common main door, with lock $L'$ that can be opened by any key $K_i, i \in [N]$, and also the administrator's master key $K'$. (We shall call this lock 'slave lock' as against 'master key'). However, this lock cannot be opened by any other key(s).

I'm looking for a mathematical representation, and a sample one-to-one mapping function (such that the function also satisfies the master key and slave lock entities).

EDIT: I'm looking for an algorithm or a function $y = f(x)$ of some sort that will help produce combinations for the locks and keys, and also define what the master key and slave lock would be in the domain considered.

Here's a schematic diagram:

schematic diagram

share|improve this question
2  
a) The symbol $\mathbb N$ is usually used for the set of natural numbers. It seems you're using it for the set $\{1,\dotsc,N\}$, which would more usually be denoted by $[N]$. b) I think you may have to say more about what sort of "mathematical representation" you're looking for, and what it means for a function to "satisfy the master key and slave lock entities". –  joriki Mar 28 '12 at 20:26
    
@joriki: Fixed the $\mathbb N$ to $[N]$; thanks for that! Also clarified the question; hope it's better now! –  SNag Mar 28 '12 at 21:12
2  
Unfortunately the edit hasn't really made it any clearer to me. I think you have to make more effort to define the terms you're using. What's "a sample one-to-one mapping function"? What are "combinations for the locks and keys", and what does it mean to "produce" them? And what does it mean to "define what the master key and slave lock would be in the domain considered"? All this remains very vague to me (and I suspect the fact that no-one else has replied suggests that it remains as vague to others). –  joriki Mar 28 '12 at 21:17
    
@joriki: The room keys and room locks are strictly one-to-one mapped; the master key has a one-to-many mapping to the locks; and all the keys have a many-to-one mapping to the slave lock. By "sample function" i meant something like what Peter Taylor proposed (division). "Combinations for locks and keys" are all the ordered pairs satisfying the established relation (a key opening a lock iff the key's integer divides the lock's integer). The domain considered in this case is the set of all integers, and the master key and slave lock defined are integers too. –  SNag Mar 28 '12 at 22:12
add comment

3 Answers 3

up vote 0 down vote accepted

You can map keys and locks to integers and have a key opening a lock iff the key's integer divides the lock's integer. Then let each room key map to a distinct prime, each room lock map to the prime corresponding to its key, the master key map to 1, and the master lock map to the product of all the primes used.

share|improve this answer
    
Thanks! This is close to what I was looking for. It's clear that if I consider different (mutually exclusive) sets of prime numbers, the slave lock is exclusive to that set. However, the master key would always be 1, meaning the master key of one dormitory would be able to open another. Is there any way to tightly bind the room lock/key pairs together with the slave lock/master key such that (A) The locks (including the slave lock) in the set cannot be opened by any keys outside the set? and (B) The keys (including the master key) in the set cannot open any lock outside the set? –  SNag Mar 29 '12 at 7:51
    
@SNag, the question doesn't say anything about multiple dormitories, so you might want to edit that in. But you can do it by using a few more primes. Let each master key be a prime, each key and lock of which it's a master be the product of that prime with a new one, and the slave lock be the product of all the related primes. –  Peter Taylor Mar 29 '12 at 8:53
    
Thanks for the update! The basic idea is clear now! –  SNag Mar 29 '12 at 9:31
add comment

You can use a relation between the set of locks (add $L'$ as $N+1$) and keys (add $K'$ as $N+1$). $R$ contains $(a,b)$ is true if key $K_a$ opens lock $L_b$. $R$ consists of all pairs $(c,c)$ plus all pairs $(N+1,d)$ plus all pairs $(e,N+1)$ for $c,d,e \in [N]$

share|improve this answer
add comment

I am not able to come up with a strict mathematical model that follows a f(x) = y function, but based on the structure of a lock / key mechanism from the Wikipedia page on locks, here's what I am thinking. A key has a series of grooves that align in the lock.

Going by your figure, let's assume $N=5$. We have 5 keys and 5 students, and each student has a key with, let's say, 5 grooves. The locks $L_1$ through $L_5$ then have 5 pins as well, and they must align. 1 to 1 mapping, so far so good.

For the slave lock $L^'$, we create a new groove. This is grove $N+1$ or grove $6$. This lock must be designed to "ignore" the grooves $1$ through $N$. Therefore, think of some kind of a mask pattern. In other words, for the locks in the rooms, the mask is $111111$. For the $L^'$, the mask is $100000$. This way, for the room doors to open, all $6$ grooves must match. For the slave lock, if groove $6$ matches we are good.

Then we have a master key. Once again, let's create another pin $7$ (or the FINAL pin) which happens to be an over ride pin. If a $7$ grooved key were to be inserted, the lock would just open right away. Now, only the administrator gets a $7$ groove key, while students only get a $6$ grooved key.

In summary, to come up with some sort of a math formula -

For each lock -

Check if key has $N+2$ grooves. If so, match groove $N+2$ to pin $N+2$ to open.

Else, check if key has 6 grooves. If so, use the pattern set into the lock to find out which grooves need to be matched.

----Match corresponding grooves. If so, open.

Else, continue to keep door locked.

I am sure some logic formula can be worked out based on this ...

You could extend this "model" for more requirements by adding more grooves and setting masks correspondingly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.