<p>An input to Mathematical Safe problem is represented by the 4-tuple $(L,K,S,X_0)$, where </p>

<ul>
<li>$L=[n]$ is the set of locks, </li>
<li>$K=(k_1,\dots,k_l,\dots,k_n)$, where $k_l$ is the number of the states of the lock $l$ and each state set of lock $l$ is a set of congruence classes modulo $k_l$ ($\mathbb{Z}_{k_l}$), </li>
<li>$S=(S_1,\dots,S_l,\dots,S_n),S_l\subseteq L,l\in S_l,\forall l$,</li>
<li>an initial tuple of lock states $X_0=(x_1^0,x_2^0,\dots,x_n^0), x_l^0\in \mathbb{Z}_{k_l},\forall l$.</li>
</ul>

<p>Let $x_l^j$ be the state of lock $l$ after turn $j$. Initially we are given a tuple of states $X_0$. After a single clockwise turn $j$ of the key in a lock $l$ all the locks $l&#39;\in S_l$ pass from a state $x_{l&#39;}^j$ to a state $(x_{l&#39;}^j+1)\bmod k_{l&#39;}$. The solution is the sequence of turns which opens the safe, i.e. brings it to the set of lock states $X=\{0,0,\dots,0\}$. The goal is to find a solution with minimum number of turns.</p>

<p>I know that this problem has been studied in some papers after 2002 year by one author, <a href="http://scholar.google.com/scholar?q=%22mathematical%20safe%22&amp;hl=en&amp;btnG=Search&amp;as_sdt=1,5" rel="nofollow">Donets G.A</a>. But it seems to me that it was studied before. Am I right in this respect and if so what references are there on this problem?</p>

CC BY-SA 3.0
2011-04-13T13:55:05.560Z
(1) I cannot understand the problem.  Why are you given many states instead of one state?  (2) You wrote “b_l = {0, 1, …, k_l − 1}”, but that should be “b_l ∈ {0, 1, …, k_l − 1}.”  (3) In the sentence after the itemized list, is it really “(b_j + 1) mod b_l” or a typo for “(b_j + 1) mod k_j”?
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-13T15:57:12.867Z
I agree. There are many problems in the formulation.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T17:23:06.473Z
In the post there are two typos. $S_l$ should be a subset of $Z$ and instead of $b_l$ in $(b_j+1)\bmod b_l$ should be $k_j$. I've corrected that. Sorry for this. And Tsuyoshi you're right about $b_l\in\{0, 1,\dots, k_l − 1\}$.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T19:28:00.583Z
I still fail to understand the problem and in particular why you are given many states instead of one state.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-13T19:45:35.353Z
The "state" of the safe is multidimensional, where each "coordinate" is drawn from the modulo set over some $k$. Each lock influences a subset of the states. Think of it like the combination lock on a suitcase (in which N is often 3 or 4)
Suresh Venkat
CC BY-SA 3.0
2011-04-13T19:56:14.820Z
@Tsuyoshi: Indeed, we are given one state, from which we are required to open the safe with minimum number of turns. When I wrote about B as a set, I meant it as the set of all feasible states.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T19:56:58.303Z
This seems like a special case of the general problem of linear programming with modular arithmetic. Maybe googling those keywords might help.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T20:08:57.963Z
@Tsuyoshi: Maybe you meant by many states in "$b_l\in\{0,1,\dots,k_l−1\}$ is the set of states of the $l$-th lock". I've corrected this too as follows: "$b_l\in\{0,1,\dots,k_l−1\}$ is the state of the $l$-th lock".
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T20:14:23.373Z
It does not seem to me that in your formulation, you are given any state as a starting point.  I read your formulation as you are given some set B of states, whose meaning is unclear.  What is the input of your problem?  Please try to write it a little more rigorously.  For example, putting an equation inside braces like “{b=(b_1,…,b_N)}” is sloppy and I do not understand its meaning in the current context.  (Suresh: I understand that a state is a vector.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-13T21:20:19.363Z
@Tsuyoshi: I've described an input to this problem.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T22:18:22.893Z
Thanks, now I can understand the problem.  (Nitpicking: 1. The capital N should be the small n.  2. You used braces {} to describe both a set and a tuple, but I do not think that it is a good writing style.  A tuple is usually written with parentheses ().)
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-13T22:28:35.400Z
@Tsuyoshi: Thanks for comment, I changed $N$ to $n$. Concerning tuples notation: I know about usage of () for tuples (this can be seen from the phrase "4-tuple $(L,K,S,X_0)$). I thought about this and came to conclusion that since all the expressions in braces are sets (i.e. in all cases symbols with different indices) it's justified to use {}. Even tuple $(L,K,S,X_0)$ can be seen as a set with this reasoning. Maybe I'm wrong?
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T23:05:21.233Z
In many cases {3,5} and {5,3} are the same thing.  (3,5) and (5,3) are different.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-13T23:11:03.073Z
@Tsuyoshi: I've corrected notation for sets/tuples.
Oleksandr Bondarenko
<ds.algorithms><reference-request>
References for the mathematical safe problem ?
Oleksandr Bondarenko
# References for the mathematical safe problem ?

(Asked by: username_0 on 2011-04-13)

An input to Mathematical Safe problem is represented by the 4-tuple $(L,K,S,X\_0)$, where

* $L=[n]$ is the set of locks,
* $K=(k\_1,\dots,k\_l,\dots,k\_n)$, where $k\_l$ is the number of the states of the lock $l$ and each state set of lock $l$ is a set of congruence classes modulo $k\_l$ ($\mathbb{Z}\_{k\_l}$),
* $S=(S\_1,\dots,S\_l,\dots,S\_n),S\_l\subseteq L,l\in S\_l,\forall l$,
* an initial tuple of lock states $X\_0=(x\_1^0,x\_2^0,\dots,x\_n^0), x\_l^0\in \mathbb{Z}\_{k\_l},\forall l$.

Let $x\_l^j$ be the state of lock $l$ after turn $j$. Initially we are given a tuple of states $X\_0$. After a single clockwise turn $j$ of the key in a lock $l$ all the locks $l'\in S\_l$ pass from a state $x\_{l'}^j$ to a state $(x\_{l'}^j+1)\bmod k\_{l'}$. The solution is the sequence of turns which opens the safe, i.e. brings it to the set of lock states $X=\{0,0,\dots,0\}$. The goal is to find a solution with minimum number of turns.

I know that this problem has been studied in some papers after 2002 year by one author, [Donets G.A](http://scholar.google.com/scholar?q=%22mathematical%20safe%22&hl=en&btnG=Search&as_sdt=1,5). But it seems to me that it was studied before. Am I right in this respect and if so what references are there on this problem?

**Tags:** ds.algorithms, reference-request

> **Comments:**
> **username_1**: (1) I cannot understand the problem.  Why are you given many states instead of one state?  (2) You wrote “b_l = {0, 1, …, k_l − 1}”, but that should be “b_l ∈ {0, 1, …, k_l − 1}.”  (3) In the sentence after the itemized list, is it really “(b_j + 1) mod b_l” or a typo for “(b_j + 1) mod k_j”?  
> **username_2**: I agree. There are many problems in the formulation.  
> **username_0**: In the post there are two typos. $S_l$ should be a subset of $Z$ and instead of $b_l$ in $(b_j+1)\bmod b_l$ should be $k_j$. I've corrected that. Sorry for this. And Tsuyoshi you're right about $b_l\in\{0, 1,\dots, k_l − 1\}$.  
> **username_1**: I still fail to understand the problem and in particular why you are given many states instead of one state.  
> **username_2**: The "state" of the safe is multidimensional, where each "coordinate" is drawn from the modulo set over some $k$. Each lock influences a subset of the states. Think of it like the combination lock on a suitcase (in which N is often 3 or 4)  
> **username_0**: @Tsuyoshi: Indeed, we are given one state, from which we are required to open the safe with minimum number of turns. When I wrote about B as a set, I meant it as the set of all feasible states.  
> **username_2**: This seems like a special case of the general problem of linear programming with modular arithmetic. Maybe googling those keywords might help.  
> **username_0**: @Tsuyoshi: Maybe you meant by many states in "$b_l\in\{0,1,\dots,k_l−1\}$ is the set of states of the $l$-th lock". I've corrected this too as follows: "$b_l\in\{0,1,\dots,k_l−1\}$ is the state of the $l$-th lock".  
> **username_1**: It does not seem to me that in your formulation, you are given any state as a starting point.  I read your formulation as you are given some set B of states, whose meaning is unclear.  What is the input of your problem?  Please try to write it a little more rigorously.  For example, putting an equation inside braces like “{b=(b_1,…,b_N)}” is sloppy and I do not understand its meaning in the current context.  (Suresh: I understand that a state is a vector.)  
> **username_0**: @Tsuyoshi: I've described an input to this problem.  
> **username_1**: Thanks, now I can understand the problem.  (Nitpicking: 1. The capital N should be the small n.  2. You used braces {} to describe both a set and a tuple, but I do not think that it is a good writing style.  A tuple is usually written with parentheses ().)  
> **username_0**: @Tsuyoshi: Thanks for comment, I changed $N$ to $n$. Concerning tuples notation: I know about usage of () for tuples (this can be seen from the phrase "4-tuple $(L,K,S,X_0)$). I thought about this and came to conclusion that since all the expressions in braces are sets (i.e. in all cases symbols with different indices) it's justified to use {}. Even tuple $(L,K,S,X_0)$ can be seen as a set with this reasoning. Maybe I'm wrong?  
> **username_1**: In many cases {3,5} and {5,3} are the same thing.  (3,5) and (5,3) are different.  
> **username_0**: @Tsuyoshi: I've corrected notation for sets/tuples.  

---

## 0 answers

