## 3 Upper and Lower Bounds of \(\mathit{diam}(\mathscr{M}_{m,n})\)  
In this section, we consider the following problem: How many _steps_ are enough to derive a configuration \(\mathbf{Y}\in\mathscr{M}_{m,n}\) from a configuration \(\mathbf{X}\in\mathscr{M}_{m,n}\). That is, we try to evaluate the value \(\max_{\mathbf{X},\mathbf{Y}\in\mathscr{M}_{m,n}}\,dn(\mathbf{X},\mathbf{Y})\). We call the value the _diameter_ of \(\mathscr{M}_{m,n}\) and denote it by \(\mathit{diam}(\mathscr{M}_{m,n})\). Next theorem gives simple upper and lower bounds for \(\mathit{diam}(\mathscr{M}_{m,n})\). (For pebble games which are generalization of the 15 puzzle, a similar study can be found in [5].)  
**Theorem 1**.: _The following statements hold:_  
1. _For any configurations_ \(\mathbf{X}\)_,_ \(\mathbf{Y}\in\mathscr{M}_{m,n}\) _with_ \(\mathbf{X}\equiv\mathbf{Y}\)_,_ \(dn(\mathbf{X},\mathbf{Y})\leq 4 mn+c\cdot\max\{m,n\}\) _for some constant_ \(c\)_._
2. _For a given_ \(0<\varepsilon<1\)_, there are integers_ \(m\) _and_ \(n\) _such that for any configuration_ \(\mathbf{X}\in\mathscr{M}_{m,n}\) _there is a configurations_ \(\mathbf{Y}\in\mathscr{M}_{m,n}\) _for which_ \(dn(\mathbf{X},\mathbf{Y})\geq\varepsilon mn\)_._  
Proof.: We first show the first statement. Since triangle rotation and three elements rotation take four and seven steps, respectively, according to our solution described in the previous section, we can have an upper bound: \(\mathit{diam}(\mathscr{M}_{m,n})\leq 4 mn+c\cdot\max\{m,n\}\) for some constant \(c\).  
We now show the second statement. Let us consider first the case where \(mn\) is even. Note that \(\{\mathbf{Y}:\mathbf{Y}\equiv\mathbf{X}\}=\mathscr{M}_{m,n}\). For a configuration \(\mathbf{P}\) in \(\mathscr{M}_{m,n}\), let \(N(\mathbf{P})\) denote the set of configurations \(\mathbf{Q}\) obtained from \(\mathbf{P}\) by executing one row or column operation (namely, \(\mathbf{Q}\) can be obtained from \(\mathbf{P}\) by applying \(O^{k}\) for \(O\in\{N,S,E,W\}\) and some integer \(k\)). Let \(d=\max_{\mathbf{W}\in\mathscr{M}_{m,n}}dn(\mathbf{X},\mathbf{W})\). Since \(|N(\mathbf{P})|\) is at most \(2 mn\), \(|\mathscr{M}_{m,n}|\) is at most \(\frac{(2 mn)^{d+1}-1}{2 mn-1}\) (see Figure 5). Hence, as \(|\mathscr{M}_{m,n}|=(mn)!\), \((mn)!\leq\frac{(2 mn)^{d+1}-1}{2 mn-1}\) holds. Since \(\big{(}\frac{nm}{e}\big{)}^{mn}<(mn)!\leq\frac{(2 mn)^{d+1}-1}{2 mn-1}\leq(2 mn) ^{d+1}\), it follows that \(mn\frac{\log(mn)-1}{\log 2+\log(mn)}-1<d\). This completes the proof of the even case for the second statement.  
Let us consider now the case where \(mn\) is odd. The second statement holds also for the odd case. This can be proved by the almost same way. The difference is the number of configurations obtained from \(\mathbf{X}\), that is, \(|\{\mathbf{Y}:\mathbf{Y}\equiv\mathbf{X}\}|=|\mathscr{M}_{m,n}|/2\) holds for the odd case. Clearly, the difference does not affect the result of calculation.  
Figure 5: The relation between \(d\) and \(mn\).  
By applying a similar argument to evaluating the push number, we have that \(pn(\mathbf{X},\mathbf{Y})\) is \(O(mn\cdot\max\{m,n\})\) for any pair \((\mathbf{X},\mathbf{Y})\) with \(\mathbf{X}\equiv\mathbf{Y}\), and for any \(\mathbf{X}\) there is \(\mathbf{Z}\) such that \(pn(\mathbf{X},\mathbf{Z})\) is \(mn(1-o(1))\).