未解決問題議論

文献あり

【くどー問題】理論的にわかること

数値計算,整数論

323

はじめに

本記事では「くどー問題」を扱います。くどー問題の内容、および本記事で用いられる表記については以下をご参照ください（項目をクリックすると展開されます）

くどー問題とは

そろそろ誰かに解いてほしい自作問題(未解決) から引用させて頂きます：

$1$ から $n (\geq 3)$ までの整数が書かれたカードが1枚ずつある。この時、以下の条件を満たしながらカードを1枚ずつ取り除いていくことを考える。

【条件】
1. どの時点においても「カードに書かれた数の3乗和」が「カードに書かれた数の和」で割り切れる
2. $1$ と $n$ のカードは最後の2枚になるまで残す

この時、条件を満たしながらカードがなくなるまで取り除くことができるような $n$ は無数に存在するか？

表記に関して

$n$ : カードに書かれた数の集合 ${1, 2, \dots, n}$ のうちの最大の数
$m$ : 削除されたカードの枚数
$d (d_{m})$ : 削除されたカードに書かれた数（ $m$ 枚目に削除されるカードに書かれた数）。「削除する数」、「削除可能な数」などとも呼ぶ
削除列: 削除されたカードに書かれた数の列。 $[d_{1}, d_{2}, \dots, d_{m}]$ のこと。「削除可能な数の列」、 $Delete (n; m)$ と記すこともある
$mmax (n)$ : ある $n$ に対し、削除可能な数が存在する最大の $m$
$S (S_{m})$ : 残りのカードに書かれた数の和 ( $m$ 枚の削除後の残りのカードに書かれた数の和)。 $S_{0} := n (n + 1) / 2$
$T (T_{m})$ :残りのカードに書かれた数の3乗和 ( $m$ 枚の削除後の残りのカードに書かれた数の3乗和) 。 $T_{0} := {(n (n + 1) / 2)}^{2}$
$k_{m}$ : (残りのカードに書かれた数の3乗和)/(残りのカードに書かれた数の和)。すなわち $k_{m} := T_{m} / S_{m}$
$k_{m}^{(diff)}$ : 以下で定義される
$\begin{array}{r} k_{m}^{(diff)} := \frac{d_{m} (k_{m - 1} - d_{m}^{2})}{S_{m - 1} - d_{m}} (m \geq 1) \end{array}$
このとき以下が成立する（【くどー問題】Y.K.さんの方法参照のこと）
$\begin{array}{r} k_{m} = k_{m - 1} + k_{m}^{(diff)} (m \geq 1, k_{0} := T_{0} / S_{0} = S_{0} \in N) \end{array}$
$k_{m}^{(diff)}$ が整数になるように $d_{m}$ を選ぶことで削除列を構成することができる。

また、関連記事にRefs.kudoprob_01 kudoprob_02 kudoprob_03 kudoprob_04があります。

数値計算でわかること

本記事では「くどー問題」の理論的な解析に関して述べます。その前に本章では数値計算からわかっていることを記します。そしてこれらの事実を理論的な観点からどれだけ説明できるかを示します。

まず現在のところ、 $3 \leq n \leq 10000$ において、最後まで削除可能な $n$ は $n = 3, 6$ しか見つかっていません。

図1が $3 \leq n \leq 10000$ に対する $mmax (n)$ のグラフです（ $mmax$ に関しては「表記」の項目参照のこと）：

!FORMULA[35][38042][0] vs !FORMULA[36][1665667463][0]のグラフ。青い点は計算が終わっているデータ。黄色い三角は計算が終わっておらず、!FORMULA[37][1665667463][0]の下限値を示している。緑の直線は!FORMULA[38][2010706321][0]であり、これにデータが乗ればその数は最後まで削除可能。 $n$ vs $mmax (n)$ のグラフ。青い点は計算が終わっているデータ。黄色い三角は計算が終わっておらず、 $mmax (n)$ の下限値を示している。緑の直線は $mmax (n) = n - 2$ であり、これにデータが乗ればその数は最後まで削除可能。

黄色い三角の点は計算量が多くなるため計算が未完了な $n$ に関する $mmax (n)$ の下限です。緑の線は $mmax (n) = n - 2$ です。これにデータが乗ればその $n$ は最後まで削除可能です。上の図のデータにアクセスできるインタラクティブな図は以下です：

図1のインタラクティブな図

この図は拡大・縮小することができ、データ点にカーソルを合わせると $(n, mmax (n))$ が表示されます。また、削除列に関する特徴の解説が「くどー問題」再びの「 $Delete (n; m)$ の $m$ 依存性」の章にあるのでご参照ください。

これらのデータから明らかにわかることが4つほどあります：

数値計算からわかる事実

大きな $n$ では基本的に $mmax (n) = 0, 0, 2, 2, 0, 0, 2, 2, \dots$ となる。時折例外が存在する。
$mmax (n) ≃ n / 2$ となる一群の $n$ が存在する。
最初に削除できる数字は $n / 2$ または $(n + 1) / 2$ である場合が多い
削除列には連続した整数が並ぶことが多い。特に $mmax (n) ≃ n / 2$ となる $n$ の場合、削除列は基本的に1つのみ、かつずっと連続する整数が並ぶ

1.2.は上に挙げた図から、3.4.は削除列を見ることでわかります。以下これらを（ある程度）理論的に説明します。

理論的にわかること

m=1,2で削除できる数に関して

$m = 1, 2$ で削除可能な数に関して考察します。

$n$ を4で割った余りで分類します。このとき以下が示せます：

$n = 4 k + 2 (k \in N)$ のとき、 $m = 1$ において $n / 2 = 2 k + 1$ は削除できる。これに続き、 $m = 2$ では $n / 2 + 1 = 2 k + 2$ が削除できる
$n = 4 k + 3$ のとき、 $m = 1$ において $(n + 1) / 2 = 2 k + 2$ は削除できる。これに続き、 $m = 2$ では $(n - 2) / 2 = 2 k + 1$ が削除できる
$n = 4 k$ のとき $m = 1$ で $n / 2 = 2 k$ は削除できない。
$n = 4 k + 1$ のとき $m = 1$ で $(n + 1) / 2 = 2 k + 1$ は削除できない。

1.2.は具体的に代入すればすぐに証明できますし、3.4.も簡単にわかると思います。

ここで $n$ が大きい時、

【仮定1】 $m = 1$ ではほとんどの場合 $n / 2$ or $(n + 1) / 2$ しか削除できない
【仮定2】上に示した $n = 4 k + 2, 4 k + 3$ における $m = 1, 2$ の削除列は殆どの場合途切れ、 $m = 3$ では削除可能な数字が存在しない

を仮定します。公式1および【仮定1】【仮定2】は
$\begin{array}{r} mmax (n) = 0, 0, 2, 2, 0, 0, 2, 2, \dots for large n \end{array}$
という、数値計算でわかっている振る舞いを導きます。

【仮定1】【仮定2】が成立する理由は今のところちゃんとはわかっていません。ただしわかっていることもあります。【仮定1】に関連し、Y.K.さんの以下の証明が存在します：

【仮定1】に関連した定理（Y.K.さんによる）

$m = 1$ で削除可能な数 $d$ に関し、 $S_{0} = n (n + 1) / 2$ と $d$ が互いに素なら、 $d$ は削除できない

くどー問題のメモを参照のこと（ただし定理1で $d$ と記したものは、Y.K.さんの記事では $m$ と記されていることに注意） $_{◼}$

これらの仮定に関してはもうすこし考察の必要がありそうです。

「数値計算からわかる事実」の2.4.に関して

本章では、前記した「数値計算からわかる事実」の2.4.が密接に関連しており、説明が可能であることを述べます。すなわち $mmax (n) ≃ n / 2$ となる一群の $n$ の存在と削除列に連続した整数が並ぶことの関係とその説明を与えます。

前回の記事でY.K.さんに教えて頂いたくどー問題の数値計算法に関して説明しました。実はこの方法で計算すると、 $d_{m}$ と $k_{m}^{(diff)}$ の間に著しい特徴があることに気付きます（記号の意味に関しては「表記」参照のこと）。例えば $n = 1322$ の削除列の最初の方を見てみましょう：

      #########
n: 1322
- m: 1
(diffk,list_d): [(331, [661])]
- m: 2
(diffk,list_d): [(32, [661, 32]), (331, [661, 662])]
- m: 3
(diffk,list_d): [(33, [661, 32, 33])]
- m: 4
(diffk,list_d): [(34, [661, 32, 33, 34])]
- m: 5
(diffk,list_d): [(35, [661, 32, 33, 34, 35])]
︙
##########

丸括弧内の最初の数値は $k_{m}^{(diff)}$ です。 $k_{m}^{(diff)}$ の隣の角括弧の中の数字が削除列です。 $m = 1$ で削除可能な数は $661$ のみです。 $m = 2$ では削除可能な数が2つ、 $32$ と $662$ が存在します。削除列 $[661, 662]$ の次に削除できる数字が存在しないため、 $m = 3$ では削除列は1つに戻ります。

この結果を見ると
$\begin{array}{r} k_{m}^{(diff)} = d_{m} \end{array}$
が $m = 2$ の1つ目の削除列で成立し、その後ずっとこの関係が保たれるという著しい特徴があることがわかります。実はある程度 $mmax (n)$ が大きくなる $n$ では、多くの場合、 $m = 2, 3, 4$ のどれかからこの関係が成立する削除列が存在します。その理由は以下の事実によります：

ある $m$ に対して $d_{m} = a \in N$ が削除可能であり、かつ以下を満たすとする：
$\begin{array}{r} \frac{a (k_{m - 1} - a^{2})}{S_{m - 1} - a} = a (すなわち k_{m - 1} - a^{2} = S_{m - 1} - a) \end{array}$
このとき $d_{m + 1} = a + 1$ は削除可能であり、かつ以下が成立する：
$\begin{array}{r} \frac{(a + 1) (k_{m} - (a + 1)^{2})}{S_{m} - (a + 1)} = a + 1 \end{array}$

定理1からわかるのは、ある $m$ で $k_{m}^{(diff)} = d_{m}$ が成立するなら、( $m + 1$ )回目の削除では $d_{m + 1} = d_{m} + 1$ が削除可能であり、かつ $k_{m + 1}^{(diff)} = d_{m + 1}$ が成立するということです。これが削除列に連続した整数が存在する理由かと思います。公式1が成立することは
$\begin{array}{r} k_{m} - (a + 1)^{2} = k_{m - 1} + a - (a + 1)^{2} = k_{m - 1} - a^{2} - (a + 1) \\ = S_{m - 1} - a - (a + 1) \\ ∴ \frac{k_{m} - (a + 1)^{2}}{S_{m} - (a + 1)} = \frac{S_{m - 1} - a - (a + 1)}{S_{m - 1} - a - (a + 1)} = 1 \end{array}$
からすぐにわかります。

さらにこのことから $mmax (n) ≃ n / 2$ となる一連の $n$ が存在することもわかります。なぜなら $mmax$ が大きくなる $n$ に関して $n / 2$ or $(n + 1) / 2$ は多くの場合最初に削除されてしまっているので、 $d$ がこの値まで到達すると連鎖が途切れるからです。

また、たとえ最初に $n / 2$ or $(n + 1) / 2$ が削除されていなかったとしても、最初に $k_{m}^{(diff)} = d_{m}$ が成立する $d_{m}$ が $m$ より2以上大きいなら、すべての数字が削除されることはなく、この削除列は必ず途切れます。すなわちこのような削除列はそれ単独で最後の数字まで削除できるということはないです。

ちなみに最後まで削除可能な $n = 3, 6$ における $d$ と $k^{(diff)}$ は以下のようになります:
$\begin{aligned} n = 3 : & d_{1} = 2, k_{1}^{(diff)} = 1 \\ n = 6 : & d_{1} = 3, k_{1}^{(diff)} = 2 \\ d_{2} = 4, k_{2}^{(diff)} = 2 \\ d_{3} = 5, k_{3}^{(diff)} = 0 \\ d_{4} = 2, k_{4}^{(diff)} = 6 \end{aligned}$
これらの $n$ では $d_{m} = k_{m}^{(diff)}$ が成立することはないです。

計算が終わってない $n$ におけるinf(mmax)の改善

前章の考察から、計算が重く探索の終わっていない $n$ （図1の黄色い三角の点）の $mmax$ の下限を改善することができます。

上記した $n = 1322$ の削除列の連続した整数がどこまで続くか考えると、 $661$ が最初に削除されているため $660$ まで続いて途絶えます。ということは、この削除列は $m = 660 - 32 + 2 = 630$ まで続くことになります。これは $mmax$ の下限です。これ以外の系列の削除列が存在する可能性はありますし、 $n = 1322$ では実際存在します。

このようにして計算が終わっていない $n$ に対して $mmax$ の下限を改善した図が以下です：

図1において、理論的な考察から計算が未完了のデータ（黄色い三角の点）の $mmax (n)$ の下限の改善を行ったもの

対応するインタラクティブなグラフは以下です：

図2のインタラクティブなグラフ

計算の終わってない $n$ のうちひとつだけ、 $n = 1456$ の $mmax$ の下限に関しては、理論的な考察よりも現在完了している数値計算による下限の方が大きな値を与えます。

まとめ

本記事では、くどー問題に関して理論的にわかっていることを述べました。 $mmax (n)$ が $n$ の大きいところで $0, 0, 2, 2, 0, 0, 2, 2, \dots$ という繰り返しの構造を持つこと、削除列が連続した整数から構成されること、さらに $mmax (n) ≃ n / 2$ となる一群の $n$ が存在する理由に関して（大雑把に）説明を与えました。

ここまで行った考察以外に、理論的にも数値的にもできることとして、「逆方向の探索」があります。これは ${1, n}$ から始め、「3乗和/1乗和が整数となる」ように数を追加していく方法です。コメント欄でtanuさんにご指摘頂いたのですが、これを考察すると、順方向の探索において「最後まで残しておかなければならない数」（＝「追加する数の列」の全てに共通して存在する数）が見つかるかもしれません。順方向の探索でどの削除列にもこの数が存在するなら、その $n$ において最後まで削除することは不可能です。特に数値計算が重くなる $n$ に対してこの考察をすることは有益かと思います。