When the handover gets one bit shorter

With nine passages, a surveyor can leave one door uninspected on every move and send a seven-bit report. Keeping the same door off every inspection list requires eight bits. The handler can choose a passage that works in every admitted case.

The surveyor sees whether a passage is open only by inspecting it. The handler knows which passages fit the exhibit. Both menus are nonempty, and the two people know that a common passage exists somewhere. They share the protocol and a reliable one-way channel. The handler sees the report and its own fit list. It cannot see which doors the surveyor inspected or their readings.

One fewer inspection than a full survey
PassagesInspectionsFixed inspection listNext door depends on earlier readings
5416 meanings · 4 bits10 meanings · 4 bits
98256 meanings · 8 bits126 meanings · 7 bits

Each number counts the smallest guaranteed reporting vocabulary for that row and procedure class. Bits are fixed-length payload bits. The inspection count is a worst-case requirement and both witness procedures use exactly that many on every path.

Follow one nine-door move

Suppose the building allows A, D and H. The exhibit fits B, F and H. The surveyor follows the agreed branching list.

G closed → I closed → B closed → D open → A open → H open → C closed → F closed.

Stop before checking E. Send report 22.

The surveyor’s readings are compatible with ADH or ADEH. Other readings can produce the same report. Its printed meaning allows exactly four building menus, each contained in the next: ADH, ADEH, ADEHI, ADEFHI. The handler compares these in order with its own BFH menu. The first possible fit is H in ADH. All later menus retain H, so the handler can choose it immediately.

Take the five-door example separately. For building AC and handler BC, the surveyor sees D closed, B closed, E closed and A open. Report 2 means A, AC, ABC or ABCE. The handler knows A alone cannot be the whole building menu on this move because the parties are guaranteed a workable route. The first compatible menu is AC, so it chooses C.

Why fewer inspections cannot guarantee a choice

If any path stops with two uninspected doors, X and Y, let the exhibit fit precisely those two. Complete the same survey readings first with only X open among the two, then with only Y. Both buildings and the handler fit the promise. The surveyor sees identical readings and the handler needs opposite routes. This rules out both early stopping and any smaller worst-case inspection budget in this model.

Why adaptive inspection can shorten the message

With a fixed list, the surveyor always leaves the same door U unread. Two different sets of observed open doors cannot share a report. Pick an observed door D that is open in only one of the two readings. Make U closed in that building and open in the other. Give the handler the fit list D and U. The same proposed report would demand opposite choices. Every fixed-list reading therefore needs its own meaning. Sending the readings suffices because the two possible building menus within each reading are nested.

The adaptive tree can leave different doors unread. Each terminal reading either fixes a single building menu or leaves two menus differing by precisely one door. Some readings can be joined into a single report: every building menu in their union is contained in the next. The handler uses the smallest menu compatible with its fit list and chooses a fit from it. That choice survives every possible larger menu. The full exported tables give the actual group for each report.

For a lower bound, take all buildings with exactly four open doors out of nine. Any two different four-door sets have one door exclusive to each. Give the handler those two exclusive doors and each building requires a different choice. All 126 four-door buildings therefore need different reports even if the surveyor inspects everything. The nine-door tree attains 126; its seven-bit word length and report count are both optimal. The ten two-door buildings give the same argument with five passages.

Why nine is the first size with a shorter fixed-length word

For n from 2 through 8, the sizes of the largest equal-size layer of building menus are 2, 3, 6, 10, 20, 35 and 70. The incompatible-menu argument makes each a lower bound on report meanings. Each already requires n−1 bits, the size of a fixed n−1-door report. At nine doors the lower bound is 126, which fits in seven bits, and the explicit inspection tree attains it. This establishes the first saving relative to the fixed inspection list. A raw nine-box full survey uses nine payload bits. Timing, packet headers, inspection effort, codebook briefing and reading errors are outside the word-length comparison.

Would anybody use the shorter report?

If the radio reserves a whole byte per move, these seven- and eight-bit messages occupy the same slot. If the payload can be packed bit by bit, let b be the value of saving a bit on one move, a the extra effort of following the adaptive survey and reading its code on that move, and K the one-off cost of preparing and teaching it. With otherwise equal inspection costs, the adaptive arrangement repays the setup after r moves only if r(b − a) > K. If visiting particular doors costs different amounts, the routes taken must be priced separately. The museum model supplies no measured values for those costs.

Check every move

In each certificate, start at node 0. Inspect the named door and follow its yes or no node until you reach a report number. The report table gives its possible building menus in increasing inclusion order. The files contain the complete instructions for both roles.

From a checkout with Node.js, run node essai-03/larger/make-certificates.mjs and node --test model/larger-survey.test.mjs. The first reconstructs the published tables from compact probe orders. The second walks each building through each tree, forms the handler’s possible worlds from the report and its own fit list, and checks that every prescribed route works throughout that set. Same-size building menus give an independent lower bound.

For each tree the construction orders terminal readings by inclusion from the largest member of one reading to the smallest of another. As each reading contains at most two adjacent menus, readings can share a chain exactly when they are comparable this way. A bipartite matching joins comparable readings into report chains. The exported tables are sufficient to verify the upper bounds regardless of the search used to find the trees.

The named routes, sensors, one-message rule and successful-delivery assumption are supplied. If the common-route promise is withdrawn, a handler may need to report a blockage. A seven-bit route-selection code provides no such guarantee. Choosing a route conveys neither permission to move nor evidence of arrival.

Return to the museum essai