切手問題

数学的には、問題は次のように定式化される。

整数 m と正の整数の集合 V が与えられたとき、k ≤ m なる k 個の要素の和 v₁ + v₂ + ··· + v_k で表せない最小の整数 z を求めよ。

Summarize Timeline Top Qs Fact Check

n種類を適切に選ぶと、2枚の切手での解は最大で

2, 4, 8, 12, 16, 20, 26, 32, 40, 46, 54, 64, 72, 80, 92, 104, 116, 128, 140, 152, 164, 180, 196, 212,... (オンライン整数列大辞典の数列 A001212)

となる。

例えば、順に

${\displaystyle {\begin{array}{ll}\{1\}&\to 1,1+1\\\{1,3\}&\to 1,1+1,3,3+1\\\{1,3,4\}&\to 1,1+1,3,4,4+1,3+3,4+3,4+4\\\{1,3,5,6\}&\to 1,1+1,3,3+1,5,6,6+1,5+3,6+3,5+5,6+5,6+6\end{array}}}$

となる。

2 種類を適切に選ぶと、h枚の切手での解は最大で

2, 4, 7, 10, 14, 18, 23, 28, 34, 40, 47, 54, 62, 70, 79, 88, 98, 108, 119, 130, 142, 154, 167, 180,... (オンライン整数列大辞典の数列 A014616)

となる。

例えば、順に

${\displaystyle {\begin{array}{ll}\{1,2\}&\to 1,2\\\{1,3\}&\to 1,1+1,3,3+1\\\{1,3\}&\to 1,1+1,3,3+1,3+1+1,3+3,3+3+1\\\{1,4\}&\to 1,1+1,1+1+1,4,4+1,4+1+1,4+1+1+1,4+4,4+4+1,4+4+1+1\end{array}}}$

となり、一般に${\displaystyle \{1,\lfloor (h+4)/2\rfloor \}}$の切手を用意することで最大化でき、その解は

${\displaystyle \left\lfloor {\frac {1}{4}}(h^{2}+6h+1)\right\rfloor }$

と表せる^[2]。

3種類を適切に選ぶと、 h 枚の切手での解は最大で

3, 8, 15, 26, 35, 52, 69, 89, 112, 146, 172, 212, 259, 302, 354, 418, 476, 548, 633, 714, 805, 902, 1012, 1127, 1254, 1382,... (オンライン整数列大辞典の数列 A001208)

となる。

n ≥ 20 のとき

${\displaystyle \beta =\left\lfloor {\frac {4h+4}{9}}\right\rfloor +2,\gamma =\left\lfloor {\frac {2}{9}}h\right\rfloor +2}$

とおくと

${\displaystyle a_{1}=1,a_{2}=2\beta -\gamma +1,a_{3}=\gamma a_{2}-\beta }$

が h 枚の切手での最大の解を与え、その最大の解は

${\displaystyle (h+4-\beta -\gamma )a_{3}+(\gamma -2)a_{2}+(\beta -2)a_{1}={\frac {4}{81}}h^{3}+{\frac {2}{3}}h^{2}+Ah+B,}$

ここで A, B は

${\displaystyle (A,B)={\begin{cases}\left({\frac {22}{9}},0\right)&(n\equiv 0{\pmod {9}}),\\\left({\frac {68}{27}},{\frac {62}{81}}\right)&(n\equiv 1{\pmod {9}}),\\\left({\frac {71}{27}},-{\frac {26}{81}}\right)&(n\equiv 2{\pmod {9}}),\\\left({\frac {23}{9}},0\right)&(n\equiv 3{\pmod {9}}),\\\left({\frac {68}{9}},-{\frac {154}{81}}\right)&(n\equiv 4{\pmod {9}}),\\\left({\frac {68}{27}},{\frac {46}{81}}\right)&(n\equiv 5{\pmod {9}}),\\\left({\frac {23}{9}},-1\right)&(n\equiv 6{\pmod {9}}),\\\left({\frac {71}{27}},-{\frac {1}{81}}\right)&(n\equiv 7{\pmod {9}}),\\\left({\frac {68}{27}},-{\frac {170}{81}}\right)&(n\equiv 8{\pmod {9}})\end{cases}}}$

となる ^[3][4][5]。

この問題は、 総当たりまたはバックトラッキングで |V|^m の定数倍時間で解くことができる。ここで |V| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 m が定数である場合、多項式時間で解ける問題である。容量 m が任意の場合、問題はNP困難である^[1]。