そろそろ誰かに解いてほしい自作問題【続】(未解決)(5年振り)

2026/08/10編集中
こんにちは．私が高1のときに作った問題そろそろ誰かに解いてほしい自作問題(未解決) がネットに残っていたので久しぶりに考えてみようと思います．今回はAI(GPT5.6Sol)とスパコン(Wisteria/BDEC-01)の力を借りました．結論から言うと，今回も解けていませんが，今分かっていることをまとめておいて，また5年後くらいに考えてみようと思います．

詳細

$\mathbb{N}$の有限部分集合$A$と$x \in A$に対し，$A \setminus \{x\} $の3乗和が1乗和で割り切れるとき，$A$から$x$が削除可能という．
集合$\{1,\cdots,n(\geq3)\}$から$1,n$以外の数を一つずつ順番に削除していくとき，全ての数が削除可能な$n$は$n=3,6$に限られる．

最大削除数

各$n$に対し，最大削除数$M(n)$が定まる．全て削除可能なとき，$M(n)=n$とする($n-2$ではなく)．例えば，$M(6)=6, M(19)=15$．

!FORMULA[15][-1049071918][0]までの最大削除数 $n=1000$までの最大削除数
!FORMULA[16][1838509318][0]までの最大削除数 $n=10000$までの最大削除数
!FORMULA[17][1159214418][0]までの最大削除数 $n=100000$までの最大削除数
!FORMULA[18][1159214418][0]までの最大削除率 $n=100000$までの最大削除率
!FORMULA[19][1159214418][0]までの最大削除数(低領域) $n=100000$までの最大削除数(低領域)

図は$n=3$から$n=100000$までの最大削除数$M(n)$である．橙色は計算が終わっておらず，下限となっている(最終更新2026/08/08)．なお，下限はDFSを一定時間走らせて求めたものであり，BFSによる探索はまだこれより浅い層までしか到達していない．

最大削除数の性質

適当な状態における残存集合の，1乗和を$S$，3乗和を$T$，$k=\frac{T}{S}$とする．初期状態において，$k=S=\frac{n(n+1)}{2}$，$T=S^2$．

正準削除

$c \in \mathbb{Z}$とする．ある状態で，$k-cS=x(x-c)$とすると，$x$が削除可能であり，削除後の状態について，$k'-cS'=(x+c)x$．
よって，$x, x+c, x+2c, \cdots$の順に(まだ削除されていない数を)削除可能であり，この間，$k+cS$は一定．

上記の削除列を幅$c$の正準削除列，$k+cS$を正準削除列定数という．正準削除列は，すでに削除された数に到達すると停止する．

交換削除

$c \in \mathbb{Z}$とする．ある状態で，$k-cS=x(x-c)$，$2cS=y(y+x+c)$とすると，($x$の他に)$y$が削除可能であり，削除後の状態について，$k'-cS'=(x+c)x$．さらにこの後$x+c$が削除可能であり，削除後の状態について，$k''-cS''=(x+2c)(x+c)$，$2cS''=(y-2c)(y+x+c)$．
よって，$y, x+c, y-2c, x+3c, \cdots$の順に(まだ削除されていない数を)削除可能であり，適当な$y-2jc$を削除した後いつでも正準削除列$x+(2j+1)c, x+(2j+2)c, \cdots$に戻れる．

正準削除列の途中には上記の削除列を複数挟むことができ，$x$の代わりに$y(\neq x)$を削除することを交換削除，$y$から$y-2jc$までの一連の交換削除を交換ブロックという．以後このような交換を$(x,y)$の交換ということもある．交換削除により，すでに削除された数を飛ばして削除列が続けられる可能性がある．
幅$c$の正準削除列とその間に挟まれた(複数の)交換ブロックの一連の削除列を幅$c$のカスケードといい，カスケード内で$k-cS=x(x-c)$である状態を根が$x$(の状態)という．

幅$c$の正準削除列の途中で交換削除が始まるためには$c>0$が必要．また，$x$の代わりに交換削除できる$y$は高々1つ．

ある状態で，$k-cS=x(x-c)$，$2cS=y(y+x+c)$とする．このとき，$y$と$x$の大小関係は$k+cS$と$3x^2$の大小関係に一致する．

幅$c(>0)$のカスケードの途中，$k+cS>3x^2$において$y$を交換削除した場合$y>x$であり，$(x,y)$を高い交換，$k+cS<3x^2$において$y$を交換削除した場合$y< x$であり，$(x,y)$を低い交換という．
正準削除列から交換削除が始まる際，最初の交換の高低は直前の正準削除列定数と根の大小関係によって決まる．

1つの交換ブロック内において，交換元$x$と交換先$y$の和$t=x+y$は一定値をとり，$t$をブロック定数という．カスケードにおいて，正準削除列部分では正準削除列定数が一定，交換ブロック部分ではブロック定数が一定となる．

幅$c(>0)$のカスケード内の隣接する異なる交換ブロックを考え，
前側の削除ブロックについて，ブロック定数を$t_0$，最後の交換を$(x_0,y_0)$
後側の削除ブロックについて，ブロック定数を$t_1$，最初の交換を$(x_1,y_1)$
とする．$x_1=x_0+c$のとき，2つのブロックは接触する，$x_1 \geq x_0+3c$のとき，2つのブロックは接触しないという．なお，交換削除できる数が高々1つであることから，$x_1 = x_0+2c$の場合は同一のブロックとなり，条件に合わない．

接触

幅$c(>0)$のカスケード内の接触する交換ブロックを考え，
前側の削除ブロックについて，ブロック定数を$t_0$，最後の交換を$(x_0,y_0)$
後側の削除ブロックについて，ブロック定数を$t_1$，最初の交換を$(x_1,y_1)$
とする．このとき，$y_0 > y_1$．また，$t_0$と$t_1$の大小関係は$y_1$と$x_0$の大小関係に一致し，特に，$(x_0,y_0)$が低い交換のとき，$t_0< t_1$，$(x_1,y_1)$は低い交換となる．
また，$c=1$に限定すると，$(x_0,y_0)=(x_0,x_0+1), (x_1,y_1)=(x_0+1,x_0)$，$t_0=t_1$の形に限られる．

非接触

幅$c(>0)$のカスケード内の接触しない交換ブロックを考え，
前側の削除ブロックについて，ブロック定数を$t_0$，最後の交換を$(x_0,y_0)$
後側の削除ブロックについて，ブロック定数を$t_1$，最初の交換を$(x_1,y_1)$
とする．このとき，$y_0 > y_1$．また，$t_0$と$t_1$の大小関係は$x_1$と$y_0$の大小関係に一致し，特に，$(x_0,y_0)$が低い交換のとき，$t_0>t_1$，$(x_1,y_1)$は低い交換となる．
また，$c=1$に限定すると，
・$(x_0,y_0)$が高い交換，$y_0 > x_1$，$t_0 < t_1$
・$(x_0,y_0)$が高い交換，$y_0 = x_1$，$t_0 = t_1$，$(x_1,y_1)$は低い交換
・$(x_0,y_0)$が低い交換，$t_0>t_1$，$(x_1,y_1)$は低い交換
の3つのどれかの形に限られる．

$n/2$トリガー

$n \equiv 2 \pmod{4}$のとき，最初に$\frac{n}{2}, \frac{n+2}{2}$の順に消せる．
$n \equiv 3 \pmod{4}$のとき，最初に$\frac{n+1}{2}, \frac{n-1}{2}$の順に消せる．
つまり，$n \equiv 2,3 \pmod{4}$のとき，$M(n) \geq 2$

多くの場合，$n \equiv 0,1 \pmod{4}$で$M(n)=0$，$n \equiv 2,3 \pmod{4}$で$M(n)=2$，となっている．
初期状態からカスケードに入る，または，異なるカスケード間を移る際に，カスケードとは無関係の数を削除することがあり，このような数をトリガーという．特に，初期状態から上の命題のような削除(2枚ではなく1枚のみでも可)を行った直後にトリガーに入る場合，$n/2$トリガーという．

$n/2$トリガーと(単一の)幅$1$の正準削除列のみからなる削除列の長さは$\frac{n}{2}$未満．

$\frac{1}{2}$到達

$\displaystyle\limsup_{n\to\infty} \frac{M(n)}{n} \geq \frac{1}{2}$

例えば，$n = \frac{2}{3}(2a(a-1)-1)$，$a \equiv 2 \pmod{3}$は，$\frac{n}{2}, a, a+1, \cdots, \frac{n}{2}-1$の順で削除可能であり，$M(n) \geq \frac{n}{2}-a+1 = \frac{n}{2}- O(\sqrt{n})$．

$n/2$トリガーと(単一の)幅$1$のカスケードのみからなる削除列の長さは$\frac{\sqrt{13}-1}{4}n$未満．

最初に提示した削除率の図の$65\%$付近の一帯(計算が完了していないものが多いが)の正体はこれである．

何が起きているか簡単に説明しておく．
初期状態からのトリガーには，$n/2$トリガーと偶然トリガーの2種類がある．$M(74)=30$などは$n/2$トリガー由来(最初に$37$を削除可能)，$M(2261)=2223$などは偶然トリガー由来(最初に$2233$を削除可能)である．初期トリガーからカスケードに入ると一気に多数削除できる．今の所，数が多数削除できる要因は(既に説明した)カスケードとトリガーの組み合わせによるものしか確認できていない．また，カスケードは幅$1$のものが多い．
(幅が正の)正準削除列から交換ブロックに入れる可能性は低いが，一度入ってしまえばどこで交換ブロックを抜けるかは自由なので，多数の分岐枝が生まれる．こうなると，分岐先のどこかで交換ブロックに入れる可能性が高まり，さらに分岐が発生する．これを繰り返していくと，カスケードを抜けなくても削除列の上限長$\frac{\sqrt{13}-1}{4}n$に近づいていく上に，偶然トリガーで別のカスケードに移れる可能性もあるため，計算量が爆発する．$65\%$付近の一帯の多くが計算未完了な理由はこれである(BFSだと$50\%$にも到達しない)．スパコンを用いてこれなので，普通のPCだと計算は一生終わらない．