【くどー問題】 Y.K.さんの方法

※本記事では「くどー問題」を扱います。問題の内容に関しては以下のリンクをご参照ください：

この問題の解決を目指したMathlog記事を挙げておきます：

• 「くどー問題」の数値計算（bisaitama）
• 「くどー問題」再び（bisaitama）
• くどー問題のメモ（Y.K.）

適宜ご参照ください。

Y.K.さんの方法

「くどー問題」に関し、 Y.K.さん から有益なコメントを頂きました。

これまで私はくどー問題の数値計算を行ってきました。今までのコードでは、3乗和と1乗和を愚直に計算していました。一方Y.K.さんの提案された方法を用いると、3乗和、またそもそも3乗を計算する必要もなくなります。

整数の集合$\{1,2,\ldots,n\}$（$n\in \mathbb{N}$）から$m$個の数字を削除した集合の要素の3乗和と1乗和をそれぞれ$T_m, S_m$とします。ある時点で$T_m/S_m=k_m\in\mathbb{N}$が成立したとします。$m+1$回目に$d\in\mathbb{N}$を削除することにします（$d$は$2\le d\le n-1$かつこれまでに削除されていない数とする）。このとき
\begin{align} \frac{T_{m+1}}{S_{m+1}}&=\frac{T_m-d^3}{S_m-d}\\ &=\frac{S_mk_m-d^3}{S_m-d}\\ &=k_m+\frac{dk_m-d^3}{S_m-d}\\ &=k_m+\frac{d(k_m-d^2)}{(S_m-d)} \ \ \ (=k_{m+1}) \end{align}
が成立します。最後の式第2項が整数なら$(k_m,S_m)$に対して$d$は削除できます。ここで
\begin{align} T_0=\left(\frac{1}{2}n(n+1)\right)^2,\ S_0=\frac{1}{2}n(n+1),\ k_0=S_0=\frac{1}{2}n(n+1) \end{align}
です。

このことから、$m=0$から始めて、$k_m,S_m$およびそれまでに削除されていない数を$d$に代入して上式第2項を計算し、これが整数か否かを判断することで次の$(k_{m+1},S_{m+1})$を再帰的に求めればくどー問題が解けることがわかります。ある$(k_m,S_m)$の組に対し上式第2項が整数となるような$d$は一般には複数存在するため、$(k_{m+1},S_{m+1})$は複数の$d$に対してそれぞれ存在することに注意してください。$n$によっては$(k,S)$の組が$m$に対し指数的に増加し計算量が膨大になります。

この方法を用いて数値計算コードを作成すると、以前のコードと比較し計算が非常に高速化されます。前回は$5000$まででしたが、今回は$3\le n \le 10000$の$n$に関して計算を行いました。

結果は今のところ最後まで削除できる$n$は（$n=3,6$以外）見つかっていません。ただし計算量が多くなるために探索が終わっていない$n$が計37個あります。これらに最後まで削除できる数が存在する可能性があることに注意してください。

以下が$n$ vs $\mathrm{mmax}(n)$のグラフです（※$\mathrm{mmax}$: 削除可能な数の存在する削除回数$m$の最大値。Ref.kudoprob参照のこと）：

$3\le n\le 10000$における$\mathrm{mmax}(n)$（または$\mathrm{mmax}$の下限）。青い点が$\mathrm{mmax}(n)$。黄色い三角の点は計算が終わっていない$n$に対する$\mathrm{mmax}$の下限値。緑の線は$\mathrm{mmax}(n)=n-2$の線であり、これに$\mathrm{mmax}$が乗ればその$n$は最後まで削除可能。

さらにこのグラフのデータにアクセスできるグラフも載せておきます：

データにカーソルを合わせると、その点の$(n,\mathrm{mmax}(n))$が表示されます。

この図からわかることに関しては以前の記事Ref.kudoprobをご参照ください。

まとめ

Y.K.さんの提唱する方法を数値計算で実装することでコードを高速化しました。これを用い、$3\le n\le 10000$の範囲で$\mathrm{mmax}(n)$の計算を行いました。今のところ$n=3,6$以外には最後まで削除可能な$n$は見つかっていません。

実はY.K.さんとの議論の中で理論的にわかったこともあります。これに関しては次の記事で述べます。

おしまい。${}_\blacksquare$