###### tags: `math`
# Boal Sort
## 問題
$1$から$m$までの数字が書かれた球がそれぞれ$4$つずつあり、その球を入れる筒が$n$個ある。($m,n$は自然数であり、$m<n$を満たす)。

筒は最大$4$個までの球を入れることができ、先入れ後出しのスタック構造となっている。(筒の一番上の球しか操作できない)。

最初、$m$個の筒の中に$4$個ずつの球が任意の順番で入っている($n-m$個の筒は空である)。これを「初期状態」と定義する。

また、$m$個の筒において、それぞれの筒が全て同番号の$4$つの球が入っている状態を「理想状態」と定義する(当然$n-m$個の筒は空である)。

操作を以下のように定義する:
- 筒の一番上にある球を筒から取り出し、他の筒に入れる
- 球をある筒から別の筒に移動させる時、同じ番号の球の上にしか移すことができない
- 空の筒へ移動させる場合は、どの番号の球でも良い

操作を何回か行い、「初期状態」から「理想状態」に遷移することができるかを考える。

(1) 「$n\geq m+2$の時、任意の初期状態から何回かの操作を経て理想状態へ遷移することができる」という命題は真か偽か？

(2) (1)が真である時、$n=m+1$のときはどうか？また、(1)が偽である場合、任意の初期状態から理想状態へ遷移できる$n$の下限はいくらか？