Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\newcommand{\Arrow}[1]{\,\stackrel{#1}{\longrightarrow}\,}
\newcommand{\Bi}{\mathtt{B}} % binary alphabet $\{\sa{0},\sa{1}\}$
\)
It can be checked that the unique shortest safe-opening word for $2$ buttons
is $\mathcal{S}(2) = \sa{11}\cdot \sa{01} \cdot \sa{11}$.
For $u=\sa{0111}$ and $A=\sa{1010}$ there are four nodes $v$ conjugate of
$u$, $\sa{0111}$, $\sa{1110}$, $\sa{1101}$, $\sa{1011}$, and consequently
edges:
$$u\Arrow{A}\sa{1101},\; u\Arrow{A}\sa{0100},\; u\Arrow{A}\sa{0111},\;
u\Arrow{A}\sa{0001}.$$
|
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.
