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

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

切手問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/09/10 08:42 UTC 版)

ナビゲーションに移動 検索に移動

切手問題とは、ある枚数の切手で作れない最小の金額(郵便料金)を求める数学の問題である[1]。限られたスペース(封筒の面積)に切手を組み合わせて郵便料金を払う事ができるかを問う。

例えば、封筒は3枚の切手しか貼れず、使用可能な切手の額面が1円、2円、5円、20円の場合、12円までの金額は4 = 2 + 2、8 = 5 + 2 + 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. MR0686707. 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. 

外部リンク




英和和英テキスト翻訳>> 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