ریاضیاتپیش‌چاپنظریه۳ دقیقه مطالعه

حدسی از 1969 دربارهٔ جمع‌هایی که یکدیگر را خنثی می‌کنند نادرست از آب درآمد

ساعتی با شش ساعت را در نظر بگیرید، و فهرستی از حرکت‌ها: «عقربه را 1 ساعت جلو ببر»، «4 ساعت جلو ببر» و غیره. با پنج حرکت که هر کدام یک ساعت است، هیچ گروهی از آن‌ها هرگز عقربه را دقیقاً به نقطهٔ آغاز بازنمی‌گرداند. با شش حرکت، هر چه باشند، همیشه گروهی این کار را می‌کند. ریاضی‌دانان این حساب ساعتی را C₆ می‌نویسند، و عدد شش در اینجا ثابت داونپورت (Davenport constant) این ساعت است.

اکنون 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) از دانشگاه تیانجین (Tianjin University)، آلفرد گرولدینگر (Alfred Geroldinger) از دانشگاه گراتس (University of Graz)، گوئوچینگ وانگ (Guoqing Wang) از دانشگاه تیانگونگ (Tiangong University) و شیانگ‌نِنگ زنگ (Xiangneng Zeng) از دانشگاه سون یات‌سن (Sun Yat-Sen University) اکنون نشان می‌دهند که این حدس نادرست است.

این تیم حرکت‌ها را مانند قطعه‌های ساختمانی کنار هم می‌چیند:

  • فهرستی از 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 ساعت، که در آن‌ها کران تازه با فرمول قدیمی برابر است، و نیز برای ساعت‌هایی با تعدادی ساعت غیر از شش، چیز تازه‌ای نمی‌گوید. این یادداشت پنج صفحه است، و داوری همتا هنوز در پیش است.