مشكلة طابع البريد

📅 آخر تحديث: ٦ أغسطس ٢٠٢٦
✍️ نُشر في: ٦ أغسطس ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة

مشكلة طابع البريد (وتسمى أيضًا مشكلة عملة فروبينيوس ونظرية تشيكن ماك ناجيت [1] ) هي لغز رياضي يسأل عن أصغر قيمة بريدية لا يمكن وضعها على مظروف، إذا كان الأخير يمكنه حمل عدد محدود فقط من الطوابع، وقد يكون لهذه الطوابع قيم وجهية محددة معينة فقط. [2]

على سبيل المثال، لنفترض أن الظرف لا يتسع إلا لثلاثة طوابع، وأن قيم الطوابع المتاحة هي 1 سنت، و2 سنت، و5 سنتات، و20 سنتًا. عندئذٍ يكون الحل هو 13 سنتًا؛ حيث يمكن الحصول على أي قيمة أصغر بثلاثة طوابع على الأكثر (على سبيل المثال 4 = 2 + 2، و8 = 5 + 2 + 1، وما إلى ذلك)، ولكن للحصول على 13 سنتًا يجب استخدام أربعة طوابع على الأقل.

التعريف الرياضي

رياضيا، يمكن صياغة المشكلة على النحو التالي:

بالنظر إلى عدد صحيح m ومجموعة V من الأعداد الصحيحة الموجبة، أوجد أصغر عدد صحيح z لا يمكن كتابته على هيئة المجموع v 1 + v 2 + ··· + v k لعدد معين k ≤ m من العناصر (غير المميزة بالضرورة) لـ V.

تعقيد

يمكن حل هذه المشكلة باستخدام البحث بالقوة الغاشمة أو التتبع العكسي مع أقصى وقت متناسب مع | V | m ، حيث | V | هو عدد قيم الطابع المميزة المسموح بها. لذلك، إذا كانت سعة المغلف m ثابتة، فهي مشكلة زمنية متعددة الحدود . إذا كانت السعة m عشوائية، فمن المعروف أن المشكلة صعبة NP . [2]

انظر أيضا

مراجع

  1. ^ https://artofproblemsolve.com/wiki/index.php/Chicken_McNugget_Theorem
  2. ^ ab Jeffrey Shallit (2001)، The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (مارس 2002)، 90-94. تم الوصول إليه في 2009-12-30.
  • لونون، دبليو إف (1969). "مشكلة طابع البريد". مجلة الحوسبة 12 (4): 377-380. doi : 10.1093/comjnl/12.4.377 .
  • ألتر، ر.؛ بارنيت، جيه إيه (1980). "مشكلة طابع البريد". مجلة الرياضيات الأمريكية الشهرية . 87 (3): 206-210. doi :10.2307/2321610. JSTOR  2321610.
  • جراهام، آر إل؛ سلون، إن جي إيه (1980). "حول القواعد المضافة والرسوم البيانية المتناغمة". مجلة سيام للجبر. الأساليب المنفصلة . 1 (4): 382-404. CiteSeerX  10.1.1.70.5521 . doi :10.1137/0601045.
  • تشاليس، إم إف (1993). "تقنيتان جديدتان لحساب القواعد h المتطرفة Ak". مجلة الحوسبة 36 ( 2): 117-126. doi : 10.1093/comjnl/36.2.117 .
  • كوهونين، ج.؛ كوراندر، ج. (2013). "سلاسل الجمع تلتقي بطوابع البريد: تقليل عدد الضرب". arXiv : 1310.7090 [math.NT].
  • كوهونين، جوكا (2014). "خوارزمية الالتقاء في المنتصف لإيجاد قاعدتين إضافيتين مقيدتين متطرفتين". arXiv : 1403.5945 [math.NT].
  • وايسستين، إريك دبليو. “مشكلة طابع البريد”. عالم الرياضيات .
  • تسلسل OEIS A001212 (حل مشكلة الطوابع البريدية التي تحتوي على n فئة و2 طابع بريدي)
تم الاسترجاع من "https://en.wikipedia.org/w/index.php?title=مشكلة_الطوابع_البريدية&oldid=1245458692"
Original text
Rate this translation
Your feedback will be used to help improve Google Translate