त्रिभुज पर चींटियाँ: टकराव न होने की प्रायिकता (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली समस्या ६.४: त्रिभुज के शीर्षों पर तीन चींटियाँ यादृच्छिक दिशा चुनती हैं। आठ परिणाम गिनो, कब सिर्फ पीछा होता है वह देखो, प्रायिकता १/४। जावा में गणना शामिल।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तीन चींटियाँ एक त्रिभुज के तीन कोनों पर बैठी हैं। एक ही क्षण हर चींटी किनारे पर बाएँ या दाएँ चुनती है और एक जैसी गति से चलने लगती है। क्या वे टकराएँगी? इंटरव्यू का सवाल भौतिकी का सिमुलेशन नहीं है। यह छोटा गिनती वाला सवाल है: हर समान रूप से संभावित विकल्पों में से कितने दिशा-संयोजन टकराव बचाते हैं?

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू की क्लासिक गणित-और-तर्क पहेलियों जैसी समस्या, किसी किताब की नकल नहीं। सीटीसीआई जावा श्रृंखला का हिस्सा। अध्याय ६, गणित और तर्क, समस्या ६.४।

---

१. रोज़मर्रा की उपमा

सोचो तीन लोग पार्क के त्रिभुजाकार रास्ते के तीन कोनों पर खड़े हैं। हर कोई सिक्का उछालता है: घड़ी की दिशा में घूमो, या उल्टी दिशा में। सबकी चाल एक जैसी।

अगर तीनों सिक्के एक जैसे निकलें, वे दूरी बनाए रखते हैं। हर कोई आगे वाले का पीछा करता है और पीछे वाले से पीछा करवाता है। किसी किनारे पर आमने-सामने मुलाकात नहीं। बस घूमते रहते हैं।

अगर एक भी व्यक्ति उल्टी दिशा जाए, किसी किनारे पर दो लोग एक-दूसरे की ओर चलते हैं। आमने-सामने मिलते हैं। इस पहेली में वही टकराव है।

तो पहेली यह है: तीन सिक्के, चित या पट। कितनी बार तीनों मेल खाते हैं?

---

२. सादे शब्दों में समस्या

सेटअप:

• समबाहु त्रिभुज (आकार असल में मायने नहीं रखता; तीन शीर्ष, तीन किनारे)।
• हर शीर्ष पर एक चींटी।
• हर चींटी स्वतंत्र रूप से दिशा चुनती है: घड़ी की दिशा (सीडब्ल्यू) या उल्टी दिशा (सीसीडब्ल्यू), हर एक की प्रायिकता 1/2।
• सभी चींटियाँ किनारों पर एक जैसी स्थिर गति से चलती हैं।

टकराव का नियम (इंटरव्यू में ज़ोर से कहो):

• दो चींटियाँ टकराती हैं अगर वे एक ही किनारे पर एक-दूसरे की ओर चल रही हों (आमने-सामने मुलाकात)।
• अगर तीनों एक ही दिशा चुनें, कभी आमने-सामने नहीं मिलतीं। बराबर दूरी बनाए रखकर घूमती रहती हैं।
• सामान्य मॉडल में "शीर्ष पर गुज़रना" अलग मामला नहीं मानते: सिर्फ सब-एक-दिशा वाली दौड़ें टकराव-मुक्त हैं।

सवाल: चींटियाँ कभी न टकराएँ, इसकी प्रायिकता क्या है?

हल से पहले स्पष्ट करो:

• क्या दिशाएँ स्वतंत्र और निष्पक्ष हैं? (हाँ: हर चींटी, हर दिशा, प्रायिकता 1/2।)
• क्या समान गति मायने रखती है? (आमने-सामने कहानी के लिए हाँ। अलग गति मिलन बिंदु बदल सकती है, लेकिन क्लासिक जवाब फिर भी दिशा-सहमति पर टिका है।)
• क्या टकराव सिर्फ आमने-सामने है, या पीछे से पकड़ना भी? (क्लासिक कथन: आमने-सामने। समान गति पर एक-दिशा वाली चींटियाँ एक-दूसरे को नहीं पकड़तीं।)
• n चींटियाँ n-भुज पर? अच्छा अगला सवाल। वही विचार: सिर्फ दो वैश्विक अभिविन्यास चलते हैं।

---

३. पहले सोचो

प्रतिदर्श समष्टि

हर चींटी के २ विकल्प। तीन चींटियाँ:

total outcomes = 2^3 = 8

सिक्के निष्पक्ष हों तो आठों समान रूप से संभावित। उन्हें त्रिक (A, B, C) के रूप में लिखो जहाँ 0 का मतलब सीडब्ल्यू और 1 का मतलब सीसीडब्ल्यू (शीर्षों का कोई भी लेबल ठीक)।

(0,0,0)  सब सीडब्ल्यू
(0,0,1)
(0,1,0)
(0,1,1)
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)  सब सीसीडब्ल्यू

कौन टकराव बचाते हैं?

सिर्फ दो समान पंक्तियाँ:

• सब सीडब्ल्यू: (0,0,0)
• सब सीसीडब्ल्यू: (1,1,1)

हर मिश्रित पंक्ति में कम से कम एक पड़ोसी जोड़ी ने उल्टी दिशाएँ चुनीं, इसलिए वे बीच के किनारे पर एक-दूसरे की ओर चलती हैं और टकराती हैं।

अतः:

favorable = 2
probability = 2 / 8 = 1/4

कहने का दूसरा तरीका

चींटी ए को स्थिर करो (दिशा मुक्त, प्रायिकता १)। बी को ए से मेल खाना चाहिए (1/2)। सी को ए से मेल खाना चाहिए (1/2)। गुणनफल:

P(no collision) = 1 * (1/2) * (1/2) = 1/4

आठ पंक्तियाँ लिखे बिना वही जवाब। शुरुआती कहानी के लिए इंटरव्यू में सूची बेहतर है, क्योंकि साक्षात्कारकर्ता देखता है कि तुमने गिना।

मिश्रित दिशाएँ हमेशा क्यों टकराती हैं (समान गति)

शीर्ष A, B, C को सीडब्ल्यू क्रम में नाम दो। किनारा AB शुरू में सिर्फ ए और बी रखता है।

• अगर ए सीडब्ल्यू बी की ओर चले और बी सीसीडब्ल्यू ए की ओर: AB पर आमने-सामने।
• अगर ए सीसीडब्ल्यू (सी की ओर) चले और बी सीडब्ल्यू: कहीं और फिर भी आमने-सामने आता है, क्योंकि तीनों मेल नहीं खाते।

इंटरव्यू में हर मिश्रित पैटर्न केस-बाश की ज़रूरत नहीं अगर साफ़ प्रमेय कहो:

टकराव-मुक्त तभी जब हर चींटी एक ही अभिविन्यास चुने।

"यदि" का प्रमाण: एक दिशा, समान गति, स्थिर अंतराल, कोई आमने-सामने नहीं। "केवल यदि" का प्रमाण: अगर कोई अलग हो, वह चींटी और कोई पड़ोसी साझा किनारे पर विरोधी जोड़ी बनाते हैं (या चक्र त्रिभुज पर कम से कम एक विरोधी पड़ोसी जोड़ी मजबूर करता है)।

त्रिभुज पर यह खास साफ़ है: दो दिशाएँ मतलब कम से कम एक किनारे पर उल्टी यातायात।

अगला सवाल: नियमित n-भुज पर n चींटियाँ

वही मॉडल: हर एक सीडब्ल्यू या सीसीडब्ल्यू चुनता है प्रायिकता 1/2 से, समान गति, टकराव = किनारे पर आमने-सामने।

सिर्फ दो सुरक्षित विन्यास: सब सीडब्ल्यू, सब सीसीडब्ल्यू।

P = 2 / 2^n = 2^(1-n)

n = 3 के लिए: 2^(1-3) = 2^(-2) = 1/4। वही जवाब।

n = 4 के लिए: 1/8। बड़े n पर प्रायिकता शून्य की ओर गिरती है। लगभग हमेशा कोई असहमत होता है।

---

४. जावा समाधान

बंद रूप के लिए भारी कोड की ज़रूरत नहीं। फिर भी, परिणाम गिनना गिनती दिखाने का साफ़ तरीका है, और n तक फैलता है।

बंद रूप

/** Probability all n ants agree on direction (fair coins, independent). */
static double noCollisionProbability(int n) {
    if (n < 1) {
        throw new IllegalArgumentException("n must be at least 1");
    }
    // 2 favorable out of 2^n
    return 2.0 / Math.pow(2, n);
}

// triangle
// noCollisionProbability(3) == 0.25

सभी 2^n मास्क गिनो

बिट i चींटी i की दिशा है (0 सीडब्ल्यू, 1 सीसीडब्ल्यू)। मास्क सुरक्षित तभी जब हर बिट ० हो या हर बिट १ हो।

/**
 * Count direction assignments with no head-on collision.
 * Bit i of the mask is ant i's direction.
 */
static int countSafeConfigs(int n) {
    if (n < 1 || n > 30) {
        throw new IllegalArgumentException("n out of supported range");
    }
    int total = 1 << n; // 2^n
    int safe = 0;
    int allOnes = total - 1; // n bits set
    for (int mask = 0; mask < total; mask++) {
        if (mask == 0 || mask == allOnes) {
            safe++;
        }
    }
    return safe; // always 2 for n >= 1
}

static double probabilityByEnumeration(int n) {
    int total = 1 << n;
    return (double) countSafeConfigs(n) / total;
}

त्रिभुज की स्पष्ट तालिका (व्हाइटबोर्ड के लिए अच्छी)

static void printTriangleCases() {
    // ants A, B, C; 0 = CW, 1 = CCW
    String[] labels = {"CW", "CCW"};
    int safe = 0;
    for (int a = 0; a <= 1; a++) {
        for (int b = 0; b <= 1; b++) {
            for (int c = 0; c <= 1; c++) {
                boolean ok = (a == b) && (b == c);
                if (ok) {
                    safe++;
                }
                System.out.printf(
                    "(%s, %s, %s) -> %s%n",
                    labels[a], labels[b], labels[c],
                    ok ? "safe (all same)" : "collide");
            }
        }
    }
    System.out.println("safe / total = " + safe + " / 8 = " + (safe / 8.0));
}

लगभग आउटपुट:

(CW, CW, CW) -> safe (all same)
(CW, CW, CCW) -> collide
(CW, CCW, CW) -> collide
(CW, CCW, CCW) -> collide
(CCW, CW, CW) -> collide
(CCW, CW, CCW) -> collide
(CCW, CCW, CW) -> collide
(CCW, CCW, CCW) -> safe (all same)
safe / total = 2 / 8 = 0.25

यूनिट-शैली जाँच

assert Math.abs(noCollisionProbability(3) - 0.25) < 1e-9;
assert Math.abs(probabilityByEnumeration(3) - 0.25) < 1e-9;
assert countSafeConfigs(3) == 2;
assert countSafeConfigs(4) == 2;
assert Math.abs(noCollisionProbability(4) - 0.125) < 1e-9;
assert Math.abs(noCollisionProbability(1) - 1.0) < 1e-9; // one ant: never collides

---

५. क्लासिक मामलों से गुज़रना

सब घड़ी की दिशा में

ए, बी, सी पर चींटियाँ सब सीडब्ल्यू। थोड़ी देर बाद हर एक ने एक जैसा चाप तय किया। चींटियों के बीच दूरी एक भुजा जितनी बनी रहती है (परिधि पर)। कोई पड़ोसी की ओर आमने-सामने नहीं चलता। सुरक्षित।

सब उल्टी दिशा में

वही कहानी, उलटा अभिविन्यास। सुरक्षित।

दो सीडब्ल्यू, एक सीसीडब्ल्यू

मान लो ए और बी सीडब्ल्यू हैं, सी सीसीडब्ल्यू है। फिर ए किनारे AB पर बी की ओर चलता है जबकि बी सी की ओर... और सी लेबल के हिसाब से बी या ए की ओर। त्रिभुज पर अल्पसंख्यक दिशा कम से कम एक किनारे पर उल्टी यातायात बनाती है। टकराव।

ठोस: ए ऊपर, बी नीचे-दाएँ, सी नीचे-बाएँ। सीडब्ल्यू मतलब ए→बी, बी→सी, सी→ए। सीसीडब्ल्यू मतलब ए→सी, सी→बी, बी→ए।

अगर ए और बी सीडब्ल्यू चुनें और सी सीसीडब्ल्यू:

• ए बी की ओर चलता है (सीडब्ल्यू)।
• बी सी की ओर चलता है (सीडब्ल्यू)।
• सी बी की ओर चलता है (सीसीडब्ल्यू: सी→बी)।

तो बी और सी किनारे BC पर एक-दूसरे की ओर। आमने-सामने। खत्म।

कोई और मिश्रित त्रिक शीर्षों का नाम बदलने पर वही आकार है।

प्रायिकता अंकगणित

P(all CW)  = (1/2)^3 = 1/8
P(all CCW) = 1/8
P(safe)    = 1/8 + 1/8 = 1/4

या: 8 में से 2 अनुकूल मास्क।

---

६. जटिलता, किनारे, इंटरव्यू सुझाव

तरीका	समय	स्थान	नोट
बंद रूप 2 / 2^n	ओ(१)	ओ(१)	मॉडल साफ़ होने पर सबसे अच्छा जवाब
2^n मास्क गिनना	ओ(२ⁿ)	ओ(१)	कोड डेमो में n ≤ २० ठीक; n = ३ पर ज़्यादा
n = ३ के लिए नेस्टेड लूप	ओ(१)	ओ(१)	शुरुआती व्हाइटबोर्ड के लिए सबसे अच्छा

किनारे और जाल:

१. समान संभावना भूलना। अगर सिर्फ "दो अच्छे मामले" कहो और ८ से न बाँटो, काम अधूरा। २. किसी भी मुलाकात को टकराव कहना, एक-दिशा सहित। समान गति पर वे पकड़ नहीं पातीं। जब तक साक्षात्कारकर्ता मॉडल न बदले, आमने-सामने पर रहो। ३. लगना कि चलने का क्रम मायने रखता है। समान गति पर एक साथ चुनाव: शुद्ध संयोजनिकी। ४. फ़्लोटिंग पॉइंट का घमंड। सटीक भिन्न पसंद करो: 2/8 = 1/4। कोड में ही डबल। ५. n = 2 "द्विभुज" बेतुका। बहुभुज के लिए n ≥ 3 रखो, या नोट करो n = 1 तुच्छ रूप से १ है। ६. मानना कि वे उछलती या पलटती हैं। क्लासिक समस्या: एक बार चुनती हैं और संभावित मिलन तक चलती रहती हैं।

कैसे बोलें (३० सेकंड संस्करण):

१. हर चींटी की २ दिशाएँ, इसलिए ८ समान रूप से संभावित परिणाम। २. टकराव तभी बचता है जब सब सीडब्ल्यू चलें या सब सीसीडब्ल्यू। ३. यह ८ में से २ है, प्रायिकता 1/4। ४. सामान्य n-भुज: 2 / 2^n।

पहेली के बाहर कहाँ दिखता है:

• प्रायिकता इंटरव्यू में प्रतिदर्श समष्टि और स्वतंत्रता।
• "सहमति" घटनाएँ: सब बिट बराबर, सब वोट एक, सब घड़ियाँ एक कला।
• सममिति तर्क: सतत गति को विविक्त विकल्प गिनती तक घटाओ।

---

७. दोस्त को समझाने वाला सार

त्रिभुज पर चींटियाँ वन्यजीव का भेस पहनी गिनती की समस्या है।

१. तीन चींटियाँ, हर एक सीडब्ल्यू या सीसीडब्ल्यू चुनती है प्रायिकता 1/2 से। आठ परिणाम, सब बराबर। २. किनारे पर आमने-सामने टकराव गिना जाता है। समान गति, एक दिशा: सिर्फ पीछा, कभी आमने-सामने नहीं। ३. ठीक दो परिणाम सुरक्षित: सब सीडब्ल्यू, सब सीसीडब्ल्यू। ४. प्रायिकता: 2/8 = 1/4। ५. n-भुज पर n चींटियों के लिए: 2 / 2^n।

अगर आठ त्रिक लिख सको, दो समान वाले चिह्नित कर सको, और बता सको मिश्रित चुनाव आमने-सामने क्यों मजबूर करता है, समस्या ६.४ तुम्हारी है। कोई कैलकुलस नहीं। बस सावधानी से गिनना।

---

श्रृंखला

• मार्गदर्शिका: सीटीसीआई श्रृंखला मार्गदर्शिका
• पिछला: डोमिनो
• अगला: पानी के जग