مشكلة العملة

لو${\displaystyle n=1}$إذن يجب أن يكون لدينا${\displaystyle a_{1}=1}$بحيث يمكن تكوين جميع الأعداد الطبيعية.

لو${\displaystyle n=2}$يمكن إيجاد عدد فروبينيوس من الصيغة${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$، والذي اكتشفه جيمس جوزيف سيلفستر عام 1882. ^{[ 5 ] [ ملاحظة 1 ]} كما أثبت سيلفستر في هذه الحالة أن هناك ما مجموعه${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$الأعداد الصحيحة غير القابلة للتمثيل (الموجبة).

صيغة أخرى للمعادلة لـ${\displaystyle g(a_{1},a_{2})}$يُقدّمها سكوبين ^{[ 7 ]} في هذه القضية: إذا${\displaystyle a_{1},a_{2}\in \mathbb {N} }$و${\displaystyle \gcd(a_{1},a_{2})=1}$ثم، لكل${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$يوجد زوج واحد فقط من الأعداد الصحيحة غير السالبة${\displaystyle \rho }$و${\displaystyle \sigma }$بحيث${\displaystyle \sigma <a_{1}}$و${\displaystyle n=\rho a_{1}+\sigma a_{2}}$.

تم إثبات الصيغة على النحو التالي. لنفترض أننا نريد بناء العدد${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$. منذ${\displaystyle \gcd(a_{1},a_{2})=1}$جميع الأعداد الصحيحة${\displaystyle n-ja_{2}}$ل${\displaystyle j=0,1,\ldots ,a_{1}-1}$متميزة عن بعضها البعض بتردد${\displaystyle a_{1}}$وبالتالي أي عدد صحيح${\displaystyle m}$يجب أن يكون متطابقًا بتردد${\displaystyle a_{1}}$إلى إحدى هذه البقايا؛ على وجه الخصوص، أخذ${\displaystyle m=a_{1}}$هناك قيمة فريدة لـ${\displaystyle j=\sigma \geq 0}$وعدد صحيح فريد${\displaystyle t}$بحيث${\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}$بإعادة الترتيب، نحصل على عدد صحيح غير سالب${\displaystyle \rho =1-t}$لهذا السبب.${\displaystyle n=\rho a_{1}+\sigma a_{2}}$. بالفعل،${\displaystyle \rho \geq 0}$لأن${\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}$.

لإثبات أن نصف الأعداد الصحيحة بالضبط${\displaystyle 0,1,\ldots ,ab-ab}$إذا كانت قابلة للتمثيل كمجموعات خطية من الأعداد الصحيحة غير السالبة، فيجب أولاً إثبات أنه إذا كان العدد الصحيح${\displaystyle k\in [0,ab-ab]}$إذا كان قابلاً للتمثيل، فعندئذٍ${\displaystyle Nk}$غير قابل للتمثيل، حيث${\displaystyle N=ab-ab}$.

ثم يُبين المرء أن العكس صحيح أيضًا: إذا${\displaystyle k}$إذا لم يكن قابلاً للتمثيل، فعندئذٍ${\displaystyle Nk}$يمكن تمثيلها. ولإثبات ذلك، استخدم حقيقة أن${\displaystyle \gcd(a,b)=1}$مما يسمح لنا بالكتابة${\displaystyle k=xa+yb}$تقليل المعاملات وإعادة ترتيبها عن طريق إضافة مضاعفات${\displaystyle ab}$يمكننا أن نفترض، حسب الضرورة.${\displaystyle 0\leq x<b}$(في الواقع، هذا${\displaystyle x}$هو فريد من نوعه${\displaystyle x}$(تحقيق المعادلة والمتباينات).

وبالمثل نأخذ${\displaystyle u,v}$مُرضٍ${\displaystyle Nk=ua+vb}$ و${\displaystyle 0\leq u<b}$الآن يمكننا جمع هذه المعادلات لكتابة${\displaystyle N=(u+x)a+(y+v)b}$والتي، باستخدام${\displaystyle N=ab-ab}$العائد${\displaystyle ab-b(1+y+v)=a(x+u+1)}$العدد الصحيح${\displaystyle x+u+1}$إيجابي، لأن${\displaystyle x,u\geq 0}$في الواقع، منذ الجانب الأيسر من${\displaystyle ab-b(1+y+v)=a(x+u+1)}$يقبل القسمة على${\displaystyle b}$، و${\displaystyle (a,b)=1}$يجب أن يكون لدينا ذلك${\displaystyle x+u+1}$يقبل القسمة على${\displaystyle b}$. حتى الآن${\displaystyle x,u\leq b-1}$، لذا${\displaystyle x+u+1\leq 2b-1}$، لهذا السبب${\displaystyle x+u+1=b}$. استبدال هذا في${\displaystyle ab-b(1+y+v)=a(x+u+1)}$وطرح${\displaystyle ab}$ينتج عن كلا الجانبين${\displaystyle b(1+y+v)=0}$. لذا${\displaystyle 1+y+v=0}$وهذا يعني أن${\displaystyle y+v=-1}$وهذا يعني أن واحداً فقط من${\displaystyle y}$أو${\displaystyle v}$سالب. إذا${\displaystyle y}$إذا كانت القيمة سالبة، فـ${\displaystyle v\geq 0}$وهذا يعني أن${\displaystyle Nk=ua+vb}$قابل للتمثيل؛ الحالة عندما${\displaystyle v}$إن كون الشيء سلبياً يستلزم ذلك${\displaystyle k}$يمكن تمثيله.

وبالتالي لأي عدد صحيح غير سالب${\displaystyle k\in [0,ab-ab]}$نعلم أن واحداً فقط من${\displaystyle k}$أو${\displaystyle (ab-ab)-k}$يمكن تمثيلها (وهذه متميزة، لأن${\displaystyle ab-ab}$يجب أن يكون فرديًا مثل الأعداد الصحيحة${\displaystyle a,b}$(أولية فيما بينها). هذا يدل على أن نصف الأعداد الصحيحة في النطاق المعطى قابلة للتمثيل؛ نظرًا لوجود${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$الأعداد الصحيحة في النطاق${\displaystyle [0,ab-ab]}$وهذا يعطي النتيجة المرجوة.

تُعرف الصيغ ^{[ 8 ]} والخوارزميات السريعة ^{[ 9 ] لثلاثة أرقام على الرغم من أن الحسابات يمكن أن تكون شاقة للغاية إذا تم إجراؤها يدويًا.}

تم أيضاً تحديد حدود دنيا وعليا أبسط لأعداد فروبينيوس عندما n = 3. الحد الأدنى التقاربي الذي وضعه دافيسون

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}$

حاد نسبيًا. ^{[ 10 ]} (${\displaystyle f}$هذا هو عدد فروبينيوس المعدل، وهو أكبر عدد صحيح لا يمكن تمثيله بمجموعات خطية من الأعداد الصحيحة الموجبة.${\displaystyle a_{1},a_{2},a_{3}}$.)

السلوك المتوسط ​​التقاربي لـ${\displaystyle f}$^{يُعرف أيضًا باسم: [ 11 ]} لثلاثة متغيرات

${\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}$

توجد صيغة بسيطة لحساب عدد فروبينيوس لمجموعة من الأعداد الصحيحة في متتالية حسابية . ^{[ 1 ] : 59-60} بفرض وجود الأعداد الصحيحة a و d و w حيث القاسم المشترك الأكبر ( a , d ) = 1:   

${\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}$

ال${\displaystyle n=2}$يمكن التعبير عن الحالة المذكورة أعلاه كحالة خاصة من هذه الصيغة.

في حالة أن${\displaystyle a>w^{2}-3w+1}$يمكننا حذف أي مجموعة فرعية من العناصر${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$من متتاليتنا الحسابية، وتبقى صيغة عدد فروبينيوس كما هي. ^{[ 14 ]}

يوجد أيضًا حل مغلق لعدد فروبينيوس لمجموعة في متتالية هندسية . ^{[ 15 ]} بالنظر إلى الأعداد الصحيحة m و n و k حيث القاسم المشترك الأكبر ( m و n ) = 1:   

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$

الصيغة الأبسط التي تُظهر أيضًا التناظر بين المتغيرات هي كما يلي. بمعلومية الأعداد الصحيحة الموجبة${\displaystyle a,b,k}$، مع${\displaystyle \gcd(a,b)=1,}$يترك${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$ثم ^{[ 16 ]}

${\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$

أين${\displaystyle {\sigma }_{k}(a,b)}$يرمز إلى مجموع جميع الأعداد الصحيحة في${\displaystyle A_{k}(a,b).}$

يُشار أحيانًا إلى حالة خاصة من مسألة العملة باسم " أعداد ماك ناجتس ". وقد طرح هنري بيتشيوتو نسخة ماك ناجتس من مسألة العملة، حيث نشرها كلغز في مجلة "جيمز" عام 1987، ^{[ 17 ]} وأدرجها في كتابه المدرسي في الجبر الذي شارك في تأليفه مع أنيتا واه. ^{[ 18 ]} خطرت فكرة التطبيق لبيتشيوتو في ثمانينيات القرن الماضي أثناء تناوله العشاء مع ابنه في ماكدونالدز، حيث كان يحل المسألة على منديل. يُمثل عدد ماك ناجتس العدد الإجمالي لقطع دجاج ماك ناجتس من ماكدونالدز في أي عدد من العلب. في المملكة المتحدة ، كانت العلب الأصلية (قبل طرح علب ناجتس بحجم وجبة هابي ميل ) تحتوي على 6 أو 9 أو 20 قطعة ناجتس.

بحسب نظرية شور ، بما أن الأعداد 6 و9 و20 أولية فيما بينها (مجموعات) ، فإن أي عدد صحيح كبير بما فيه الكفاية يمكن التعبير عنه كتركيبة خطية (غير سالبة وصحيحة) لهذه الأعداد الثلاثة. لذلك، يوجد أكبر عدد غير ماكنوجت، وجميع الأعداد الصحيحة الأكبر منه هي أعداد ماكنوجت. أي أن كل عدد صحيح موجب هو عدد ماكنوجت، باستثناء عدد محدود من الحالات.

1، 2، 3، 4، 5، 7، 8، 10، 11، 13، 14، 16، 17، 19، 22، 23، 25، 28، 31، 34، 37، و43 (التسلسل A065003 في OEIS ) .

وبالتالي، فإن أكبر عدد غير ماكناغِت هو 43. ^{[ 19 ]} ويمكن ملاحظة أن أي عدد صحيح أكبر من 43 هو عدد ماكناغِت من خلال النظر في تقسيمات الأعداد الصحيحة التالية

${\displaystyle 44=6+6+6+6+20}$

${\displaystyle 45=9+9+9+9+9}$

${\displaystyle 46=6+20+20}$

${\displaystyle 47=9+9+9+20}$

${\displaystyle 48=6+6+9+9+9+9}$

${\displaystyle 49=9+20+20}$

يمكن الحصول على أي عدد صحيح أكبر بإضافة عدد من الرقم 6 إلى القسم المناسب أعلاه. ويُظهر فحص بسيط أنه لا يمكن شراء 43 قطعة ماك ناجتس، وذلك للأسباب التالية:

1. لا يمكن أن تشكل المربعات المكونة من 6 و 9 وحدها العدد 43 لأن هذه المربعات لا يمكنها إلا أن تُنتج مضاعفات العدد 3 (باستثناء العدد 3 نفسه)؛
2. إن تضمين خانة واحدة تحتوي على 20 لا يفيد، لأن الباقي المطلوب (23) ليس من مضاعفات العدد 3 أيضاً؛
3. من الواضح أن أكثر من علبة واحدة تحتوي على 20 قطعة، بالإضافة إلى علب بحجم 6 أو أكبر، لا يمكن أن تؤدي إلى إجمالي 43 قطعة ماك ناجتس.

منذ طرح علب قطع الدجاج بحجم وجبة هابي ميل المكونة من 4 قطع، أصبح أكبر عدد من القطع غير ماك ناجتس هو 11. في البلدان التي تم فيها استبدال حجم 9 قطع بحجم 10 قطع، لا يوجد أكبر عدد من القطع غير ماك ناجتس، حيث لا يمكن صنع أي عدد فردي.

في رياضة الرجبي ، توجد أربعة أنواع من النقاط: ركلة الجزاء (3 نقاط)، والركلة الساقطة (3 نقاط)، والمحاولة (5 نقاط)، والمحاولة المُحولة (7 نقاط). وبدمج هذه النقاط، يُمكن الحصول على أي مجموع نقاط باستثناء 1 أو 2 أو 4. أما في رياضة الرجبي السباعي ، فرغم السماح بجميع أنواع النقاط الأربعة، إلا أن محاولات ركلات الجزاء نادرة، والركلات الساقطة شبه معدومة. وهذا يعني أن نقاط الفريق تتكون في الغالب من مضاعفات المحاولات (5 نقاط) والمحاولات المُحولة (7 نقاط). أما النقاط التالية (بالإضافة إلى 1 و2 و4) فلا يُمكن الحصول عليها من مضاعفات 5 و7، ولذلك فهي نادرة الظهور في الرجبي السباعي: 3، 6، 8، 9، 11، 13، 16، 18، و23. على سبيل المثال، لم تُسجل أي من هذه النقاط في أي مباراة من سلسلة الرجبي السباعي العالمية 2014-2015 .

وبالمثل، في كرة القدم الأمريكية ، الطريقة الوحيدة لتسجيل فريق نقطة واحدة بالضبط هي احتساب نقطة أمان ضد الفريق المنافس عند محاولته التسجيل بعد تسجيل هدف (والذي تبلغ قيمته في هذه الحالة 6 نقاط). وبما أنه يتم احتساب نقطتين لنقاط الأمان من اللعب العادي، و3 نقاط لأهداف الجزاء ، فإن جميع النتائج الأخرى غير 1-0، 1-1، 2-1، 3-1، 4-1، 5-1، و7-1 ممكنة. ويرتبط هذا ارتباطًا مباشرًا بمفهوم " سكوريغامي" .

خوارزمية شيلسورت هي خوارزمية فرز، ولا يزال تعقيدها الزمني يمثل مشكلة مفتوحة . يوجد حد أعلى لتعقيدها في أسوأ الحالات، ويمكن تحديده بدلالة عدد فروبينيوس لتسلسل معين من الأعداد الصحيحة الموجبة.

تُعدّ شبكات بتري مفيدةً لنمذجة المشكلات في الحوسبة الموزعة . بالنسبة لأنواع محددة من شبكات بتري، وتحديدًا الدوائر الموزونة المحافظة، يُراد معرفة "الحالات" أو "العلامات" الممكنة ذات الوزن المُحدد التي تُعتبر "فعّالة". تُعادل مشكلة تحديد أقل وزن فعّال مشكلة فروبينيوس.

عند رفع متعددة حدود أحادية المتغير إلى قوة معينة، يمكن التعامل مع أسس متعددة الحدود كمجموعة من الأعداد الصحيحة. وستحتوي متعددة الحدود الموسعة على قوى من${\displaystyle x}$أكبر من عدد فروبينيوس لبعض الأسس (عندما يكون القاسم المشترك الأكبر = 1)، على سبيل المثال، لـ${\displaystyle (1+x^{6}+x^{7})^{n}}$المجموعة هي {6، 7} والتي لها عدد فروبينيوس يساوي 29، لذا فإن الحد الذي${\displaystyle x^{29}}$لن يظهر أبداً مهما كانت قيمته${\displaystyle n}$لكن بعض قيمة${\displaystyle n}$سيمنح شروطًا لها أي سلطة على${\displaystyle x}$أكبر من 29. عندما لا يكون القاسم المشترك الأكبر للأسس 1، فإن القوى الأكبر من قيمة معينة لن تظهر إلا إذا كانت من مضاعفات القاسم المشترك الأكبر، على سبيل المثال لـ${\displaystyle (1+x^{9}+x^{15})^{n}}$ستظهر قوى العدد 24، 27، ... لبعض قيم العدد 24، 27، ...${\displaystyle n}$لكن لا توجد قيم أكبر من 24 ليست من مضاعفات 3 (ولا القيم الأصغر، 1-8، 10-14، 16، 17، 19-23).