切手問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 切手問題の意味・解説 

切手問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/05/22 21:47 UTC 版)

13は、1、2、5、20の3つの切手しか入らない封筒に収まらない最小の合計です

切手問題とは、ある枚数の切手で作れない最小の金額(郵便料金)を求める数学の問題である[1]。封筒の面積の制約上、貼ることのできる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。

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

数学的な定義

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

整数 m と正の整数の集合 V が与えられたとき、km なる k 個の要素の和 v1 + v2 + ··· + vk で表せない最小の整数 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,... (オンライン整数列大辞典の数列 A001212)

となる。

例えば、順に

となる。

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,... (オンライン整数列大辞典の数列 A014616)

となる。

例えば、順に

となり、一般にの切手を用意することで最大化でき、その解は

と表せる[2]

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,... (オンライン整数列大辞典の数列 A001208)

となる。

n ≥ 20 のとき

とおくと

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

ここで A, B

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


計算複雑性

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

関連項目

参考文献

  1. ^ a b Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.
  2. ^ Stöhr, Alfred (1955年). “Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. I”. J. reine angew Math. 194: pp. 40-65. doi:10.1515/crll.1955.194.40. https://eudml.org/doc/150281 
  3. ^ Mossige, Svein (1981). “Algorithms for Computing the h-Range of the Postage Stamp Problem”. Math. Comp. 36 (154): 575-582. doi:10.1090/S0025-5718-1981-0606515-1. MR0606515. 
  4. ^ Hofmeister, Gerd (1983). “Die dreielementigen Extremalbasen”. J. reine angew Math. 339: 207-214. doi:10.1515/crll.1983.339.207. MR 0686707. https://eudml.org/doc/152515. 
  5. ^ Challis, M. F. (1993). “Two new techniques for computing extremal h-bases Ak”. Comput. J. 36 (2): 117–126. doi:10.1093/comjnl/36.2.117. 

外部リンク

  • Lunnon, W. F. (1969年). “A postage stamp problem”. Comput. J. 12 (4): pp. 377-380. doi:10.1093/comjnl/12.4.377 
  • Alter, R.; Barnett, J. A. (1980). “A postage stamp problem”. Amer. Math. Monthly 87: 206–210. doi:10.2307/2321610. 
  • Graham, R. L.; Sloane, N. J. A. (1980). “On additive bases and harmonious graphs”. SIAM J. Algebr. Discrete Methods 1: 382–404. doi:10.1137/0601045. 
  • Kohonen, J.; Corander, J. (2013). "Addition chains meet postage stamps: reducing the number of multiplications". arXiv:1310.7090
  • Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". arXiv:1403.5945
  • Weisstein, Eric W. "Postage Stamp Problem". mathworld.wolfram.com (英語).
  • オンライン整数列大辞典の数列 A001212



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「切手問題」の関連用語

切手問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



切手問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの切手問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS