أكبر مبلغ يستحيل دفعه بات محصورًا بحدّ دقيق

تخيّل صندوق دفع لا يقبل إلا أنواعًا قليلة من العملات، متوفرة بلا حدود، ولا يردّ الباقي أبدًا. بعض المبالغ يمكن دفعها بالضبط، وبعضها لا يمكن أبدًا. يسمّي الرياضيون قيم العملات مولِّدات (generators)، ويطرحون سؤالًا يبدو بسيطًا على نحو خادع: ما أكبر مبلغ لا يمكن دفعه؟

مبالغ لا يمكن دفعها أبدًا

لنأخذ أعدادًا صحيحة a₁ < a₂ < … < aₙ لا يجمعها عامل مشترك بينها جميعًا. أي مجموع نحصل عليه بجمع هذه الأعداد، كلٌّ منها بالعدد الذي نشاء من المرات، يسمى «قابلًا للتمثيل». وعدد الأعداد الصحيحة غير القابلة للتمثيل محدود، وأكبرها هو عدد فروبينيوس، F. (إذا كانت إحدى القيم تساوي 1، أمكن دفع كل شيء ويُعرَّف F بأنه −1.)

مثال صغير: بعملات 3 و4 و6، يمكنك دفع 3 و4 و6 و7 و8 وكل مبلغ بعد ذلك، لكن لا يمكنك أبدًا دفع 1 أو 2 أو 5. إذن F = 5. لاحظ أن 3 و6 يشتركان في عامل؛ المهم ألا يكون هناك عامل مشترك بين الثلاثة جميعًا.

لعملتين توجد إجابة دقيقة، هي صيغة سيلفستر: F(a₁, a₂) = a₁a₂ − a₁ − a₂. ولثلاث عملات أو أكثر، يتمثل العمل في حصر F: أي إثبات أنه لا يمكن أن يتجاوز قيمة ما تُحسب من العملات.

عامل 2 عنيد

أثبت بول إردوش (Paul Erdős) ورونالد غراهام (Ronald Graham)، لثلاثة مولِّدات أو أكثر:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

هنا aₙ هي أكبر قيمة، وaₙ₋₁ ثاني أكبر قيمة، وn عدد القيم، و⌊ ⌋ تعني التقريب إلى الأسفل. ومثل صيغة سيلفستر، يتضمن هذا الحد أكبر عملتين.

وقدّرا أيضًا أسوأ الحالات، أي أكبر قيمة ممكنة لـF حين لا تتجاوز القيم الـn كلها t. وأدت الفجوة بين تقديراتهما، وهي عامل 2 تقريبًا، إلى حدسية مسجلة باسم مسألة إردوش رقم 433 (Erdős Problem #433). وقد حلّها جاك ديكسمييه (Jacques Dixmier)، وأثبت أيضًا حدًا أبسط صالحًا لكل مجموعة: F ≤ aₙ²/(n − 1). اختفى العامل 2، لكن اختفت معه ثاني أكبر عملة.

الإبقاء على أكبر عملتين معًا

أراد لين تشن (Lin Chen) وتينغوي هو (Tingwei Hu) ويوتشن ماو (Yuchen Mao) وغوتشوان تشانغ (Guochuan Zhang)، من كلية علوم وتقنية الحاسوب في جامعة تشجيانغ، الأمرين معًا: لا عامل 2، مع الإبقاء على ثاني أكبر عملة. وجوابهم، الصالح لأي مجموعة من قيمتين أو أكثر، هو:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

هنا ⌈ ⌉ تعني التقريب إلى الأعلى. ومقارنةً بحد إردوش وغراهام، اختفى العامل 2، مقابل القسمة على n − 1 بدل n والتقريب إلى الأعلى. ومقارنةً بحد ديكسمييه، يمكن أن يكون الحد الجديد أصغر بكثير حين تكون ثاني أكبر عملة صغيرة قياسًا إلى أكبرها.

في مثال 3 و4 و6، يعطي حد إردوش وغراهام 10، وحد ديكسمييه 18، والحد الجديد 4 × 3 − 6 − 1 = 5، أي القيمة الحقيقية بالضبط. ولا مفاجأة في ذلك: فهذه المجموعة تنتمي إلى عائلة الحالات القصوى الموصوفة أدناه، والمبنية لتبلغ الحد بالضبط؛ ولا تقدم الورقة أي مقارنة على مجموعات نموذجية.

فرز المبالغ بحسب الباقي

يسلك البرهان طريق إردوش وغراهام. يُفرز كل مبلغ بحسب باقي قسمته على أكبر عملة، aₙ. وما إن يبلغ مجموعٌ من العملات الأصغر باقيًا معيّنًا، حتى تتيح إضافة نسخ من aₙ بلوغ كل مبلغ أكبر له الباقي نفسه. والمهمة هي إثبات أن كل باقٍ يمكن بلوغه بكلفة زهيدة.

الأداة الأساسية هي مبرهنة كنيزر (Kneser’s theorem)، التي تحدد مدى الكبر الذي يجب أن تبلغه مجموعة من المجاميع. استخدمها إردوش وغراهام لإثبات أن مجاميع نحو aₙ/n عملة تغطي أكثر من نصف البواقي، ثم ضاعفا العدد لتغطيتها كلها. وكل عملة في هذه المجاميع لا تتجاوز قيمتها aₙ₋₁، لذا فمضاعفة عدد العملات تضاعف الكلفة: ومن هنا جاء العامل 2.

يستخدم البرهان الجديد مجاميع من ⌈aₙ/(n − 1)⌉ عملة. وحين تفوت هذه المجاميع بعض البواقي، تقول مبرهنة كنيزر إن البواقي المفقودة ليست مبعثرة عشوائيًا: بل تشكّل عائلات كاملة من البواقي المتباعدة على فترات منتظمة. وكلما زادت العائلات المفقودة، اضطرت العملات الأصغر إلى التزاحم أكثر في كل عائلة جرى بلوغها، فتحتوي كل واحدة من تلك العائلات على بعض العملات الصغيرة، وتكون العملات الإضافية القليلة اللازمة لبلوغ العائلات المفقودة رخيصة. ولا يتجاوز المجموع أبدًا ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

تعطي هذه الخطوة الأولى الحد من دون «− 1» الأخير. أما الوحدة الأخيرة فتأتي من حجة مستقلة، تستند إلى مبرهنة لشيرك (Scherk) وكمبرمان (Kemperman) حول المجاميع التي لا يمكن تكوينها إلا بطريقة واحدة: فهي تُظهر أن المبلغ الحدّي aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ يمكن دائمًا دفعه هو نفسه. ووفقًا لقسم الشكر، أثبت المؤلفون أولًا الحد الأضعف؛ ثم ساعد GPT-6 في إيجاد الحجة التي تخفضه بواحد، وأسهم أيضًا في إثبات أن الحد لا يمكن خفضه وفي تحرير النص الإنجليزي. ويصرّح المؤلفون بأنهم يتحملون مسؤولية المخطوطة النهائية.

حالات تبلغ الحد بالضبط

لا يمكن خفض هذا الحد: فلكل n ≥ 3، يبني المؤلفون عددًا لا نهائيًا من المجموعات التي يساويه فيها F بالضبط. خذ أي q ≥ 2 والقيم q و2q و… و(n − 1)q، ومعها (n − 2)q + 1. كلها ما عدا واحدة مضاعفات لـq، فلا تدفع شيئًا لا تستطيع q وحدها دفعه. تتصرف المجموعة كعملتين، q و(n − 2)q + 1، وتعطي صيغة سيلفستر قيمة لـF تطابق الحد الجديد بالضبط. ومع n = 3 وq = 3، تنتج هذه الوصفة تمامًا مثال 3 و4 و6 السابق.

عملات أقل، سقف أدنى

يمكن أيضًا قراءة الحد من زاوية الكثافة. فهو ينطبق على أي مجموعة مختزلة مكوّنة من أصغر i قيمة إضافةً إلى أكبرها، ما دامت هذه القيم لا تزال بلا عامل مشترك. وإزالة العملات لا يمكن إلا أن تجعل الدفع أصعب، لذا فإن السقف المُثبت للمجموعة المختزلة يصح أيضًا للمجموعة الكاملة. وما يتحكم في النتيجة هو تقريبًا aᵢ/i، أي مقلوب الكثافة التي تملأ بها القيم الـi الأولى الأعداد من 1 إلى aᵢ: والمجموعة الأكثف هي التي تفوز. ويلاحظ المؤلفون على وجه الخصوص أن ثاني أكبر عملة يمكن ببساطة تنحيتها جانبًا كلما ظلت العملات المتبقية بلا عامل مشترك بينها جميعًا.

تبقى الورقة نظرية بحتة: فهي لا تقدم أي رقم عن مقدار صغر الحد الجديد على مجموعات العملات النموذجية، ولم تُثبت دقته المثلى (sharpness) إلا لثلاث قيم للعملات أو أكثر.