2024-04-25

気になっている数学関連の問題について

こんにちは、たまごはんです。

仕事柄、数学やらプログラミングやらの勉強をすることがあるのですが、しばらくすると集中力が切れてしまい、脇道に逸れてしまうことが度々あります…。その道中で見つけた、個人的に気になった数学関連の問題をまとめていこうと思います。

文字列の繰り返しに関する問題

問題．3 種類の文字 a, b, c で構成される文字列について、文字列の繰り返しを含まない文字列の個数は有限か？

補足

aaa とか caca とか bcacbcac のように、文字列 $w$ が 2 つ以上連続した文字列 $ww\cdots w$ を（文字列の）繰り返し と呼んでいます。例えば、acabcaba という文字列には cab の繰り返し（cabcab）が含まれています。

文字が 2 種類以下の場合、繰り返しを含まない文字列は有限個しかありません。これは具体的に書き出せば確かめられます。一方、文字の種類の数に関係なく、繰り返しを含む文字列は無数に存在します。これは例えば、aa から始まる任意の文字列を考えればよいです。

さて、問題の設定のもと、繰り返しを含まない長さ $n$ の文字列の個数を $a_n$ とすると、不等式 $a_n\le 3\cdot 2^{n-1}$ が成り立ちます。長さ $n$ の文字列は全部で $3^n$ 個なので、繰り返しを含まない文字列の割合は長さが増えるにつれ減少していきます。しかしながら、 $a_n$ 自体は（少なくとも $n=50$ くらいまでは）増加傾向にあるので、無数に存在する可能性も否定できません。

もし繰り返しを含まない文字列が無限個あったとすれば、文字の種類が 4 個以上の場合でも同じく無限個あることになります。一方で有限個だったとすると、文字の種類が増えても同じことが言えるのかどうかが気になります。

点の配置に関する問題

問題．単位円板の中（境界も含む）に 2 個以上の点を配置するとき、異なる 2 点の距離の最小値の最大値はいくらか？

補足

$n$ 個の点の配置 $P$ に対して、異なる 2 点間の距離の最小値を $d(P)$ とおくとき、その最大値 $d_n:=\max_P d(P)$ を求める問題です。一番は $d_n$ の厳密解を知りたいですが、恐らく難しそうなので $d_n$ の上界や下界を改善していくのが現実的かもしれません。

すぐに $0\lt d_{n+1}\le d_n\le 2$ が分かります。また、 $d_2=2$ や $d_3=\sqrt{3}$ であることも比較的容易に示せます。直感的には、十分に大きい $n$ に対して $d_{n+1}\lt d_n$ になり、特に $d_n\to 0$ （ $n\to\infty$ ）であると考えていますが、そこまで証明できていません（後者については、鳩ノ巣原理を使って証明できる気がします…）。