Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

あなたは、正確に $n$ 個のユニークなレンガ（1から $n$ まで番号が付いている）を使って都市を築く任務を与えられた、熟練の建築家であると想像してください。あなたの目標は、単にそれらを積み上げることではありません。あなたはそれらを「近隣住区（パート）」と呼ばれるグループに分ける必要がありますが、そこには2つの厳格なルールが適用されます。第一に、近隣住区が混みすぎることがあってはなりません。つまり、最大で $m$ 個のレンガを収容できます。第二に、各近隣住区におけるレンガの総重量は、特定の魔法の数 $m$ の完全な累乗（例えば $m^0=1, m^1=m, m^2$ など）でなければなりません。このパズルは、組み合わせ論という分野に属しています。これは、物事がどのように配置され、数えられ、グループ化されるかを研究する数学の一分野です。これは、巨大で無限に続く数独を解くようなもので、グリッドのサイズによってルールが変わります。数学者たちがこの問題を重視するのは、数字がどのように分解され、再構築されるかを理解することが、原子の結合を理解することが新しい材料の構築に役立つのと同様に、数学の構造に関する深い秘密を明らかにすることになるからです。

あなたがこれから読む論文は、このパズルの特定の、非常にトリッキーなバージョンを取り扱っています。著者であるウラジミール・グルヴィッチとマリア・ナウムワは、魔法の数 $m$ を 3 に設定しました。これは、彼らが 1 から $n$ までの数字を、サイズが 1、2、または 3 のグループに分け、各グループの和が 3 の累乗（1, 3, 9, 27 など）になるようにすることを意味します。彼らは、$m=2$ の場合には、任意の $n$ に対して常に正確に1通りの方法があることをすでに知っていました。また、$m$ が 3 より大きい場合、無限に多くの $n$ の値に対してそのパズルは不可能であることを知っていました。しかし、$m=3$ の場合、答えは謎でした。著者たちは、$n$ がどんなに大きくても、すべての $n$ に対して解が存在するという仮説（コンジェクチャー）を立てています。

これを検証するために、彼らは単に推測しただけではありません。彼らは数学的なセーフティネットを構築しました。もしある $n$ に対して解が存在しないとしたら、その「悪い」数字は、非常に特定的で奇妙な形をしていなければならないことを彼らは証明しました。それは $n = 3t + 3k + 2$ という形であり、かつ他の特定のパターンを避けていなければなりません。これは、探偵が「もし犯行が行われたなら、容疑者は赤い帽子を被り、足を引きずり、左利きでなければならない」と言うようなものです。もし、その記述に当てはまらない容疑者を見つけたなら、その人は犯人ではないと分かります。著者たちは、この論理を用いて、膨大な数の範囲を排除しました。また、844までのすべての数字をチェックするためにコンピュータ・シミュレーションを実行し、あらゆるケースにおいて解が見つかりました。彼らはさらに、「準分割（クアジ・パーティション）」と呼ばれる、一つの数字が2回使われることを許容する、少し緩やかなバージョンのパズルも調査し、そこでも解が存在することを証明しました。彼らはまだ、すべての $n$ に対してパズルが解けることを証明してはいませんが、反例の探索範囲を非常に小さく特定のリストへと絞り込んでおり、ほとんどの $数字$ に対して、解は可能であるだけでなく、しばしば一意的であると確信しています。

数をグループ化する偉大なゲーム

数字のタイルが入った袋を想像してください。タイルには 1 からある大きな数 $n$ までの番号が付いています。あなたの仕事は、これらのタイルをいくつかの山に仕分けることです。しかし、ルールがあります！

1. サイズのルール: 各山には最大 3 枚のタイルを入れることができます。
2. 和のルール: 各山の数字の合計は「3の累乗」でなければなりません。つまり、合計は 1, 3, 9, 27, 81... となる必要があります。

これが「3-good partition（3-グッド分割）」問題です。著者たちは、次のような単純だが頑固な問いを投げかけています。「どれほど多くのタイルから始めても、これは常にできるのだろうか？」

長い間、数学者たちは「2-good」分割（最大2枚のタイルで、和が2の累乗となるもの）の答えを知っていました。それは、常に正確に1通りの方法があることが分かっています。しかし、3 の場合はルールが複雑になります。著者たちは、答えは「はい、常に可能です」ではないかと考えていますが、それを証明する必要がありました。

「クリティカル」な容疑者たち

すべての数字について証明しようとする（それは困難な作業です）代わりに、著者たちは「悪い奴ら」、つまり失敗する数字を探すことに決めました。彼らは、もしそのような「クリティカル（決定的な）」数字が存在するとしたら、それは非常に特殊な姿をしているはずだと考えました。

もしそのようなクリティカルな数字が存在するならば、それは単なるランダムな数字ではあり得ないと彼らは証明しました。それは以下の形をしていなければなりません：
$$n = 3t + 3k + 2$$
そして、$k$ が $t$ に対してどの程度大きいかについての追加条件を満たさなければなりません。

これは、クラブのセキュリティガードのようなものです。ガードは言います。「もしチケットなしで忍び込もうとするなら、緑の帽子を被り、青いバッグを持っていなければならない」。もし赤い帽子を被っている人を見かけたら、その人は決して忍び込みの侵入者ではないと分かります。著者たちは、この「緑の帽子」の説明に当てはまらない数字は安全であることを証明しました。これにより、膨大な可能性が排除されました。

コンピュータによるチェック

彼らの巧みな数学を用いても、まだ「緑の帽子」の説明に当てはまる数字は残っていました。念のため、著者たちは（プログラマーのドミトリー・リビンと共に）プログラムを作成し、844 までのすべての数字をチェックしました。

• 結果: 1 から 844 までのすべての数字について、タイルを完璧にグループ化する方法が見つかりました。
• 結論: コンピュータは、たった一つの「悪い」数字も見つけませんでした。これは、このパズルがすべての人に対して解けるという彼らの予想を強く支持しています。

「準分割」のひねり

著者たちは、少し異なるゲームも試しました。もし一つの数字を「2回」使うことが許されたらどうなるでしょうか？彼らはこれを「準分割（クアザイ・パーティション）」と呼んでいます。例えば、数字の 3 のスペア・タイルを持っていて、それを2つの異なる山に使うことができると考えてください。
彼らは、特定の範囲の数字について、このバージョンのパズルを常に解くことができること、そして数字 3（具体的には $3^t$）が2回使われることを証明しました。これは、より難しい問題への有用な足掛かりとなりました。

いくつの方法があるのか？

この論文の最も興味深い部分の一つは、数字をグループ化する異なる方法の数を数えることです。

• 一部の数字（1, 2, 3, 4 やその他の多くの数字）については、正確に1通りの方法しかありません。それは、鍵が一つしかない錠前のようなものです。
• 数字 13 や、$3t - 3$ のような数字については、正確に2通りの方法があります。
• それ以外のほとんどの数字については、2通りよりも多い方法があると彼らは考えています。

彼らはさらに、もし解に含まれる3つの数字の組（トリプレット）を知っていれば、パズル全体を解くことができるという特別なルール（命題2）を発見しました。これは、「もし部屋にいる3人の親友が誰であるかを知っていれば、その場の人間関係のすべてが分かる」と言うようなものです。

結論

著者たちは、宇宙のすべての数字に対してこのパズルを解いたわけではありません。まだ、数学的に完全にクリアできていないトリッキーな数字（35, 38, 89, 101 など）がいくつか残っています。しかし、もし解が存在しないとしたら、それはこれらのような非常に特殊で稀な数字であるはずだと、彼らは示しました。

彼らは、「3-good partition」がすべての $n$ に対して存在するという確信を持っています。彼らは簡単な失敗例を排除し、最初の844個の数字をコンピュータでチェックし、パズルには常に解があることを見つけました。謎は、果たしてすべての数字に対してグループ化ができるかということではなく、本当に大きな数字に対して、それが「何通り」の方法で行えるのかということです。すべての数字に対して証明するという旅は続いていますが、その道筋は今、より明確になっています。