0
$\begingroup$

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

  • 0
    @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.2012-03-28

3 Answers 3

0

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.

0

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]$

0

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.

  • 0
    Thanks for the update! The basic idea is clear now!2012-03-29