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

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

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

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

問題．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$ ）であると考えていますが、そこまで証明できていません（後者については、鳩ノ巣原理を使って証明できる気がします…）。

その鳩ノ巣原理を利用することで、 $d_{n\ge 4}\le\sqrt{3}$ や $d_{n\ge 7}\le 1$ が分かります。一方、点を円周上で等間隔に配置することを考えると、 $d_n$ の定義から

$\displaystyle d_n \ge \sqrt{2 - 2 \cos\frac{2\pi}{n}}$

が導かれます。

2024/04/30 追記

$d_n\to 0$ （ $n\to\infty$ ）について鳩ノ巣原理を用いて証明できました。

任意の $\varepsilon\gt 0$ に対して十分に大きい $N$ を取ります。単位円板に外接する一辺の長さが 2 の正方形を格子状に分割して、 $N^2$ 個の一辺の長さが $\frac{2}{N}$ の小さい正方形を考えます。このとき、 $n\gt N^2$ として $n$ 個の点を どのように配置しても、鳩ノ巣原理によって少なくとも一つの小さい正方形には 2 点が含まれます。特に、この 2 点間の距離は正方形の対角線の長さ $\frac{2\sqrt{2}}{N}$ 以下です。よって、 $\frac{2\sqrt{2}}{N}\lt\varepsilon$ となるように $N$ を取れば、