The following puzzle deals with storage and search strategies for querying membership of elements in a table. Like the light bulb puzzle, it’s an example of a situation where binary search is only optimal in the limiting case. I will try to present the problem in the same weirdly racy context in which I first encountered it:

You are the manager of a hotel that, once a year, hosts members of a secretive private club in numbered suites on a dedicated floor of the hotel. There are club members, known to you only by numbers 1 through . Each year, some subset of 10 of the 18 club members come to the hotel for a weekend, each staying in his own suite. To preserve secrecy, you assign each man to a suite… but then destroy your records, including the list of the particular members staying that weekend.

It may be necessary to determine whether a particular member is staying at the hotel (say, upon receiving a call from his wife asking if her husband is there). But the club has asked that in such cases you must only knock on the door of a *single* suite to find out who is residing there. For a given subset of 10 club members, how should you assign them to suites, and what is your “single-query” search strategy for determining whether any given club member is staying at your hotel?

This problem is interesting because, for a sufficiently large universe of possible key values, we can minimize the maximum number of queries needed in a table of size by storing the keys in sorted order, and using binary search, requiring queries in the worst case. But for small , as in this problem, we can do better. For example, if , then we don’t need *any* queries, since every key is always in the table. If , then we can store in a designated position the key immediately preceding (cyclically if necessary) the missing one, requiring just a single query to determine membership.

(*Hint*: The problem is setup to realize a known tight bound: if , then there is a strategy requiring just a single query in the worst case.)

### Like this:

Like Loading...

*Related*

Sorry I don’t understand, even with the hint.

“If m=n+1, then we can store in a designated position the key immediately preceding (cyclically if necessary) the missing one, requiring just a single query to determine membership.”

Ok, so let’s assume the guests are numbered 1-11, and 3 is missing.

We could put everyone in the room such that m=n, except put 11 in room 3. This works as long as we don’t need to lookup 11.

According to the hint, the manager should place the guest immediately preceding the missing one in a designated spot (let’s say 10). The guest immediately preceding 3 is 2. So we place 2 in room 10… and then what?

Now suppose that we want to know if Guest #1 is staying at the hotel. Knowing our strategy for how we placed guests in the rooms, we need only knock on door #10. Guest #2 answers… which tells us that Guest #3 is the only one not staying at the hotel (and so the answer to the query “Is Guest #1 present?” is “Yes.”)

In other words, with guests “named” #1 through #m, define a function that, given any n-subset of {1,2,…,m}, places the corresponding guests in rooms numbered 1..n, so that you can determine whether any particular guest 1..m is present by querying the contents of a single room.