OpenAI o1（３）

OpenAI o1（２）からの続き

前回の真鍋さんのMIPOの次の問題にチャレンジしたところ，OpenAI o1から正解は出てこなかった。とりあえず，自力で考えてみようとしたら，なかなか頭が働かない。次のような整数問題だ。

Ｑ（koshix）：

最大公約数が1である正の整数の組（a1,a2,a3,a4,a5,a6）であって， k1=a1/a2, k2=2*a2/a3, k3=3*a3/a4, k4=4*a4/a5, k5=5*a5/a6, k6=6*a6/a1 として，(k1, k2, k3, k4, k5, k6) がすべて 整数であるようなものはいくつあるか。

答えは6と出たが，正解は，15876 (=126^2) なのだった。実は，自分もAIと同じ間違いをしていて，すべてのa_i の組が互いに素であると思い込んでいた。そうではなくて，（a1, a2, a3, a4, a5, a6）の6つの数の最大公約数が1という条件なのだ。

つまり，k1*k2*k3*k4*k5*k6=6!=720を6つの正の整数（k1,k2,k3,k4,k5,k6）の積に分解する場合の数を求めればよい。つまり，720を素因数分解した 2^4*3^2*5 の各指数のべきを6つの箱に分配する場合の数（重複組み合わせ）の積になり，6H4*6H2*6H1=126*21*6=15876 である。

計算方法はわかったが，これが正しいためには，（a1,a2,a3,a4,a5,a6）と（k1,k2,k3,k4,k5,k6）が一対一対応する必要がある。その証明を OpenAI o1にきいて見よう。

Ｑ（koshix）：

a_i (i=1 ... n) が正の整数であり，(a_1, a_2 ..., a_n) の組の最大公約数は1であるとする。

a_1/a_2=k_1, 2*a_2/a_3=k_2, 3*a_3/a_4=k_3, ... (n-1)*a_{n-1}/a_n=k_{n-1}, n*a_n/a_1 = k_n 

において，(k_1, k_2, ... k_n) は整数となって，k_1*k_2*k_3*...*k_{n-1}*k_n = n! が成り立つ。

このとき，一つの(k_1, k_2, ... k_n) に対して必ず一つの(a_1, a_2 ..., a_n) が対応することを証明してください。

Ａ（OpenAI o1）

証明：

まず、与えられた条件から $ a_i $ を $ k_i $ を用いて表現します。

ステップ１：$ a_i $ を $ k_i $ と $ a_1 $ で表す

最初の方程式から始めます。

1. $\dfrac{a_1}{a_2} = k_1$  ⇒  $ a_1 = k_1 a_2 $

2. $\dfrac{2a_2}{a_3} = k_2$  ⇒  $ a_3 = \dfrac{2a_2}{k_2} $

3. $\dfrac{3a_3}{a_4} = k_3$  ⇒  $ a_4 = \dfrac{3a_3}{k_3} $

   ⋮

このパターンを一般化すると、

$ a_i = \dfrac{(i-1)! \, a_1}{\prod_{j=1}^{i-1} k_j} $

となります。

ステップ２：最後の方程式を利用して $ k_n $ を表す

最後の方程式は

$\dfrac{n a_n}{a_1} = k_n$

これに $ a_n $ の表現を代入すると、

$ \dfrac{n \cdot \dfrac{(n-1)! \, a_1}{\prod_{j=1}^{n-1} k_j}}{a_1} = k_n \Rightarrow \dfrac{n!}{\prod_{j=1}^{n-1} k_j} = k_n $

したがって、$ k_1 k_2 \cdots k_n = n! $ が成り立ちます。

ステップ３： $ a_i $ の一意性の証明

$ a_i $ を $ a_1 $ と $ k_i $ で表すことができましたが、$ a_i $ が整数であるためには、$ a_1 $ が適切な値である必要があります。具体的には、すべての $ a_i $ が整数となる最小の $ a_1 $ を見つけます。

各 $ a_i $ に対して、分母となる $ \dfrac{\prod_{j=1}^{i-1} k_j}{(i-1)!} $ が存在します。すべての $ a_i $ が整数となるためには、$ a_1 $ がこれらの分母の最小公倍数（LCM）の倍数である必要があります。

すなわち、

$ a_1 = \operatorname{lcm}\left(1, k_1, \dfrac{k_1 k_2}{2}, \dfrac{k_1 k_2 k_3}{6}, \dots, \dfrac{k_1 k_2 \cdots k_{n-1}}{(n-1)!}\right) $

この $ a_1 $ を用いると、すべての $ a_i $ は一意に定まります。

ステップ４：最大公約数が1であることの確認

もし他に $ a_i' $ という解があると仮定すると、比 $ \dfrac{a_i}{a_i'} $ はすべて等しくなります。しかし、$ \gcd(a_1, a_2, \dots, a_n) = 1 $ であるため、この比は1でなければなりません。したがって、$ a_i = a_i' $ となり、一意性が証明されます。

結論：

以上より、与えられた $ (k_1, k_2, \dots, k_n) $ に対して、一意な $ (a_1, a_2, \dots, a_n) $ が存在することが証明されました。よって、一つの $(k_1, k_2, ..., k_n)$ に対して必ず一つの $(a_1, a_2, ..., a_n)$ が対応します。

なるほど，素晴らしい。ちょっと気になったのは，分母である$ \dfrac{\prod_{j=1}^{i-1} k_j}{(i-1)!} $ が必ず整数なのかどうかである。具体的に試して見ると，必ずしも整数にならない場合がある。そんなときは，分母を形成する有理数の分子だけに着目して最小公倍数を考えれば良い。分母の有理数の分母は元の数の分子に回るだけだからである。そんなわけで，多少詰めが甘いような気がするけれど，ここまで推論できれば大したものである。