ネックレスの分裂問題

ネックレス分割は、組合せ論と測度論におけるいくつかの関連する問題に付けられた美しい名前です。その名前と解は、数学者のノガ・アロン^[1]と ダグラス・B・ウェスト^[2]によるものです。

基本的なセッティングは、異なる色のビーズが付いたネックレスです。ネックレスは複数のパートナー（泥棒など）に分け、各パートナーが各色を同じ量受け取るようにします。また、カットの数はできるだけ少なくする必要があります（ビーズ間のリンクの金属をできるだけ無駄にしないようにするため）。

元の論文では、次の問題のバリエーションが解決されています。

1. 離散分割: ^{[1] : Th 1.1}ネックレスにはビーズが2つ付いています。ビーズには様々な色があります。各色にビーズが 個あり、 は正の整数です。ネックレス全体を、各部分に色iのビーズがちょうど含まれる部分に分割します (必ずしも連続している必要はありません)。最大で回切り込みを入れます。各色のビーズがネックレス上で連続している場合は、各色の内部で少なくとも回切り込みを入れる必要があるため、が最適です。${\displaystyle k\cdot n}$${\displaystyle t}$${\displaystyle k\cdot a_{i}}$${\displaystyle i}$${\displaystyle a_{i}}$${\displaystyle k}$${\displaystyle a_{i}}$${\displaystyle (k-1)t}$${\displaystyle k-1}$${\displaystyle (k-1)t}$
2. 連続分割: ^{[1] : Th 2.1} ネックレス は実区間 です。区間の各点は、異なる色のいずれかで色付けされます。すべての色 について、 で色付けされた点の集合はルベーグ測定可能で、長さ を持ちます。ここで は非負の実数です。区間を部分 (必ずしも連続している必要はありません) に分割し、各部分で色の合計の長さがちょうどになるようにします。最大で 回のカットを使用します。${\displaystyle [0,k\cdot n]}$${\displaystyle t}$${\displaystyle i}$${\displaystyle i}$${\displaystyle k\cdot a_{i}}$${\displaystyle a_{i}}$${\displaystyle k}$${\displaystyle i}$${\displaystyle a_{i}}$${\displaystyle (k-1)t}$
3. 測度分割: ^{[1] : Th 1.2} ネックレス は実区間です。区間には異なる測度があり、すべて長さに関して絶対連続しています。ネックレス全体の測度は、測度 に従って、 です。区間を部分 (必ずしも連続している必要はありません) に分割し、各部分の測度は、測度 に従って、ちょうど になります。最大で 回までカットします。これは、ホビー–ライスの定理の一般化であり、ケーキを正確に分割するために使用されます。${\displaystyle t}$${\displaystyle i}$${\displaystyle k\cdot a_{i}}$${\displaystyle k}$${\displaystyle i}$${\displaystyle a_{i}}$${\displaystyle (k-1)t}$

それぞれの問題は次の問題によって解決できます。

• 離散分割は連続分割で解決できる。離散ネックレスは、長さ 1 の各間隔が対応するビーズの色で色付けされた実間隔の色付けに変換できるからである。連続分割がビーズの内側を切断しようとする場合、切断はビーズの間だけで行われるように徐々にスライドさせることができる。^{[1] : 249}${\displaystyle [0,k\cdot n]}$
• 連続分割は測度分割によって解決できる。なぜなら、色の区間の色分けは、測度が色の合計の長さを測定するような測度の集合に変換できるからである。逆もまた真なりで、測度分割は、より洗練された縮約法を使って連続分割によって解決できる。^{[1] : 252–253}${\displaystyle t}$${\displaystyle t}$${\displaystyle i}$${\displaystyle i}$

このケースはボルスク・ウラム定理によって証明できる。^[2]${\displaystyle k=2}$

が奇数の素数である場合、証明にはボルスク・ウラム定理の一般化が必要となる。^[3]${\displaystyle k}$

が合成数の場合、証明は次のようになります（測度分割法で示しています）。 と仮定します。 複数の測度があり、それぞれの測度はネックレス全体を と評価します。カットを使用して、ネックレスを各部分の測度がちょうど になるように部分に分割します。 カットを使用して、各部分を各部分の測度がちょうど になるように部分に分割します。全体として、各部分の測度がちょうど になる部分が存在します。 カットの総数はと加算され、ちょうど になります。 ${\displaystyle k}$${\displaystyle k=p\cdot q}$${\displaystyle t}$${\displaystyle p\cdot q\cdot a_{i}}$${\displaystyle (p-1)\cdot t}$${\displaystyle p}$${\displaystyle i}$${\displaystyle q\cdot a_{i}}$${\displaystyle (q-1)\cdot t}$${\displaystyle q}$${\displaystyle i}$${\displaystyle a_{i}}$${\displaystyle pq}$${\displaystyle i}$${\displaystyle a_{i}}$${\displaystyle (p-1)\cdot t}$${\displaystyle p(q-1)\cdot t}$${\displaystyle (pq-1)\cdot t}$

場合によっては、ランダムなネックレスは、より少ないカットで均等に分割できます。数学者のノガ・アロン、ドール・エルボイム、ガボール・タルドス、ヤノシュ・パクは、2人の泥棒がランダムなネックレスを分割するために必要なカットの典型的な回数を研究しました。^[4]彼らが検討したモデルでは、t色と各色のm個のビーズを持つネックレスのセットから、ネックレスが一様にランダムに選択されます。mが無限大に近づくにつれて、ネックレスを⌊(t + 1)/2⌋以下のカットで分割できる確率はゼロに近づきますが、⌊(t + 1)/2⌋ + 1回のカットで分割できる確率はゼロから離れる方向に制限されます。より正確には、X  =  X ( t , m ) をネックレス分割に必要な最小のカット回数とします。mが無限大に近づくにつれて、次の式が成り立ちます。任意の${\displaystyle s<(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}m^{s-(t+1)/2}{\big )}.}$

いかなる${\displaystyle (t+1)/2<s\leq t}$

${\displaystyle \mathbb {P} (X=s)=\Theta (1).}$

最後に、奇数と${\displaystyle t}$${\displaystyle s=(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}(\log m)^{-1}{\big )}.}$

色の数が無限大に近づく場合も考えられます。m =1でtが無限大に近づく場合、必要なカットの数は最大0.4t、最小0.22tになる確率が高くなります。分布的にX ( t ,1)/ tがc  に収束する ような0.22< c <0.4が存在すると推測されます 。

2人の泥棒[つまりk = 2]とt色の場合には、公平な分割には最大でt回のカットが必要です。しかし、t  − 1回のカットしか利用できない場合、ハンガリーの数学者Gábor Simonyi ^[5]は、 2人の泥棒が次の意味でほぼ公平な分割を達成できることを示しています。

t分割が不可能なようにネックレスが配置されている場合、 {1, 2, ...,   t  }の任意の 2 つの部分集合D ₁とD _{2 （}両方とも空ではない）に対して、次のような( t  − 1) 分割が存在する。 ${\displaystyle D_{1}\cap D_{2}=\varnothing }$

• 色 の場合、パーティション 1 にはパーティション 2 よりも色iのビーズが多くあります。${\displaystyle i\in D_{1}}$
• 色 の場合、パーティション 2 にはパーティション 1 よりも多くの色iのビーズがあります。${\displaystyle i\in D_{2}}$
• 色iがどちらのパーティションにも含まれていない場合は、両方のパーティションに色iのビーズが同じ数存在します。

これは、泥棒が 2 つの「好み」セットD ₁とD ₂の形で好みを持ち、両方が空でない場合、( t − 1) 分割が存在し 、泥棒 1 は好みセットD _{1で泥棒 2 よりも多くの種類のビーズを取得し、泥棒 2 は好みセット}D ₂で泥棒 1 よりも多くの種類のビーズを取得し、残りは等しいことを意味します。

Simonyi は、上記の結果がk = 2 の場合の Alon の元のネックレス定理の直接的な一般化であることに気付いた Gábor Tardos の功績を認めています。ネックレスには ( t  − 1) 分割があるか、ないかのどちらかです。分割がある場合は証明する必要はありません。分割がない場合は、ネックレスに架空の色のビーズを追加し、D _{1 を}架空の色で構成し、D _{2 を空にします。すると、Simonyi の結果は、実際の色がそれぞれ同数ある}t分割があることを示します。

任意の実数直線に対して、最大で何回かのカットで区間を公平に分割できないような測定可能な -色付けが存在する。^[6]${\displaystyle k\geq 1}$${\displaystyle (k+3)}$${\displaystyle k}$

この結果は、 k人 の泥棒の側面に平行なn ( k −1)個 の超平面の任意の組み合わせを持つd次元立方体上で定義されたn個の確率測度に一般化できる。^[7]

ネックレスを分割するための近似アルゴリズムは、コンセンサス半減アルゴリズムから導き出すことができる。^[8]

• 組み合わせネックレス
• ネックレスの問題
• 正確な除算

• YouTube の「Sneaky Topology」は、問題とその位相的解決法を紹介する入門ビデオです。