Brain teaser: locks, keys and gifts

Updated on 11 October 2018: I sent an e-mail regarding this problem to SPARC team. Their reply was:

Thanks for the interest. We don’t have an official solution posted, but our solution was $\mathcal{O}\left({n\log n}\right)$. One of our alums claimed that $\mathcal{O}\left({n\log n}\right)$ was in fact optimal ($300), but I (personally) did not see the proof.

Yesterday evening, a brain teaser was spread into Yao class WeChat group. Originally, the provider of the problem didn’t tell us the source of the problem. When asked, he said that the problem was asked by someone, and that she (she’s a she) didn’t provide an answer. With repeated request of recursive source tracing, we finally got the source of the problem so that I could cite it here. The problem is the technical problem of application to SPARC. You might be able to find the problem on this Google Docs form before the form is closed. Here’s a transcription:

Question 3: Locks, Boxes, Gifts, and Friend *

Suppose that for $1 it is possible to purchase two keys and two matching locks. Either key can be used to open either lock, but once a key is used, the key is destroyed. You also have access to an unlimited supply of boxes of every size, each of which can be secured with a single lock. You have 100 different gifts to give to a friend. You want to lock up the items in such a way that your friend can get whichever set of 50 items they choose, but can’t access any set of 51 items. You make some locks, put them on some boxes (some of which contain your items), and give your friend some of the keys and all the boxes. How few dollars can you spend and still accomplish your task?

What we’ve found

Mathematical/computer science methodology mandates us to:

• think the problem in a general-value setting, where 100, 50 is replaced by $2n,n$;
• try to achieve optimum by progressively approaching it, which means we want first a construction then some optimisation, and first asymptotic bound then concrete bound.

I did my first trial on smaller numbers. For 1-out-of-2, this is easy: just pack the two items in two boxes, locked with the same locks, and throw away one key. For 2-out-of-4, it is also straightforward to: pack item 3, 4 in two boxes locked with lock 0, pack item 1 [resp. 2] in a box locked with lock 1 [resp. 2], pack the two keys to lock 0 in two boxes, locked with lock 1 and lock 2, respectively, and finally throw away one key to lock 1 and one key to lock 2. If your friend wants item 1 and item 2, he can just open the boxes with their corresponding keys. If your friend wants item 3 or item 4, he must abandon one of item 1 and item 2, which in turn allows him to open a box containing the key to lock 0, which indeed allows him to acquire item 3 or item 4. For 3-out-of-6, it takes some time. The reader is invited to check the correctness of the illustration shown below. The colour of each box represents the lock on it, and the colour of each key represents the lock it opens. (I am sorry that it won’t work for those with visual impairment.)

These constructions are quite ad-hoc, as they employ the specialty of small numbers that are hard to extend.

In the WeChat group, Kefan Lyu mentioned that one could virtually duplicate a key by locking it in a box and using the two keys to the box (the other lock is thrown away). It is also natural (mentioned by Wenhao Hong) that one can put boxes inside boxes. These two techniques already give a solution.

Viability Construction Since there are $\binom{2n}{n}$ possible outcomes, one can build a decision tree by putting boxes in boxes and use appropriate locks and keys (throw away one key to ensure choice of only one path), and let’s call the leaf boxes the ‘final decision boxes’, where we will put keys corresponding to that $n$-subset. One stores the items in boxes with different locks, and duplicate their keys until there are sufficient ones to put into the ‘final decision boxes’.

The consumption of money of this solution is $\Omega\left(\binom{2n}{n}\right)$. Not quite satisfactory.

Polynomial Solution I mentioned in the WeChat group that we could consider a gadget that allows one to choose 1 key out of $2n$, using a decision tree. We need $n$ such gadgets. This way, we only need $n$ keys to each item. The consumption is $\mathcal{O}\left(n^2\right)$. I initially thought it would be $\mathcal{O}\left(n\log n\right)$, but actually it is not. Currently this solution is the best we can do in the asymptotic sense. See Update later today for better solution.

Later, there were discussions on using divide-and-conquer or partitioning (blockwise processing) to further reduce the consumption. However, they were found no good. Somehow they failed because we could duplicate keys, not locks or the items.

I think the idea of this problem is intuitively similar to that of $k$-out-of-$n$ OT.

Chat show program ingredients

During the discussion in the WeChat group, we sometimes might come up with some humour lines. These are something that deviates from the academic setting, which is often about considering the part of a concrete real-world situation that has been abstracted away from the problem. Someone coined the term ‘chat show program ingredients’ (综艺节目元素) for this. Here’s one:

Can I lock my friend in a box?

Here’s another:

A Since $\binom{100}{50}$ isn’t a power of two, you might as well adversarially make your friend end up with nothing.

B You can also talk your friend into opening up the wrong box.

C Shouldn’t we assume transparency of the boxing scheme?

D Let’s not mix in chat show program ingredients!

And here’s a third one:

A If you assume your friend is stupid, cure him first.

B Should we assume all the boxes that can be opened in a choice will be opened?

Me Let’s for sure not mix in char show program ingredients!

Update later today

A discussion later today revealed better constructions. Let’s talk about Kefan Lyu’s $\mathcal{O}\left(n^{1.5}\right)$ construction first.

Kefan Lyu’s construction

For the ease of notation, let’s consider $n$ items. Group the items into $g$ groups so that each group has $n/g$ items.

For each group, we construct a gadget that allows us to make a choice out of $n/g$, where the choice represents the item chosen from this group. For each group, we need $n/g$ such gadgets. Each gadget costs $n/g$ keys and needs one equivalent key to each item in the group. Therefore, the cost for each group is $\Theta\left(n^2/g^2\right)$. Since we have $g$ groups, the cost for this part is $\Theta\left(n^2/g\right)$.

Let $G_{i,j}$ be the $j$-th copy of gadget for group $i$. We build the following $n/2$ gadgets $C_{1,...,n/2}$:

• Choose one out of $G_{1,1},...,G_{g,1}$;
• Choose one out of $G_{1,2},...,G_{g,2}$;
• ……
• Choose one out of $G_{1,n/g},...,G_{g,n/g}$;
• Choose one out of $G_{1,1},...,G_{g,1}$;
• Choose one out of $G_{1,2},...,G_{g,2}$;
• ……
• Choose one out of $G_{1,n/g},...,G_{g,n/g}$;
• ……

If the $G$’s are secured, the friend clearly cannot access more than $n/2$ items.

Let the chosen items from each group form the set $S_i$, then $\left|S_i\right|\leq n/g$. Since any consecutive $n/g$ gadgets in $C$ allows us to choose distinct gadgets for one group, the friend can simply:

• Choose the $G_{1,\star}$ branch in the first $\left|S_1\right|$ gadgets in $C$;
• Choose the $G_{2,\star}$ branch in the following $\left|S_2\right|$ gadgets in $C$;
• ……
• Choose the $G_{g,\star}$ branch in the last $\left|S_g\right|$ gadgets in $C$.

I.e., the construction allows the friend to choose any $n/2$ items he wants.

The cost of building these gadgets is $\Theta\left({ng}\right)$, including the cost of duplicating keys to secure $G$’s. Therefore, the total cost is $\Theta\left({ng+n^2/g}\right)$, and letting $g=\Theta\left(\sqrt n\right)$ gives the optimum among this family of constructions, $\Theta\left(n^{1.5}\right)$.

Quasilinear construction

Following Kefan’s idea, we can further achieve better bounds by nesting groups. For example, grouping items into small groups and small groups into large groups gives us an $\mathcal{O}\left(n^{4/3}\right)$ construction. If we group at $k=\mathcal{O}\left(\log n\right)$ levels, we achieve $\mathcal{O}\left(kn^{1+1/k}\right)$. By doing exactly $\Theta\left(\log n\right)$ levels of grouping (equivalently, making the size of each group constant), we achieve $\mathcal{O}\left(n\log n\right)$.

The construction can also be understood as index permutation of FFT.

This is really a compelling bound. To consider a lower bound, if we use $t$ dollars, we will have at most $2^t$ different outcomes. By Stirling’s formula,$\binom{2n}{n}=2^{\Theta\left(n\right)},$we need at least $\Theta\left(n\right)$ keys. There’s still a gap there.