द अपोकैलिप्स: लड़के, लड़कियाँ, और वो नियम जो फिर भी ५०/५० रहता है (जावा)

टीएल;डीआर

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

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

ऐसा नहीं होता। निष्पक्ष ५०/५० जन्मों पर, लड़कों और लड़कियों का वैश्विक अनुपात फिर भी १:१ की ओर जाता है।

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

---

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

निष्पक्ष सिक्का सोचो। चित = लड़का, पट = लड़की। हर परिवार पहला चित आने तक उछालता है, फिर सिक्का रख देता है।

• कुछ परिवार एक बार उछालते हैं: चित। एक लड़का। शून्य लड़कियाँ।
• कुछ पट-चित। एक लड़की, फिर एक लड़का।
• कुछ पट-पट-चित। दो लड़कियाँ, फिर एक लड़का।
• दुर्लभ परिवार पहले चित से पहले लंबी पट-लड़ी निकालते हैं।

हर परिवार ठीक एक लड़के पर खत्म होता है। लड़कियों की संख्या यादृच्छिक है: ०, १, २, ३, ... घटती संभावना के साथ।

अब पूरा कस्बा जोड़ो। बहुत से एक-लड़का परिवार। कम परिवार बहुत लड़कियों वाले। दुर्लभ, लड़की-भारी परिवार बिल्कुल इतने दुर्लभ हैं कि सीमा में कुल लड़कियाँ कुल लड़कों के बराबर आ जाएँ। सिक्के को नीति की "खबर" नहीं। हर उछाल आधा-आधा ही रहता है।

---

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

सेटअप (क्लासिक रूप):

• हर जन्म स्वतंत्र रूप से लड़का या लड़की, संभावना 1/2।
• हर परिवार लड़का होने तक बच्चे पैदा करता है, फिर रुकता है।
• परिवार स्वतंत्र। न जुड़वाँ, न लिंग चयन, न मृत्यु के छल। सिर्फ रुकने का नियम।

सवाल: आबादी में लड़कों और लड़कियों का अनुपात क्या है (बहुत परिवार, सीमा भाव)?

लोग अक्सर अनुमान लगाते हैं: लड़कियाँ ज़्यादा, क्योंकि कुछ परिवार लड़के से पहले कई लड़कियाँ पैदा करते हैं।

हम दिखाएँगे: प्रति परिवार अपेक्षित लड़के = अपेक्षित लड़कियाँ = १। अनुपात १:१। काफ़ी परिवारों की सिमुलेशन लगभग ५०% लड़कों पर बैठती है।

कोड या प्रमाण से पहले स्पष्ट करो:

• क्या सिर्फ बच्चे गिनें, माता-पिता नहीं? (हाँ। बच्चों में लड़के और लड़कियाँ।)
• क्या जन्म क्रम नीति तय करती है? (हाँ: शून्य या ज़्यादा लड़कियाँ, फिर एक लड़का। उस परिवार में लड़के के बाद लड़की नहीं।)
• निष्पक्ष सिक्का? (हाँ। अगर P(boy) = p आधा नहीं, अनुपात बदलता है। इंटरव्यू डिफ़ॉल्ट निष्पक्ष।)
• आबादी अनुपात या परिवार-प्रकार अनुपात? (बच्चों की कुल गिनती।)

---

३. पहले सोचो

जाल वाली अंतर्ज्ञान

"बहुत परिवार लड़की-लड़की-लड़की-लड़की-लड़का जैसे दिखते हैं। लड़कियों का ढेर हावी होगा।"

गलत इकाई। वे परिवार दुर्लभ हैं। क लड़कियाँ फिर लड़का की संभावना (1/2)^{k+1} है। चार लड़कियाँ फिर लड़का सिर्फ 1/32 परिवारों में। चरम परिवार देखते हुए लंबी कतारों को ज़्यादा वज़न दे रहे हो।

साफ़ इकाई: एक परिवार, अपेक्षित गिनती

हर परिवार ठीक एक लड़का पैदा करता है (आखिरी बच्चा)। इसलिए:

E[boys per family] = 1

लड़कियाँ: संभावना 1/2 से पहला बच्चा लड़का, ० लड़कियाँ। संभावना 1/4 से पैटर्न जीबी, १ लड़की। संभावना 1/8 से जीजीबी, २ लड़कियाँ। और आगे।

E[girls] = 0*(1/2) + 1*(1/4) + 2*(1/8) + 3*(1/16) + ...
         = sum_{k=0}^{inf} k * (1/2)^{k+1}

मानक श्रेणी: |x| < 1 के लिए sum_{k=1}^{inf} k x^k = x / (1-x)^2।

यहाँ x = 1/2:

sum_{k=1}^{inf} k (1/2)^k = (1/2) / (1/2)^2 = (1/2)/(1/4) = 2

हमारी योग sum k * (1/2)^{k+1} = (1/2) * sum k (1/2)^k = (1/2)*2 = 1।

तो:

E[girls per family] = 1
E[boys per family]  = 1
ratio boys : girls  = 1 : 1

दूसरी दृष्टि: सभी जन्मों की अनंत श्रेणी

हर परिवार-आकार के अपेक्षित योगदान:

पैटर्न	संभावना	लड़के	लड़कियाँ	लड़के योगदान	लड़कियाँ योगदान
बी	१/२	१	०	१/२	०
जीबी	१/४	१	१	१/४	१/४
जीजीबी	१/८	१	२	१/८	२/८
जीजीजीबी	१/१६	१	३	१/१६	३/१६
...	...	१	क	...	...

लड़के योगदान योग: 1/2 + 1/4 + 1/8 + ... = 1।

लड़कियाँ योगदान योग: 0 + 1/4 + 2/8 + 3/16 + ... = 1 (ऊपर वाली श्रेणी)।

जन्म-स्तर तर्क (इंटरव्यू की छोटी पंक्ति)

हर बच्चा अब भी १/२ संभावना से लड़का या लड़की है, पिछले जन्मों से स्वतंत्र। नीति सिर्फ तय करती है कि परिवार फिर बच्चा लेगा या नहीं, अगले बच्चे का लिंग नहीं। स्वतंत्र निष्पक्ष जन्म जोड़ने से वैश्विक लड़की-पक्षपात पैदा नहीं होता। रुकने का नियम परिवार के आकार को शुरुआती लड़कों से जोड़ता है, किसी एक जन्म के लिंग को नहीं।

---

४. अनंत श्रेणी, साफ़ लिखी

मान लो एक परिवार में लड़कियों की संख्या G है। G ज्यामितीय है: पहले सफलता से पहले असफलताएँ, सफलता संभावना 1/2।

P(G = k) = (1/2)^{k+1}   for k = 0, 1, 2, ...
E[G]     = (1 - p) / p   for geometric failures-before-success with success p
         = (1/2) / (1/2) = 1

लड़के B = 1 हमेशा, इसलिए E[B] = 1।

न परिवारों पर कुल लड़के n, कुल लड़कियाँ अपेक्षा में लगभग n। अपेक्षाओं का अनुपात १। बड़ी संख्याओं के नियम से नमूना अनुपात न बढ़ने पर १ की ओर जाता है।

अगर फिर बंद रूप माँगे:

E[G] = sum_{k=0}^{inf} k (1/2)^{k+1}
     = (1/2) sum_{k=1}^{inf} k (1/2)^k
     = (1/2) * ( (1/2) / (1 - 1/2)^2 )
     = (1/2) * ( (1/2) / (1/4) )
     = (1/2) * 2
     = 1

---

५. जावा सिमुलेशन

गणित प्रमाण है। सिमुलेशन व्हाइटबोर्ड या टेस्ट-जैसी जाँच के लिए पेट का भरोसा।

import java.util.Random;

public final class ApocalypseRatio {
    private ApocalypseRatio() {}

    /** One family: keep having kids until a boy. Returns {boys, girls}. */
    static int[] oneFamily(Random rng) {
        int boys = 0;
        int girls = 0;
        while (true) {
            // true = boy
            if (rng.nextBoolean()) {
                boys++;
                break;
            } else {
                girls++;
            }
        }
        return new int[] {boys, girls};
    }

    /**
     * Simulate n families. Returns {totalBoys, totalGirls}.
     */
    static long[] simulate(int families, long seed) {
        Random rng = new Random(seed);
        long boys = 0;
        long girls = 0;
        for (int i = 0; i < families; i++) {
            int[] bg = oneFamily(rng);
            boys += bg[0];
            girls += bg[1];
        }
        return new long[] {boys, girls};
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        long[] totals = simulate(n, 42L);
        long b = totals[0];
        long g = totals[1];
        double ratioBoys = b / (double) (b + g);
        System.out.printf("families=%d boys=%d girls=%d boyFraction=%.4f%n",
                n, b, g, ratioBoys);
        // expect boys == n, girls ~ n, boyFraction ~ 0.50
    }
}

नोट:

• हर परिवार ठीक एक लड़का देता है, इसलिए boys हमेशा families के बराबर होना चाहिए। मुफ़्त असर्ट।
• girls families के आसपास यादृच्छिक। दस लाख परिवारों पर अंश ०.५ के पास बैठता है (ठेठ त्रुटि हज़ारवें हिस्से के क्रम की)।
• Random.nextBoolean() इस काम के लिए निष्पक्ष सिक्का है।

टेस्ट हार्नेस के वैकल्पिक सहायक:

static void assertInvariants(int families, long seed) {
    long[] t = simulate(families, seed);
    if (t[0] != families) {
        throw new AssertionError("every family has exactly one boy");
    }
    double frac = t[0] / (double) (t[0] + t[1]);
    if (Math.abs(frac - 0.5) > 0.01 && families >= 100_000) {
        throw new AssertionError("ratio drifted too far: " + frac);
    }
}

---

६. किनारे के मामले और इंटरव्यू फॉलो-अप

इंटरव्यूअर ये छेड़ते हैं:

• अनुचित सिक्का: अगर P(boy) = p, तो E[boys] = 1 अभी भी (पहले लड़के पर रुक), और E[girls] = (1-p)/p। अनुपात लड़के:लड़कियाँ = 1 : (1-p)/p = p : (1-p)। सिर्फ p = 1/2 पर १:१।
• दो लड़कों के बाद रुकना, या अन्य नीति: रुकने का नियम बदलो, अपेक्षा बदलती है। "हर जन्म निष्पक्ष" नारा जन्म-स्तर पर टिकता है, परिवार संरचना के वज़न बदलते हैं। श्रेणी फिर से लिखो।
• माता-पिता गिनना: अगर कोई माँ-बाप को "आबादी" में डाले, सवाल गंदा हो गया। पूछे बिना बच्चों पर रहो।
• छोटा न: १० परिवारों पर अनुपात शोर भरा। सीमा बनाम एक रन समझाओ।
• आखिरी बच्चा हमेशा लड़का: सच, और लोग इससे पक्षपात चिल्लाते हैं। याद दिलाओ कि पहले की लड़कियों की संख्या अपेक्षा में संतुलन लाती है।
• सहसंबंध बनाम पक्षपात: परिवार का आकार इस बात से जुड़ा कि पहले कितनी लड़कियाँ आईं। यह जन्म संभावना का पक्षपात नहीं।

आम गलतियाँ:

१. प्रति परिवार अनुपात का औसत (हर परिवार लड़के/लड़कियाँ, फिर औसत)। शून्य लड़की वाले परिवारों पर अनुपात अपरिभाषित या अनंत। कुल गिनती, या गिनती की अपेक्षाएँ इस्तेमाल करो। २. कुछ पैटर्न ही लिखना और पूंछ न जोड़ना। दुर्लभ परिवारों की अनंत पूंछ बंद रूप के लिए मायने रखती है। ३. "ज़्यादातर परिवारों में लड़कियाँ ज़्यादा" को "ज़्यादातर बच्चे लड़कियाँ" समझना। असल में ज़्यादातर परिवारों में शून्य या एक लड़की (बी और जीबी तीन-चौथाई परिवार)। लंबी पूंछ लड़कियों को लड़कों के बराबर खींचती है। ४. मान लेना कि नीति हर जन्म की संभावना बदलती है। वह सिर्फ तय करती है कि अगला जन्म होगा या नहीं।

बिना कोड का छोटा मानसिक चेक:

1 family expected: 1 boy, 1 girl
1000 families expected: 1000 boys, 1000 girls

---

७. दोस्त को समझाओ सार

अपोकैलिप्स नीति: लड़का होने तक बच्चे, फिर रुको।

१. हर परिवार ठीक एक लड़के पर खत्म। प्रति परिवार अपेक्षित लड़के = १। २. लड़कियाँ ज्यामितीय गिनती (पहले लड़के से पहले असफलताएँ)। निष्पक्ष जन्मों पर अपेक्षित लड़कियाँ = १। ३. अनंत श्रेणी: लड़कों का द्रव्यमान 1/2 + 1/4 + 1/8 + ... = 1। लड़कियों का द्रव्यमान भी १। ४. हर अकेला जन्म अभी भी ५०/५०। नियम सिर्फ कब रुकना है तय करता है, अगले का लिंग नहीं। ५. जावा: परिवारों का लूप, अंदर लड़के तक लूप, जोड़। असर्ट: लड़के == परिवार संख्या; बड़े न पर अंश ०.५ के पास।

अगर व्हाइटबोर्ड पर E[G] = sum k/2^{k+1} = 1 लिख सको और बता सको कि "ज़्यादा लड़कियाँ" वाला पेट का जवाब क्यों गिरता है, समस्या ६.७ तुम्हारी है। गणित अध्याय की ऊर्जा: अंतर्ज्ञान जाल है, अपेक्षा इलाज है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: ब्लू-आइड आइलैंड
• अगला: द एग ड्रॉप प्रॉब्लम