切手問題のソースを表示


'''切手問題'''とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める[[数学]]の問題である<ref name=arxiv>Jeffrey Shallit (2001), [https://arxiv.org/abs/math.NT/0112257 ''The computational complexity of the local postage stamp problem'']. SIGACT News 33 (1) (March 2002), 90-94.  Accessed on 2009-12-30.</ref>。封筒の面積の制約上、貼ることのできる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。 

例えば、封筒には3枚の切手しか貼ることができないとする。使用可能な切手の額面が1円、2円、5円、15円の場合、12円までの金額は3枚までの切手で構成できる（例えば、4=2+2、8=5+2+1、11=5+5+1）。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。 

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

: 整数 ''m'' と正の整数の集合 ''V'' が与えられたとき、''k'' &le; ''m'' なる ''k'' 個の要素の和 ''v''<sub>1</sub> + ''v''<sub>2</sub> + ··· + ''v''<sub>''k''</sub> で表せない最小の整数 ''z'' を求めよ。 

== 特殊な場合 ==
=== ''n'' 種類、2枚の切手での解 ===
''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,... ({{OEIS|A001212}})
となる。

例えば、順に
: <math>\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}</math>
となる。

=== 2 種類、''h'' 枚の切手での解 ===
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,... ({{OEIS|A014616}})
となる。

例えば、順に
: <math>\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}</math>
となり、一般に<math>\{1,\lfloor(h+4)/2\rfloor\}</math>の切手を用意することで最大化でき、その解は
: <math>\left\lfloor \frac{1}{4}(h^{2}+6h+1)\right\rfloor</math>
と表せる<ref>{{cite article| first1=Alfred | last1=Stöhr | title= Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. I |journal = J. reine angew Math. | volume=194 | year= 1955 | pages=40-65 | doi=10.1515/crll.1955.194.40 | url=https://eudml.org/doc/150281 | MR=0075228 }}</ref>。

=== 3 種類、''h'' 枚の切手での解 ===
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,... ({{OEIS|A001208}})
となる。

''n'' &ge; 20 のとき
:<math>\beta=\left\lfloor\frac{4h+4}{9}\right\rfloor +2, \gamma=\left\lfloor\frac{2}{9}h\right\rfloor +2</math>
とおくと
:<math>a_1=1, a_2=2\beta -\gamma +1, a_3=\gamma a_2-\beta</math>
が  ''h'' 枚の切手での最大の解を与え、その最大の解は
:<math>
(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,
</math>
ここで ''A'', ''B'' は
:<math>
(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}
</math>
となる
<ref>{{cite journal| first1=Svein | last1=Mossige | title= Algorithms for Computing the ''h''-Range of the Postage Stamp Problem | journal = Math. Comp. | volume=36 | number=154 | year=1981 | pages=575-582 | doi=10.1090/S0025-5718-1981-0606515-1 | mr=0606515 }}</ref><ref>{{cite journal| first1=Gerd | last1=Hofmeister | title= Die dreielementigen Extremalbasen | journal = J. reine angew Math. | volume=339 | year=1983 | pages=207-214 | doi=10.1515/crll.1983.339.207 | url=https://eudml.org/doc/152515 | mr=0686707 }}</ref><ref>{{cite journal|first1=M. F. | last1=Challis| title=Two new techniques for computing extremal ''h''-bases ''A''<sub>''k''</sub> |journal=Comput. J. | volume=36|number=2 | pages=117–126| year=1993 |doi=10.1093/comjnl/36.2.117}}</ref>。


== 計算複雑性 ==
この問題は、 [[力まかせ探索|総当たり]]または[[バックトラッキング]]で |''V''|<sup>''m''</sup> の定数倍時間で解くことができる。ここで |''V''| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 ''m'' が定数である場合、多項式時間で解ける問題である。容量 ''m'' が任意の場合、問題は[[NP困難]]である<ref name=arxiv/>。 

== 関連項目 ==

* [[フロベニウスの硬貨交換問題]] 切手の枚数に制限がない場合に相当
* [[ナップサック問題]] 
* [[部分和問題]] 

== 参考文献 ==
{{reflist}}

== 外部リンク ==

*{{cite article| first1=W. F. | last1=Lunnon| title= A postage stamp problem
  |journal = Comput. J. | number=4 | year= 1969| pages=377-380|volume=12|doi=10.1093/comjnl/12.4.377}}
*{{cite journal| first1=R. | last1=Alter | first2=J. A. | last2=Barnett| title=A postage stamp problem
  |journal = Amer. Math. Monthly | year=1980 | volume=87 | pages=206–210 | doi=10.2307/2321610}}
*{{cite journal|first1=R. L. | last1=Graham | first2=N. J. A. | last2=Sloane
  |title=On additive bases and harmonious graphs| journal=SIAM J. Algebr. Discrete Methods
   |year =1980|volume=1 | pages=382–404|doi=10.1137/0601045|citeseerx=10.1.1.70.5521}}
* {{cite arxiv| first1=J. | last1=Kohonen| first2=J. | last2=Corander | eprint=1310.7090
  |title=Addition chains meet postage stamps: reducing the number of multiplications| year=2013}}
*{{cite arxiv|first1=Jukka | last1=Kohonen| title=A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases
   |year=2014 | eprint=1403.5945}}
* {{MathWorld | urlname=PostageStampProblem | title=Postage Stamp Problem}}
* {{OEIS|A001212|''n''種類、2枚の切手での解}}

{{DEFAULTSORT:きつてもんたい}}
[[Category:数学の問題]]
[[Category:応用数学]]
[[Category:数学パズル]]
[[Category:加法的整数論]]
[[Category:数学に関する記事]]