الرياضياتنسخة أوليةنظريةمدة القراءة: 3 د

تخمين من عام 1969 عن مجاميع يُلغي بعضها بعضًا يتبيّن أنه خاطئ

خذ ساعة ذات ست ساعات، وقائمة من الحركات: «أدِر العقرب إلى الأمام بمقدار 1 ساعة»، «إلى الأمام بمقدار 4 ساعات»، وهكذا. بخمس حركات كل منها ساعة واحدة، لا تعيد أي مجموعة منها العقرب إلى البداية بالضبط أبدًا. أما بـست حركات، أيًّا كانت، فستفعل ذلك دائمًا مجموعة ما منها. ويكتب علماء الرياضيات حساب الساعة هذا على الشكل C₆، والعدد ستة هنا هو ثابت دافنبورت لهذه الساعة.

ضع الآن r من هذه الساعات جنبًا إلى جنب، ودع كل حركة تُدير كل عقرب بمقدار خاص به. ثابت دافنبورت لمجموعة الساعات هذه، ويُكتب D(C₆^r)، هو أصغر عدد من الحركات يضمن وجود مجموعة يُعيد مجموعها كل العقارب إلى البداية في آنٍ واحد — أي متتالية جزئية مجموعها صفر (zero-sum)، بتعبير الورقة. ويرتبط هذا الثابت بمسائل في نظرية المخططات والهندسة المنتهية والتوافقيات ونظرية التحليل إلى عوامل.

صيغة من عام 1969

هناك حدّ أدنى سهل. على كل ساعة، خذ خمس حركات كل منها ساعة واحدة لا تمسّ إلا تلك الساعة: مع r من الساعات، يعطي ذلك 5r حركة لا توجد بينها أي مجموعة يُلغي بعضها بعضًا. إذن يلزم 5r + 1 حركة على الأقل. وعمومًا، بالنسبة إلى ساعات ذات n ساعة، يلزم r(n − 1) + 1 على الأقل.

وفي عام 1969، ظهر تخمين فان إمدي بوس (van Emde Boas) وكرويسفايك (Kruyswijk): أن هذا الحد السهل هو دائمًا الجواب الدقيق:

D(C_n^r) = r(n − 1) + 1.

وقد بُرهن عليه في عقد 1960 في بعض الحالات، مثل الساعات التي يكون عدد ساعاتها قوةً لعدد أولي، أو حين لا يتجاوز عدد الساعات اثنتين. وفيما عدا ذلك، ظلت القيمة الدقيقة بعيدة المنال: فحتى عام 2018، كانت حتى حالة أربع ساعات ذات ست ساعات مجهولة. ومع ذلك، صار التخمين «مسألة بارزة قائمة منذ زمن طويل» في هذا المجال، وكان متوقعًا أن يصح.

116 حركة لا يُلغي بعضها بعضًا أبدًا

والآن يتبيّن من عمل Weidong Gao (جامعة تيانجين) وAlfred Geroldinger (جامعة غراتس) وGuoqing Wang (جامعة تيانغونغ) وXiangneng Zeng (جامعة صن يات-سن) أن التخمين يُخفق.

يجمّع الفريق الحركات كما تُجمَّع قطع البناء:

  • قائمة من 24 حركة على خمس ساعات ذات ست ساعات، مبنية من جدول صغير: أي مجموعة منها يقع مجموعها ضمن مجموعة صغيرة من ثلاثة مواضع تقع دائمًا على الموضع نفسه غير الصفري؛
  • قائمتان من هذا النوع تتشاركان هذه المواضع الثلاثة، ما يعطي 48 حركة لا توجد بينها أي مجموعة يُلغي بعضها بعضًا؛
  • قائمة منفصلة من 20 حركة لا توجد بينها كذلك أي مجموعة يُلغي بعضها بعضًا.

وحين توضع هذه القوائم جنبًا إلى جنب، تعطي 2 × 48 + 20 = 116 حركة على 23 ساعة ذات ست ساعات، ولا تعيد أي مجموعة منها كل العقارب إلى البداية. وكان التخمين يقول إن 23 × 5 = 115 هي أطول قائمة ممكنة من هذا النوع. إذن بالنسبة إلى 23 ساعة، يكون ثابت دافنبورت 117 على الأقل، لا 116.

ويمكن تكديس نسخ من هذه الكتلة: والنتيجة العامة هي أن D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1، حيث يعدّ ⌊r/23⌋ كم كتلة كاملة من 23 تتسع لها r. إذن التخمين خاطئ في الساعات ذات الست ساعات بمجرد أن تبلغ r القيمة 23، ولكل r أكبر. ويشير الفريق إلى أن المبرهنة نفسها تدحض أيضًا نتيجة مُخمَّنة عن التغطيات (coverings).

ما يبقى مفتوحًا

لا يعطي البرهان القيمة الحقيقية لـ D(C₆^r)، بل حدًّا فقط يمنعه التخمين. ولا يقول شيئًا جديدًا عن أقل من 23 ساعة، حيث يساوي الحد الجديد الصيغة القديمة، ولا عن ساعات بعدد ساعات غير الستة. وتقع الورقة في خمس صفحات، ولم تخضع بعد لتحكيم الأقران.