CLR cover

Problem 124: Safe-Opening Words

The problem addresses a special non-deterministic version of synchronising words. We are given a graph $G$ with edges labelled by symbols and with a unique sink node $s$ on which all edges loop. We are to find a synchronising word $\mathcal{S}$ for which each non-deterministically chosen path labelled by $\mathcal{S}$ goes to $s$ independently of the starting node.

The problem is generally difficult but we consider a very special case called safe-opening words . It shows some surprising operations on words over the alphabet $\Bi_n=\{\sa{0},\sa{1}\}^n$.

Narrative description of the problem

The door of a rotating safe has a circular lock, which has $n$ indistinguishable buttons on its circumference with equal spacing. Each button is linked to a switch on the other side of the door, invisible from outside. A switch is in state $\sa{0}$ (off) or $\sa{1}$ (on). In each move, you are allowed to press several buttons simultaneously. If all switches are turned on as a result, the safe door opens and remains open. Immediately before each move the circular lock rotates to a random position, without changing the on/off status of each individual switch. The initial configuration is unknown.

The goal is to find a sequence called a safe-opening word $$\mathcal{S}(n) = {A}_1\cdot {A}_2\cdots {A}_{2^n-1}$$ of moves $A_i\in \Bi_n$ having a prefix that opens the safe.

Assuming button positions are numbered $1$ to $n$ from the top position clockwise, a move is described by an $n$-bit word $b_1b_2\cdots b_n$ with the meaning that button at position $i$ is pressed if and only if $b_i=1$. Positions are fixed though buttons can move, i.e. change positions.

Let $n$ be a power of two. Construct a safe-opening word $S(n)$ of length $2^n-1$ over the alphabet $\Bi_n$.

Abstract description of the problem

Each move ${A}_i$ is treated as a binary word of length $n$. Let $\equiv$ be the conjugacy (cyclic shift) equivalence. Let $G_n=(V,E)$ be the directed graph in which $V$ is the set of binary words of length $n$, configurations of the circular lock, and edges are of the form, for $A\in\Bi_n$: $$u\Arrow{A} (v \mbox{ xor } A)$$ for each $v\equiv u$ if $u\neq \sa{1}^n$, and $1^n \Arrow{A} 1^n$ otherwise.

The aim is to find a word $\mathcal{S} = {A}_1\cdot {A}_2\cdots {A}_{2^n-1}$ in $\Bi_n^*$ for which each non-deterministically chosen path in $G_n$ labelled by $\mathcal{S}$ leads to the sink $\sa{1}^n$ independently of the starting node.


  • I. Guo,