♛ सुवर्ण गुणोत्तर पाळणाऱ्या बुद्धिबळातील राण्या

उजवीकडे आणि वरच्या दिशेने कायमचा पसरलेला एक बुद्धिबळपट घ्या. डाव्या खालच्या कोपऱ्यात एक राणी ठेवा. मग एक स्तंभ उजवीकडे सरका आणि आधीच्या कोणत्याही राणीच्या हल्ल्यात नसलेल्या सर्वात खालच्या घरात राणी ठेवा — त्याच ओळीत नाही, त्याच कर्णावर नाही, त्याच प्रतिकर्णावर नाही. हेच पुन्हा पुन्हा, स्तंभामागून स्तंभ, कायमचे करत राहा.

हा एक लोभी (greedy) नियम आहे: प्रत्येक राणी पुढचे नियोजन न करता पहिली मोकळी जागा घेते. त्यातून मिळणाऱ्या ओळी अशा सुरू होतात: 0, 2, 4, 1, 3, 8, 10, 12, 14, 5, 7, 18, 6, 21, 9… त्या अनियमित वाटतात. पण तशा नाहीत.

पहिले 20 स्तंभ. हिरवट-निळ्या राण्या मुख्य कर्णाच्या वर, नारिंगी राण्या खाली. — आकृती 1, Ho (2026), arXiv:2609.31336.

दोन रेषा आणि एक प्रसिद्ध संख्या

पहिल्या शंभर स्तंभांतील राण्यांचा आलेख काढा, आणि त्या दोन सरळ रेषांवर येतात. कर्णाच्या वरच्या राण्या 1.618 च्या जवळपास उताराने चढतात; खालच्या राण्या 0.618 च्या जवळपास उताराने. दोन्ही संख्या सुवर्ण गुणोत्तराशी (golden ratio) जोडलेल्या आहेत, φ = (1 + √5)/2: एक रेषा y = xφ आहे, दुसरी y = x/φ.

समान प्रमाणातील अक्षांवर, पहिल्या 100 स्तंभांतील राण्यांची स्थाने, y = xφ आणि y = x/φ या रेषांसह. — आकृती 2, Ho (2026), arXiv:2609.31336.

ही श्रेणी 2001 पासून पूर्णांक श्रेणींच्या ऑनलाइन ज्ञानकोशात (OEIS) आहे. 2020 मध्ये मिशेल डेकिंग, जेफ्री शॅलिट आणि नील स्लोन यांनी अनुमान मांडले की राण्या या दोन रेषांपासून एका मर्यादित अंतरापेक्षा जास्त दूर कधीच जात नाहीत. डोनाल्ड क्नुथ यांनी ते संख्यात्मकरीत्या एक अब्ज स्तंभांपर्यंत तपासले. कोणीही ते सिद्ध केले नव्हते.

प्रमेय

नॅशनल युनिव्हर्सिटी ऑफ सिंगापूरचे बून सुआन हो आता ते स्पष्ट सीमांसह सिद्ध करतात. प्रत्येक स्तंभ n साठी:

• कर्णाच्या वरची राणी y = xφ या रेषेपासून 5/φ ≈ 3.09 घरांपेक्षा कमी अंतरावर असते;
• त्याच्या खालची राणी y = x/φ या रेषेपासून 4 + 5/φ ≈ 7.09 घरांपेक्षा कमी अंतरावर असते.

सुवर्ण गुणोत्तरच का? समजा राण्यांचा θ इतका अंश कर्णाच्या वर आहे. दोन्ही कुटुंबे ओळी आणि कर्ण कसे वाटून घेतात हे मोजल्यावर θ ला θ² + θ = 1 पूर्ण करावे लागते, ज्याचे धन उत्तर 1/φ आहे. खरी अडचण म्हणजे त्रुटी कधीच वाढत नाही हे दाखवणे. सगळे एका महत्त्वाच्या प्रमेयिकेवर (lemma) येऊन थांबते: कर्णाखालची j-वी राणी नेहमी j-व्या खालच्या कर्णापासून 4 कर्णांच्या आत असते.

यंत्राने तपासलेली सिद्धता

ती प्रमेयिका सिद्ध करण्यासाठी, हो प्रत्येक स्तंभापूर्वीच्या पटाचे वर्णन एका लहान ‘स्थानिक अवस्थे’ने करतात: काही संख्या, आणि उंचावरच्या राण्या कुठे आहेत याची नोंद ठेवणारे चार-अक्षरी वर्णमालेतील छोटे शब्द. 12-अक्षरी शब्दांचा एक मर्यादित ‘इतिहास-आलेख’ (2,092 शिरोबिंदू, 2,603 कडा) कोणत्या अक्षरानंतर कोणते अक्षर येऊ शकते हे सांगतो. मग एक संगणक स्तंभ 30 पासून पोहोचता येणाऱ्या प्रत्येक अवस्थेचा शोध घेतो: 7,014 अवस्था, आणि प्रत्येक अवस्था आवश्यक सीमा पाळते. एक विगमन (induction) दाखवते की खरी श्रेणी हा मर्यादित संच कधीच सोडत नाही.

कोणताही कोड सामायिक न करणारे दोन स्वतंत्र प्रोग्राम त्याच अवस्थांपर्यंत पोहोचतात. Lean या सिद्धता-सहाय्यकातील एक औपचारिकीकरण शोधनिबंधासोबत आहे, आणि सगळा कोड सार्वजनिक आहे.

बोनस: एक खेळ आणि एक जलद जनक

या राण्यांमध्ये एक खेळ दडलेला आहे. एकच राणी डावीकडे, खाली, किंवा डावीकडील कर्णरेषेत हलवा; जो हलवू शकत नाही तो हरतो. हरणारी घरे म्हणजे नेमक्या लोभी राण्या. प्रतिकर्णावरील चाल काढून टाका, आणि तुम्हाला Wythoff’s Nim मिळतो, जो खेळ सुवर्ण गुणोत्तराने नियंत्रित असल्याचे आधीच माहीत आहे.

या सिद्धतेतून एक विलक्षण काटकसरी अल्गोरिदमही मिळतो. हो यांच्या प्रोग्रामने सुमारे 25 सेकंदांत दहा अब्ज राण्या निर्माण केल्या, फक्त 1.76 मेगाबाइट स्मृती वापरून, तर क्नुथ यांच्या प्रोग्रामच्या एका रूपांतराला 49 सेकंद आणि 6 गिगाबाइटपेक्षा जास्त लागले. असे दिसून येते की पटाच्या प्रत्येक कर्णावर नेमकी एकच राणी असते.

AI च्या साहाय्याने सापडलेली

शोधनिबंध एका घोषणेने संपतो: “सिद्धता GPT-6 Pro च्या साहाय्याने सापडली, ज्याने या शोधनिबंधाचा प्राथमिक मसुदाही तयार केला.” नंतर लेखकाच्या मार्गदर्शनाखाली Claude Opus 5.5 वापरून त्यात सुधारणा केल्या गेल्या. एक प्रश्न अजूनही खुला आहे: क्नुथ यांच्या अधिक घट्ट खालच्या सीमा, ज्या संगणकाने शंभर अब्ज स्तंभांपर्यंत पडताळल्या आहेत, अजूनही सिद्धतेच्या प्रतीक्षेत आहेत.