How to lock a shared artefact

Question

This answer reminded me of a nice puzzle. I present it as a challenge for you.

N thieves had stolen a magical artefact. They bought a lock with N keys and attached the artefact to a loop on a wall in their garage, so that each of them could use the artefact at any time. Immediately a big problem came up: if one of them decided to take the artefact from the garage, then they would not be able to find out who had done it. As they couldn't trust each-other, they were eager to always know who had taken the artefact whenever it was not in the garage. Meanwhile, any thief alone should be able to take it when he needed it.

How could they achieve this goal, if they could buy any number of locks with any number of keys to each lock? How can this be done with the minimum number of locks?

P.S. I do not know whether proof of minimality exists.

Explanations:

1. Thieves can use only padlocks and keys, other things are forbidden.
2. They can attach locks to the loop and to the artefact. They can attach the locks to each other. Shackles of the locks are wide enough to be attached to any number of other shackles simultaneously.
3. They can distinguish locks by serial number.
4. Thieves can't break locks. Also they can't open locks then do not have keys to.

---

P.S. A common mistake is to not take into account that a thief, once the artefact is stolen, is free to leave his lock whenever he wants.

Answer 1

You can do it with $2N$ locks. Make one chain $123...N$. If we see $123...p$ on the wall, we know the artifact was taken by $p$ or $p+1$. Make another chain $246...N13...(N-1)$.

Added: you can do it with $N+3$ locks. Make the $123...N$ chain as above. Then make a three lock chain. Give a key to the first lock to every even number, a key to the last lock to every odd number, and nobody a key to the middle lock. The short chain will distinguish $p$ from $p+1$

Even better: a $3 \log_2 N$ solution. Write each person's number in binary starting at $0$. Make a three lock chain for each bit, giving the key for the lock on the wall to those with a $0$ in that bit, the key for the lock on the artifact to those with a $1$, and nobody the key to the middle one. So for $N=8$ you make three chains. For the first, the wall lock can be unlocked by $0,1,2,3$ and the artifact lock by $4,5,6,7$. For the second, the wall lock can be unlocked by $0,1,4,5$ and the artifact lock by $2,3,6,7$ and the third wall lock can be unlocked by $0,2,4,6$ and the artifact lock by $1,3,5,7$. To see who took it, put a $1$ for each missing middle lock and a $0$ for each present middle lock. Form a binary number and you have the number of the taker. You can also do $5 \log_3 N$ with chains of $5$ and base $3$, but that is inferior unless $N=3$ or $65 \le N \le 81$

Answer 2

N+1 Locks

1 master lock attached to the artefact.

N locks attached to the loop, each lock has a key to the master lock attached to it.

Each thief has a key to one of the locks (except the master).

Any thief can obtain a key to the master using their own key, and whichever lock is open/missing implicates the thief.

Edit: This only works once - once a master key has been accessed, it could potentially be copied.

Answer 3

Edit 3:

N Thieves can make N Chains of locks in the following fashion

Loop - Lock1 - Lock2 - Lock3 - Lock4 - ... - LockN-1 - LockN - Artefact

Loop - Lock2 - Lock3 - Lock4 - Lock5 - ... - LockN - Lock1 - Artefact ...

And so on, shifting by 1 each time.

Thanks to that, assuming that X steals the Artefact, he has to remove 1 Lock X attached to the artefact itself. At which point, assuming that the thieves write down the order that they assign themselves, the longest chain will reveal the thief: the longest chain will necessarily be of length (N-1), ending in X-1. Or X could put his lock back at the end of the chain, but hey, he's just incriminating himself even more.

If X tries to put his lock back on the second longest chain, such that the two longest chains have the same length, X will still be found out since the lock (X+1), missing at the end of the second (faked) longest chain, also exists at the beginning of the real longest one, thus making it impossible for (X+1) to have the artefact.

---

Unless I'm wrong, they can tie 2 chains of locks between the lop and the artefact, such that each chain is:

Loop-Lock A-Lock B-Artefact

Loop-Lock B-Lock A-Artefact

Where Lock A and Lock B denote a lock owned by the first or second thief, respectively.

That way, no matter who takes the artefact, there will remain a lock attached to the loop that belongs to the thief that didn't borrow the artefact, making it very obvious who took it.

Also, this can probably be extended to more thieves, but I can't think of it off the top of my head

Edit:

After mulling it out some more, N thieves just need to make chains in such a way so that every single one of N thieves has at least 1 lock attached directly to the loop, and has 1 lock somewhere in the other chains.

Let's refer to a chain starting with (Loop - Lock X - ... - Artefact) as X's chain. Let's refer to chains that look like (Loop - ... - LockX X - ... - Artefact) as other chains.

In this way, any X can break all the other chains at some point in the middle, can break his own chains at the beginning, and it's pretty obvious that X took the artefact if X's chains are missing.

Edit2: Which doesn't solve the problem of X leaving his lock back on the loop.

Answer 4

I can't tell if this answer is only true due to a misstatement in the rules, but I'll answer the question as written regardless:

"Thieves can't break a lock they do not have a key to."

Which this answer assumes means thieves can break a lock they do have a key to. The term breaking also implies a difference from "unlocking", but again, this conclusion may stem from misstatements in the rules.

Under these assumptions-

To successfully protect this "artefact" N chain of locks must be procured, each comprised of a cycle of N - 1 locks which require a cycle of N - 1 keys.

Example for N = 2

Chain 1 contains: Lock 1.A which accepts key a

Chain 2 contains: Lock 2.A which accepts key b

Example for N = 3

Chain 1 contains" Lock 1.A which accepts key a and b Lock 1.B which accepts key b and c

Chain 2 contains Lock 2.A which accepts key b and c Lock 2.B which accepts key c and a

This works because a thief can break a unique series of chains to release the "artefact" but has no written ability to repair the broken locks. Leaving proof of their treachery behind.

EDIT: For the sake of completion, each lock in the cycle is held in place by N locks with a cycle of single lock keys, thus preventing a perpetrator from stealing the proof of their crime along with the "artefact".