「切手問題」の版間の差分

'''切手問題'''とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める[[数学]]の問題である<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円、2015円の場合、12円までの金額は3枚までの切手で構成できる（例えば、4 = 2 + 2、8 = 5 + 2 + 1のように切手で構成することができるが、11=5+5+1）。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。