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

مسألة كيركمان للتلميذة هي مسألة في علم التوافيق اقترحها توماس بينينغتون كيركمان عام 1850 تحت عنوان "السؤال السادس" في "مذكرات السيدة والسيد" (صفحة 48). وتنص المسألة على ما يلي:

خمس عشرة فتاة في مدرسة يمشين ثلاثاً جنباً إلى جنب لمدة سبعة أيام متتالية: المطلوب ترتيبهن يومياً بحيث لا تمشي اثنتان جنباً إلى جنب مرتين. ^{[ 2 ]}

يُعدّ نظام كيركمان الثلاثي مثالاً على حل هذه المشكلة ، ^{[ 3 ]} وهو نظام شتاينر ثلاثي يتميز بالتوازي ، أي تقسيم كتل النظام الثلاثي إلى فئات متوازية، وهذه الفئات بدورها تقسيمات للنقاط إلى كتل منفصلة. تُسمى أنظمة شتاينر التي تتميز بالتوازي أيضاً بالأنظمة القابلة للحل .

يوجد سبعة حلول غير متماثلة بالضبط لمسألة تلميذة المدرسة، كما وردت في الأصل من قبل فرانك نيلسون كول في كتاب كيركمان باريدز عام 1922. ^{[ 4 ]} تم تلخيص الحلول السبعة في الجدول أدناه، حيث تشير الأحرف من A إلى O إلى الفتيات الـ 15.

بناءً على عدد التشاكلات الذاتية لكل حل وتعريف مجموعة التشاكلات الذاتية، فإن العدد الإجمالي للحلول بما في ذلك الحلول المتماثلة هو بالتالي:

${\displaystyle 15!\times \left({\frac {1}{168}}+{\frac {1}{168}}+{\frac {1}{24}}+{\frac {1}{24}}+{\frac {1}{12}}+{\frac {1}{12}}+{\frac {1}{21}}\right)}$

${\displaystyle =15!\times {\frac {13}{42}}}$

${\displaystyle =404,756,352,000}$

${\displaystyle =2^{10}\times 3^{5}\times 5^{3}\times 7\times 11\times 13^{2}}$.

لهذه المشكلة تاريخ طويل وحافل. يستند هذا القسم إلى أعمال تاريخية أنجزها روبن ويلسون ^{[ 5 ]} ولويز دوفيلد كامينغز ^{[ 6 ]} في أوقات مختلفة . وفيما يلي سرد ​​تاريخها:

• في عام 1844، طرح ويسلي وولهاوس ، محرر مجلة "يوميات السيدات والسادة" آنذاك، السؤال التالي: "حدد عدد التوليفات الممكنة من n رمزًا، بواقع p رمزًا في كل توليفة؛ مع مراعاة عدم تكرار أي توليفة من q رمزًا، قد تظهر في أي توليفة منها، في أي توليفة أخرى." لم يُتلقَّ سوى إجابتين، إحداهما خاطئة والأخرى صحيحة.${\textstyle {\frac {n!}{q!(nq)!}}\div {\frac {p!}{q!(pq)!}}}$وبما أن السؤال لم يطلب أكثر من عدد التوليفات، فلم يتم الحصول على أي معلومات حول الشروط المتعلقة بـ n أو p أو q التي يمكن عندها تحقيق مثل هذا الحل.
• في عام 1846، تساءل وولهاوس: "كم عدد الثلاثيات التي يمكن تكوينها من n رمزًا، بحيث لا يتكرر أي زوج من الرموز أكثر من مرة؟". وهذا يعادل تكرار سؤاله الذي طرحه عام 1844 مع القيمتين p = 3 و q = 2. ^{[ 5 ]}
• في عام ١٨٤٧، نشر توماس كيركمان، البالغ من العمر ٤١ عامًا، بحثه بعنوان " حول مسألة في التوافيق " ( كيركمان ١٨٤٧ ) ، والذي وصف فيه بشكل شامل وحلّ مسألة بناء أنظمة ثلاثية من الرتبة n، حيث n = ١ أو ٣ ( mod ٦). كما درس قيمًا أخرى لـ n، على الرغم من استحالة تحقيق التوازن التام. وقدّم سلسلتين مختلفتين من الأنظمة الثلاثية، إحداهما لـ n = ٧، ١٥، ١٩، ٢٧، إلخ، والأخرى لـ n = ٩، ١٣، ٢٥، إلخ. وباستخدام هذه الافتراضات، أثبت وجود أنظمة ثلاثية لجميع قيم n = ١ أو ٣ (mod ٦) ^{[ ٦ ]} (ليس بالضرورة أنظمة قابلة للحل، ولكن أنظمة ثلاثية بشكل عام). كما وصف بالتفصيل في ذلك البحث الأنظمة الثلاثية القابلة للحل، وخاصةً لـ n = ٩ و١٥؛ وتُعرف هذه الأنظمة الثلاثية الآن باسم أنظمة كيركمان الثلاثية. لم يستطع أن يقول بشكل قاطع ما هي القيم الأخرى لـ n التي يمكن أن توجد من أجلها أنظمة ثلاثية قابلة للحل ؛ لم يتم حل هذه المشكلة حتى الستينيات (انظر أدناه).
• في عام ١٨٥٠، طرح كيركمان مسألة التلميذات الخمس عشرة، التي ستُصبح أكثر شهرةً بكثير من بحثه الذي نُشر عام ١٨٤٧. وقد قُدّمت عدة حلول. قدّم كيركمان نفسه حلاً ^{[ ٧ ]} تبيّن لاحقًا أنه مُتماثل مع الحل الأول المذكور أعلاه. ادّعى كيركمان أنه الحل الوحيد الممكن، لكن هذا كان غير صحيح. كما تبيّن لاحقًا أن حل آرثر كايلي ^{[ ٨ ]} مُتماثل مع الحل الثاني. يُمكن تضمين كلا الحلين في PG(3,2)، على الرغم من أن هذه الهندسة لم تكن معروفة في ذلك الوقت. مع ذلك، عند نشر حلوله لمسألة التلميذات، أغفل كيركمان إحالة القراء إلى بحثه المنشور عام ١٨٤٧، وكان لهذا الإغفال عواقب وخيمة على الاختراع والأسبقية، كما سيتبين لاحقًا.
• وفي عام 1850 أيضاً، تساءل جيمس جوزيف سيلفستر عما إذا كان من الممكن إيجاد 13 حلاً مختلفاً لمسألة التلميذات الخمس عشرة التي تستخدم جميع${\textstyle {15 \choose 3}=455}$يتضاعف ثلاث مرات بالضبط مرة واحدة إجمالاً، مع ملاحظة أن${\displaystyle 455=13\times 35}$. In words, is it possible for the girls to march every day for 13 weeks, such that every two girls march together exactly once each week and every three girls march together exactly once in the term of 13 weeks? This problem was much harder, and a computational solution would finally be provided in 1974 by RHF Denniston (see below).
• In 1852, Robert Richard Anstice provided a cyclic solution, made by constructing the first day's five triples to be 0Gg, AbC, aDE, cef, BdF on the 15 symbols 0ABCDEFGabcdefg and then cyclically shifting each subsequent day by one letter while leaving 0 unchanged (uppercase staying uppercase and lowercase staying lowercase).^[5] If the four triples without the 0 element (AbC, aDE, cef, BdF) are taken and uppercase converted to lowercase (abc, ade, cef, bdf) they form what would later be called the Pasch configuration.^[9] The Pasch configuration would become important in isomorph rejection techniques in the 20th century.
• In 1853, Jakob Steiner, completely unaware of Kirkman's 1847 paper, published his paper titled Combinatorische Aufgabe which reintroduced the concept of triple systems but did not mention resolvability into separate parallel classes. Steiner noted that it is necessary for n to be 1 or 3 (mod 6) but left an open question as to when this would be realized, unaware that Kirkman had already settled that question in 1847. As this paper was more widely read by the European mathematical establishment, triple systems later became known as Steiner triple systems.^[5]
• In 1859, Michel Reiss answered the questions raised by Steiner, using both methodology and notation so similar to Kirkman's 1847 work (without acknowledging Kirkman), that subsequent authors such as Louise Cummings have called him out for plagiarism.^[6] Kirkman himself expressed his bitterness.
• In 1860, Benjamin Peirce unified several disparate solutions presented thus far, and showed that there were three possible cyclic solution structures, one corresponding to Anstice's work, one based on Kirkman's solution, and one on Cayley's.^[5]
• في عام ١٨٦١، عاد جيمس جوزيف سيلفستر إلى المشكلة وحاول الادعاء بأنه هو من ابتكرها، وأن محاضراته في كامبريدج كانت مصدر عمل كيركمان. سرعان ما رفض كيركمان ادعاءاته، مصرحًا بأنه عندما كتب أوراقه لم يكن قد زار كامبريدج قط ولم يسمع بعمل سيلفستر. ^{[ ٥ ]} أدى هذا الخلاف حول الأسبقية إلى خلاف بين سيلفستر وكيركمان.
• في عامي 1861-1862، نشب خلاف بين كيركمان وآرثر كايلي حول مسألة لا صلة لها بالموضوع (امتناع كايلي عن نشر سلسلة من أبحاث كيركمان حول نظرية الزمر والمجسمات، الأمر الذي كلف كيركمان مكانة مرموقة في الأوساط الرياضية الأوروبية)، مما ساهم في تهميشه من قبل المؤسسة الرياضية. وقد طُويت صفحة بحثه الشامل الذي نُشر عام 1847 في غياهب النسيان، حيث نسب العديد من المؤلفين اللاحقين الفضل إلى شتاينر أو ريس، دون علمهم بالتاريخ.
• لم تتأثر شعبية لغز تلميذة المدرسة بالخلافات الأكاديمية التي واجهها كيركمان، وفي أواخر القرن التاسع عشر وأوائل القرن العشرين، ظهر اللغز في العديد من كتب الرياضيات الترفيهية لإدوارد لوكاس ، ^{[ 10 ]} وراوس بول ، ^{[ 11 ]} وويلهلم أهرنز ، ^{[ 12 ]} وهنري دوديني . ^{[ 13 ]} وفي حياته، اشتكى كيركمان من أن أعماله الرياضية الجادة طغت عليها شعبية مسألة تلميذة المدرسة. ^{[ 6 ]} توفي كيركمان عام 1895.
• في عام 1918، أعيد لفت انتباه أوسع إلى أعمال كيركمان الرياضية الجادة من قبل لويز دوفيلد كامينغز في ورقة بحثية بعنوان "ورقة كيركمان التي لم تحظ بالتقدير الكافي " ^{[ 6 ]} والتي ناقشت التاريخ المبكر للمجال وصححت الإغفال التاريخي.
• في نفس الفترة تقريبًا، كان كامينغز يعمل مع فرانك نيلسون كول وهنري سيلي وايت على الأنظمة الثلاثية. وقد تُوِّج هذا العمل بورقتهم البحثية الشهيرة التي نُشرت عام 1919 بعنوان " التصنيف الكامل لأنظمة الثلاثيات المكونة من 15 عنصرًا " ^{[ 14 ]} ، والتي كانت أول ورقة بحثية تُفصِّل جميع الحلول الثمانين لنظام شتاينر الثلاثي المكون من 15 عنصرًا. وشملت هذه الحلول أنظمة قابلة للحل وأخرى غير قابلة للحل.
• في عام ١٩٢٢، نشر كول بحثه "مواكب كيركمان " ^{[ ٤ ]} الذي سرد ​​لأول مرة جميع الحلول السبعة غير المتماثلة لمسألة التلميذات الخمس عشرة، مجيبًا بذلك على سؤالٍ ظلّ قائمًا منذ خمسينيات القرن التاسع عشر. تتوافق حلول كيركمان السبعة مع أربعة أنظمة شتاينر مختلفة عند إزالة قيد قابلية التقسيم إلى فئات متوازية. ثلاثة من أنظمة شتاينر لها طريقتان محتملتان للتقسيم إلى فئات متوازية، أي حلان لكيركمان لكل منها، بينما الرابع له طريقة واحدة فقط، ليصبح المجموع سبعة حلول لكيركمان.
• في ستينيات القرن العشرين، ثبت وجود أنظمة كيركمان الثلاثية لجميع الرتب n = 3 (mod 6). وقد أثبت ذلك لأول مرة لو جياشي ( بالصينية :陆家羲) عام 1965، ^{[ 15 ]} وقدم بحثه إلى مجلة "أكتا ماثيماتيكا سينيكا"، إلا أن المجلة اعتقدت خطأً أن المسألة قد حُلت بالفعل، فرفضت بحثه عام 1966، وهو ما تبين لاحقًا أنه خطأ جسيم. ^{[ 16 ]} وتأثرت إسهاماته الأكاديمية اللاحقة بالثورة الثقافية ، فرُفضت أبحاثه مرة أخرى. وفي عام 1968، أثبت كل من دي كي راي تشودري وآر إم ويلسون النظرية المعممة بشكل مستقل . ^{[ 17 ]}
• في عام 1974، حلّ آر إتش إف دينستون مسألة سيلفستر المتمثلة في بناء 13 حلاً منفصلاً لكيركمان واستخدامها لتغطية جميع الثلاثيات البالغ عددها 455 على الفتيات الـ 15. ^{[ 18 ]} سيتم مناقشة حله أدناه.

تساءل جيمس جوزيف سيلفستر في عام 1850 عما إذا كان من الممكن إنشاء 13 نظامًا منفصلاً من أنظمة كيركمان، يتكون كل منها من 35 ثلاثية، لاستخدام جميع${\textstyle {15 \choose 3}=455}$ثلاثة أرقام على 15 فتاة. لم يُعثر على حل حتى عام 1974 عندما ابتكره آر إتش إف دينستون في جامعة ليستر باستخدام الحاسوب. ^{[ 18 ]} تمثلت فكرة دينستون في ابتكار حل كيركمان لأسبوع واحد بطريقة تسمح بتبديله وفقًا لتبديل محدد بطول دورة 13 لإنشاء حلول منفصلة للأسابيع اللاحقة؛ وقد اختار تبديلًا بدورة واحدة طولها 13 ونقطتين ثابتتين مثل (1 2 3 4 5 6 7 8 9 10 11 12 13)(14)(15). في ظل هذا التبديل، ستُقابل ثلاثية مثل 123 الأرقام 234، 345، ... (11، 12، 13)، (12، 13، 1)، و(13، 1، 2) قبل أن تتكرر. قام دينستون بتصنيف 455 ثلاثية إلى 35 صفًا، كل صف منها يحتوي على 13 ثلاثية، ويمثل كل صف مدار ثلاثية معينة تحت التبديل. ^{[ 18 ]} ولإنشاء حل سيلفستر، لا يمكن لأي حل كيركمان لأسبوع واحد أن يستخدم ثلاثيتين من نفس الصف، وإلا ستتداخلان عند تطبيق التبديل على إحداهما. حل مسألة سيلفستر يُعادل إيجاد ثلاثية واحدة من كل صف من الصفوف الـ 35 بحيث تُشكل الثلاثيات الـ 35 معًا حل كيركمان. ثم طلب من حاسوب إليوت 4130 إجراء هذا البحث تحديدًا، والذي استغرق منه 7 ساعات لإيجاد حل الأسبوع الأول، ^{[ 18 ]} حيث قام بتسمية الفتيات الـ 15 بالأحرف من A إلى O.

اليوم الأول ABJ CEM FKL HIN DGO اليوم الثاني ACH DEI FGM JLN BKO اليوم الثالث ADL BHM GIK CFN EJO اليوم الرابع AEG BIL CJK DMN FHO اليوم الخامس AFI BCD GHJ EKN LMO اليوم السادس AKM DFJ EHL BGN CIO اليوم السابع BEF CGL DHK IJM ANO 

توقف عن البحث عند تلك النقطة، ولم يكن يسعى إلى إثبات التفرد. ^{[ 18 ]}

قام الملحن الأمريكي توم جونسون، صاحب المدرسة التبسيطية، بتأليف مقطوعة موسيقية بعنوان " سيدات كيركمان" استناداً إلى حل دينستون. ^{[ 19 ] [ 20 ]}

حتى عام 2021، لم يكن معروفاً ما إذا كانت هناك حلول أخرى غير متماثلة لمشكلة سيلفستر، أو كم عدد الحلول الموجودة.

اليوم الأول: 123456789 اليوم الثاني: 147 258 369 اليوم الثالث: 159 267 348 اليوم الرابع: 168 249 357 

الحل الأول: اليوم الأول اليوم الثاني اليوم الثالث اليوم الرابع الأسبوع الأول ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG الأسبوع الثاني ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG الأسبوع 3 ABE.CDI.FGH ACG.BDF.EHI ADH.BGI.CEF AFI.BCH.DEG الأسبوع 4 ABF.CEI.DGH ACD.BHI.EFG AEH.BCG.DFI AGI.BDE.CFH الأسبوع الخامس ABG.CDE.FHI ACH.BEI.DFG ADI.BCF.EGH AEF.BDH.CGI الأسبوع السادس ABH.CDF.EGI ACI.BDG.EFH ADE.BFI.CGH AFG.BCE.DHI الأسبوع السابع ABI.CFG.DEH ACE.BFH.DGI ADF.BEG.CHI AGH.BCD.EFI 

الحل الثاني: اليوم الأول اليوم الثاني اليوم الثالث اليوم الرابع الأسبوع الأول ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG الأسبوع الثاني ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG الأسبوع 3 ABE.CGH.DFI ACI.BFH.DEG ADH.BGI.CEF AFG.BCD.EHI الأسبوع الرابع ABF.CGI.DEH ACE.BDG.FHI ADI.BCH.EFG AGH.BEI.CDF الأسبوع الخامس ABG.CDI.EFH ACH.BDF.EGI ADE.BHI.CFG AFI.BCE.DGH الأسبوع السادس ABH.CEI.DFG ACD.BFI.EGH AEF.BCG.DHI AGI.BDE.CFH الأسبوع السابع ABI.CDE.FGH ACG.BDH.EFI ADF.BEG.CHI AEH.BCF.DGI 

في عام 1910، تمت معالجة المشكلة باستخدام هندسة غالوا بواسطة جورج كونول. ^{[ 23 ]}

يُستخدم حقل غالوا GF(2) ذو العنصرين مع أربعة إحداثيات متجانسة لتكوين PG ( 3,2) الذي يحتوي على 15 نقطة، 3 نقاط على كل خط، و7 نقاط و7 خطوط في مستوى. يمكن اعتبار المستوى شكلاً رباعياً كاملاً مع الخط المار بقطره. تقع كل نقطة على 7 خطوط، ويبلغ عدد الخطوط الإجمالي 35 خطاً.

تُحدد خطوط PG(3,2) بإحداثيات بلوكر الخاصة بها في PG(5,2) بـ 63 نقطة، 35 منها تمثل خطوط PG(3,2). تُشكل هذه النقاط الـ 35 السطح S المعروف باسم سطح كلاين الرباعي . لكل نقطة من النقاط الـ 28 الخارجة من S، توجد 6 خطوط تمر بها ولا تتقاطع مع S. ^{[ 23 ] : 67}

بما أن الأسبوع يتكون من سبعة أيام، فإن العدد السباعي يمثل جزءًا مهمًا من الحل:

عند اختيار نقطتين A وB على الخط ABC، يتقاطع كل خط من الخطوط الخمسة الأخرى المارة بالنقطة A مع خط واحد فقط من الخطوط الخمسة الأخرى المارة بالنقطة B. تُسمى النقاط الخمس الناتجة عن تقاطع هذه الخطوط، بالإضافة إلى النقطتين A وB، "سباعية". ^{[ 23 ] : 68}

تُحدد المجموعة السباعية بأي نقطتين منها. تقع كل نقطة من النقاط الـ 28 على S في مجموعتين سباعيتين. يوجد 8 مجموعات سباعية. المجموعة الخطية الإسقاطية PGL(3,2) متماثلة مع المجموعة المتناوبة على المجموعات السباعية الثمانية. ^{[ 23 ] : 69}

تتمثل مسألة تلميذة المدرسة في إيجاد سبعة خطوط في الفضاء الخماسي لا تتقاطع، بحيث يكون لأي خطين منها دائمًا سباعي مشترك. ^{[ 23 ] : 74}

في فضاء PG(3,2)، يُطلق على تقسيم النقاط إلى خطوط اسم "انتشار" ، ويُطلق على تقسيم الخطوط إلى انتشارات اسم " تعبئة" أو "توازي" . ^{[ 24 ] : 66} يوجد 56 انتشارًا و240 تعبئة. عندما تناول هيرشفيلد هذه المسألة في كتابه " الفضاءات الإسقاطية المنتهية ثلاثية الأبعاد " (1985)، لاحظ أن بعض الحلول تُطابق تعبئات فضاء PG(3,2)، كما وصفها كونيل أعلاه، ^{[ 24 ] : 91،} وقدّم اثنين منها. ^{[ 24 ] : 75}

يمكن تعميم المشكلة إلى${\displaystyle n}$يا فتيات، أين${\displaystyle n}$يجب أن يكون مضاعفًا فرديًا للعدد 3 (أي${\displaystyle n\equiv 3{\pmod {6}}}$)، المشي في مجموعات ثلاثية لـ${\textstyle {\frac {1}{2}}(n-1)}$أيام، مع اشتراط، مرة أخرى، ألا يسير زوج من الفتيات في نفس الصف مرتين. حل هذا التعميم هو نظام شتاينر الثلاثي ، وهو S(2, 3, 6t + 3) مع التوازي (أي، نظام يظهر فيه كل عنصر من عناصر 6t + 3 مرة واحدة فقط في كل مجموعة من المجموعات المكونة من 3 عناصر)، والمعروف باسم نظام كيركمان الثلاثي . ^{[ 25 ]} هذا التعميم للمسألة هو ما ناقشه كيركمان أولاً، بينما الحالة الخاصة الشهيرة${\displaystyle n=15}$لم يُقترح هذا الحل إلا لاحقًا. ^{[ 26 ]} نُشر حل كامل للحالة العامة بواسطة دي كي راي-تشودري وآر إم ويلسون في عام 1968، ^{[ 17 ]} على الرغم من أن لو جياشي ( بالصينية :陆家羲) كان قد حلّها بالفعل في عام 1965، ^{[ 15 ]} ولكن لم يُنشر في ذلك الوقت. ^{[ 16 ]}

يمكن النظر في العديد من الاختلافات للمشكلة الأساسية. قام آلان هارتمان بحل مشكلة من هذا النوع مع اشتراط ألا يسير أي ثلاثي في ​​صف من أربعة أكثر من مرة ^{[ 27 ]} باستخدام أنظمة شتاينر الرباعية.

وفي الآونة الأخيرة، اكتسبت مشكلة مماثلة تُعرف باسم مشكلة لاعب الجولف الاجتماعي اهتمامًا، وهي تتعلق بـ 32 لاعب جولف يرغبون في اللعب مع أشخاص مختلفين كل يوم في مجموعات من 4 أفراد، على مدار 10 أيام.

بما أن هذه استراتيجية لإعادة التجميع حيث تكون جميع المجموعات متعامدة، فإن هذه العملية ضمن مشكلة تنظيم مجموعة كبيرة إلى مجموعات أصغر حيث لا يشترك شخصان في نفس المجموعة مرتين يمكن الإشارة إليها باسم إعادة التجميع المتعامدة. ^{[ 28 ]}

تتناول مشكلة الأغطية القابلة للحل الموضوع العام${\displaystyle n}$فتيات،${\displaystyle g}$ groups case where each pair of girls must be in the same group at some point, but we want to use as few days as possible. This can, for example, be used to schedule a rotating table plan, in which each pair of guests must at some point be at the same table.^[29]

The Oberwolfach problem, of decomposing a complete graph into edge-disjoint copies of a given 2-regulargraph, also generalizes Kirkman's schoolgirl problem. Kirkman's problem is the special case of the Oberwolfach problem in which the 2-regular graph consists of five disjoint triangles.^[30]

• Cooperative learning strategy for increasing interaction within classroom teaching
• Dobble card game^[31]
• Progressive dinner party designs
• Speed Networking events
• Sports Competitions
• Combinatorics
• R M Wilson
• Dijen K. Ray-Chaudhuri
• Discrete mathematics

• كلاريش، إريكا (9 يونيو 2015)، "حل معضلة التصميم، بدون تصاميم." ، مجلة كوانتا
• سلسلة نصية (مارس 2015) - عرض مرئي للحل ، ستاك إكستشينج