مهمة 165 عامًا مضت تطارد علماء الرياضيات

في عام 1850 ، صاغ القس توماس كيركمان ، عالم الرياضيات البريطاني وعميد الرعية في لانكشاير ، لغزًا بريئًا في مجلة ترفيهية لعشاق الرياضيات "مفكرة للسيدات والسادة":

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

تبدو المهمة بسيطة ، ولكن إذا حاولت حلها ، فستدرك على الفور أن الأمر ليس كذلك. يمكنك محاولة حلها بقلم رصاص وورقة أو اللعب في إصدار HTML .

بسبب بساطتها الزائفة ، سرعان ما أصبحت المهمة مشهورة. أرسل عشاق الرياضيات قراراتهم ، ونشر العلماء مقالات علمية في محاولة لصياغة حل عام للمشكلة.

ونتيجة لذلك ، ساعد هذا اللغز في تشكيل مجال جديد من الرياضيات: المخططات التوافقية ، والتي يتم تخصيص الكتب الدراسية السميكة لها الآن.. ما بدأ كمهمة بسيطة لتوزيع الأشخاص في مجموعات (أو مخططات ، كما تم تسميتهم في نهاية المطاف) أصبح الآن طريقة يتم استخدامها في التصميم التجريبي ورموز تصحيح الأخطاء في علوم الكمبيوتر والتشفير والزراعة والرياضة وحتى في عمليات الاحتيال المتعلقة بالمقامرة (كانت هناك قصة عندما كسب كارتل إجرامي ملايين الدولارات في سبع سنوات عن طريق شراء تذاكر مع جميع المجموعات الممكنة من 5 من أصل 46 في 6 من 46 من اليانصيب إذا كانت تكلفة التذاكر أقل من المكافآت الإضافية للفوز بـ 5 من 46 بالإضافة إلى احتمال الفوز بالجائزة الكبرى).

على سبيل المثال ، يستخدم رمز Hamming الكلاسيكي لحل الأخطاء حل المشكلة حول تلميذات المدارس (إنشاء مجموعات من ثلاث فتيات ، حيث لا يتكرر الزوج) ، ولكن فقط لمخطط سبع فتيات (بت).


طائرة فانو لـ (7 ، 3 ، 2)

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

على سبيل المثال ، بالنسبة لمجموعة من 19 فتاة ، هناك أكثر من 11 مليار ثلاثة توائم محتملين يلتقي فيها كل زوج مرة واحدة فقط. هذا الرقم هو الجواب. لكن عدد الخيارات يتزايد باطراد مع زيادة عدد طالبات المدارس.

من الواضح أن المشكلة تحل في ظل ظروف معينة ولا تحل في ظل ظروف أخرى. على سبيل المثال ، إذا كانت ثلاثة أزواج من ثلاثة أزواج محتملة تتكون من ست تلميذات ، فمن الواضح أنه لم يتم حل المشكلة (هناك خمسة أزواج محتملة مع تلميذة أنيا ، في نفس الوقت ، كل ثلاثة أزواج مع أنيا ، وخمسة لا تنقسم إلى قسمين). أي ، وفقًا لمبدأ القسمة ، يتم إلغاء العديد من الخيارات (n ، k ، t) على الفور .

في نفس الوقت ، هناك (ن ، ك ، ر) تمتثل تمامًا لمبدأ القسمة ، ولكن لا يوجد حتى الآن حل: على سبيل المثال ، (47 ، 3 ، 2) .

على مدى السنوات الماضية ، أصبح الحل معروفًا للعديد من التركيبات (n ، k ، t)تم فحصها جبريًا أو باستخدام القوة الوحشية على أجهزة الكمبيوتر. ولكن كيف يمكن حل هذا بطريقة عامة ، وماذا تفعل مع استثناءات مثل (47 ، 3 ، 2) ؟ كيف نفهم ما إذا كان للمشكلة حل أم لا؟ يقول عالم الرياضيات جيل كالاي من الجامعة العبرية في القدس في مقابلة مع وايرد إن

هذه المهمة تعتبر منذ فترة طويلة واحدة من أشهر المشكلات في التوافقية . يتذكر أنه جادل مع الزملاء حول هذا قبل عام ونصف ، وتوصلوا إلى استنتاج مفاده أن "لن نعرف الإجابة أبدًا ، لأن المهمة معقدة للغاية". ومع ذلك ، بعد أسبوعين فقط ، أثبت أستاذ الرياضيات الشاب بيتر كيفاش من أكسفورد أن كالاي كان مخطئًا. في مقال علمي

من يناير 2014 ، يجادل بأن حل المشكلة موجود دائمًا تقريبًا إذا تم استيفاء شرط الانقسام. في ورقة جديدة مؤرخة أبريل 2015 ، أظهر كيفية حساب العدد التقريبي للحلول لمعلمات معينة.

لم يتوقع أحد تطبيق نظرية الاحتمالات على حل المشكلة ، لكن الطريقة عملت بشكل مثالي.

بالعودة إلى اليانصيب ، أدرك المحتالون أنه من الممكن تقليل عدد التذاكر التي تم شراؤها عن طريق شراء جميع مجموعات 5 من أصل 46 (عند تحديد 6 من أصل 46 رقمًا) ، ثم سيحصلون على جميع الجوائز الإضافية على الإطلاق ، وقد يحصلون أيضًا على الجائزة الكبرى. على الرغم من أن المخطط (46 ، 6 ، 5) لم يتم حسابه بعد ، إلا أن هناك مخططات قريبة بما يكفي للتطبيق العملي. ربما تم استخدام واحد منهم من قبل كارتل إجرامي.

يتزايد عدد الدوائر المحسوبة الجديدة باستمرار. يجد الكثير منهم تطبيقًا عمليًا ، مثل (15 ، 3 ، 2) من المشكلة الكلاسيكية ، و (46 ، 6 ، 5) . أدلة من 1000 صفحة تحتوي على رسوم بيانية. ومع ذلك ، لا يزال علماء الرياضيات في حيرة حول كيفية تحديد ما إذا كان الحل موجودًا لظروف معينة معينة. بفضل Kivash ، علمنا أن احتمال حدوث ذلك مرتفع جدًا. لذا على الأقل أصبح من الواضح الآن أنه مع كل المجهول ، من الأفضل البحث عن حل بدلاً من التخلي عنه. علاوة على ذلك ، هناك أدوات لتوليد دوائر العينة لأي معلمات.

ولكن بفضل عمل Kivash ، كان من المأمول أن يتم تطوير طريقة لخلق دقيقةمخططات لأية معلمات. إذا حدث ذلك ، فسيكون هذا تقدمًا غير عادي في الرياضيات.

ومع ذلك ، فإن عمل كيفاش نظري بحت. يقول الخبراء أن إنشاء خوارزميات عملية بناءً على أسلوبه يتطلب العمل الشاق لعدة أجيال أخرى من علماء الرياضيات.

Source: https://habr.com/ru/post/ar380785/