القيمة المفقودة الصغرى (رياضيات)

قالب:يتيمة قالب:مقالة غير مراجعة في الرياضيات، المكس او "القيمة المفقودة الصغرى" (في الانكليزية: mex، minimum excluded value) في مجموعة جزئية من مجموعة ترتيبية بشكل جيد هي اصغر قيمة من المجموعة الكبرى و التي ليست ضمن المجموعة الجزئية. بعبارة اخرى، تعبر عن القيمة الصغرى في المجموعة المكملة للمجموعة الجزئية.

بعيدا عن نطاق المجموعات، فان جميع قالب:وإو من الاصناف جيدة الترتيب تمتلك قيمة مفقودة صغرى (مكس). يستخدم مكس الاصناف الجزئية لصنف الاعداد الترتيبية في نظرية اللعبة الاندماجية لاسناد "قيم نيم" قالب:وإو. فحسب نظرية سبراج–جراندي، "قيمة نيم" لوضعية في لعبة هو القيمة المفقودة الصغرى لصنف قيم الوضعيات التي يمكن الوصول اليها ضمن حركة واحدة من الموضع الحالي.

كما يمكن استخدام القيم المفقودة الصغرى في نظرية البيان (بالانكليزية: Graph Theory) في خوارزميات التلوين الجشعة. عادة ما تختار هذه الخوارزميات ترقيما لنقاط البيان و ترقيما للالوان المتاحة للنقاط، ثم تعالج النقاط بالترتيب حيث انها تلون كل نقطة باللون الذي يقابل مكس مجموعة الالوان الموضوعة في النقاط المجاورة.

امثلة

تفترض هذه الامثلة ان المجموعة المعطاة هي مجموعة جزئية من صنف الاعداد الترتيبية فيكون:$$\begin{array}{ccc}\mathrm{mex}(\mathrm{\varnothing })& =& 0\\ \mathrm{mex}(\{1,2,3\})& =& 0\\ \mathrm{mex}(\{0,2,4,6,\dots \})& =& 1\\ \mathrm{mex}(\{0,1,4,7,12\})& =& 2\\ \mathrm{mex}(\{0,1,2,3,\dots \})& =& \omega \\ \mathrm{mex}(\{0,1,2,3,\dots ,\omega \})& =& \omega +1\end{array}$$حيث ان $\begin{array}{c}\omega \end{array}$ هو القيمة الترتيبية من طبيعة نهاية لمجموعة الاعداد الطبيعية.

في نظرية الالعاب

تستخدم القيمة المفقودة الصغرى في نظرية سبراج–جراندي لتحديد "النيمبر" للعبة محايدة تقليدية اللعب. كلا اللاعبين في هذه اللعبة يتمتع بنفس الحركات في كل وضعية من اللعبة و يكون اللاعب الرابح هو اللاعب الذي يقوم بالحركة الاخيرة. "النيمبر" يساوي 0 من اجل اي لعبة يخسرها اللاعب الاول بشكل فوري عند البداية، و يساوي مكس "النيمبرز" لكل الوضعيات الممكنة مستقبلا لاي لعبة اخرى.

على سبيل المثال، في نسخة معدلة على "نيم" (لعبة ازالة العناصر من اكوام مختلفة) تبدأ اللعبة بكومة واحدة من قالب:Mvar من الحجارة و على اللاعب ان يأخذ اي عدد موجب تماما من الحجارة. اذا كان قالب:Mvar يساوي الصفر، "النيمبر" سيكون 0 لان مكس المجموعة الخالية التي تمثل الحركات المسموحة هو "النيمبر" 0. اما اذا كان قالب:Mvar هو حجر واحد، فان اللاعب الذي عليه التحرك لن يترك اي حجارة بالتأكيد، فالحالة الوحيدة الممكنة هي 0 و قالب:تعبير رياضي هو "النيمبر" في هذه الحالة. اما اذا كان قالب:Mvar هو حجران اثنان، فاللاعب الذي عليه التحرك يمكن ان يترك حجرا واحدا 1 او لا يترك شيئا 0، فيكون "النيمبر" 2 هو المكس "للنيمبرز" قالب:تعبير رياضي . عموما، اللاعب الذي عليه التحرك على كومة تحوي قالب:Mvar حجر سيترك اي عدد من الحجار بين 0 و قالب:تعبير رياضي، فسيكون مكس هذه "النيمبرز" قالب:تعبير رياضي} يساوي "النيمبر" قالب:Mvar دوما. اللاعب الأول يفوز فقط عندما يكون عدد الحجارة المبدئي اكبر من الصفر، فتكون الحركة الرابحة هي أخذ جميع الحجارة معا.

اذا عدلنا على قوانين اللعبة حيث ان اللاعب الذي يحين دوره يستطيع اخذ 3 من الحجار على الاكثر، ثم فرضنا ان قالب:تعبير رياضي على سبيل المثال، فان الحالات التالية للحالة الابتدائية تمتلك "النيمبرز" قالب:تعبير رياضي فيكون مكسها يساوي 0. بما ان "النيمبر" لاربعة حجار هو 0، فان اللاعب الاول يخسر دوما امام استراتجية اللاعب الثاني التي تقوم بأخذ جميع الحجارة المتبقية بعد و بغض النظر عن حركة اللاعب الاول. اما في مثال يكون عدد الحجارة فيه قالب:تعبير رياضي ، "النيمبرز" للحالات التالية للحالات 2 و 3 و 4 هي "النيمبرز" 0 و 2 و 3، فيكون المكس لمجموعة "النيمبرز" قالب:تعبير رياضي} هو "النيمبر" 1. فتكون البداية بخمسة حجارة تؤدي للفوز المؤكد للاعب الأول.

راجع مقال "النمبرز" للمزيد من التفاصيل حول مفهوم القيم "النمبرية".