बास्केटबॉल: एक शॉट बनाम तीन में से दो (प्रायिकता)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.२: पाने की प्रायिकता पी पर खेल १ (एक सफल) या खेल २ (तीन में कम से कम दो) चुनो। बीजगणित: पी बनाम ३पी²(१-पी)+पी³, और कब कौन जीते।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम रिंग के नीचे खड़े हो। कोई दो मेले वाले खेल पेश करता है। खेल १: एक ही शॉट; घुस गया तो जीत। खेल २: तीन शॉट; कम से कम दो घुसें तो जीत। हर बार एक ही खिलाड़ी। हर कोशिश पर घुसने की वही प्रायिकता p। शॉट स्वतंत्र। कौन सा खेल लोगे?

अंतर्ज्ञान उलझाता है। अगर हाथ ठंडा है, एक ही मौका दो सफलताओं से ज़्यादा सुरक्षित लग सकता है। अगर हाथ गरम है, दो की शर्त वाले तीन प्रयास एक ही जीवन-मरण वाले शॉट से सुरक्षित लग सकते हैं। इंटरव्यू चाहता है वह बीजगणित जो इस एहसास को p के साफ नियम में बदल दे।

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

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

पार्क में फ्री थ्रो सोचो।

खेल १ "मनी बॉल" है: एक प्रयास। घुस गया, इनाम तुम्हारा। जीत की प्रायिकता बस इतनी है कि तुम आमतौर पर कितनी बार घुसाते हो: p।
खेल २ छोटी सीरीज़ है: तीन प्रयास, दो या ज़्यादा सफल चाहिए। पहले दो चूके तो तीसरा नहीं बचाता। पहले दो घुस गए तो तीसरा चूक भी सकते हो।

अगर निशाना बहुत खराब है (p शून्य के पास), दो सफलियाँ ज़रूरी होना सख्त है। एक भाग्यशाली अकेला शॉट बेहतर दांव है। अगर निशाना बहुत अच्छा है (p एक के पास), दो बार चूकना दुर्लभ है, इसलिए खेल २ तुम्हारे पक्ष में है। बीच में कहीं दोनों खेल बराबर होते हैं। वही बिंदु हम हल करते हैं।

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

दिया:

हर शॉट स्वतंत्र रूप से प्रायिकता p से घुसता है, 0 <= p <= 1।
खेल १: १ में से १ सफल पर जीत।
खेल २: ३ में से कम से कम २ सफल पर जीत।

खोजो:

हर खेल जीतने की प्रायिकता p के फलन के रूप में।
किन p पर खेल १ चुनो, खेल २ चुनो, या दोनों बराबर।

ज़ोर से कहने वाले अनुमान:

शॉट स्वतंत्र एक जैसे बर्नुली प्रयोग हैं, सफलता p।
खेल २ में क्रम मायने नहीं; सिर्फ सफलियों की गिनती।
"पसंद" का मतलब जीत की ऊँची प्रायिकता (अपेक्षित मज़ा या और कोई उपयोगिता नहीं)।

अगर कोड माँगें तो सिग्नेचर का आकार:

// positive: prefer game1; negative: prefer game2; zero: equal
int compareGames(double p)

double probGame1(double p)
double probGame2(double p)

बीजगणित से पहले स्पष्ट करो:

क्या p ज्ञात है, या p के अंतराल छोड़ते हैं? (p के अंतराल।)
क्या शॉट स्वतंत्र हैं? (हाँ, क्लासिक कथन।)
ठीक दो, या कम से कम दो? (कम से कम दो: एमएमएफ, एमएफएम, एफएमएम और एमएमएम।)
p = 0 और p = 1? (दोनों खेल समान: कभी नहीं जीतते, या हमेशा जीतते।)

३. पहले सोचो

खेल १ की जीत प्रायिकता

एक शॉट। एक सफलता।

P(Game1) = p

फैलाने को कुछ नहीं।

खेल २ की जीत प्रायिकता

तीन स्वतंत्र शॉट। ठीक २ सफल या ठीक ३ सफल पर जीत।

द्विपद गुणांक:

ठीक २ सफल: C(3, 2) = 3 क्रम: एमएमएफ, एमएफएम, एफएमएम। प्रत्येक की प्रायिकता p^2 (1-p)।
ठीक ३ सफल: C(3, 3) = 1 क्रम: एमएमएम। प्रायिकता p^3।

P(Game2) = 3 * p^2 * (1 - p) + p^3
         = 3p^2 - 3p^3 + p^3
         = 3p^2 - 2p^3

यह भी लिख सकते हो: "१ घटा पी(० सफल) घटा पी(१ सफल)":

P(0) = (1-p)^3
P(1) = 3 p (1-p)^2
P(Game2) = 1 - (1-p)^3 - 3p(1-p)^2

फैलाने पर वही बहुपद। p से तुलना के लिए "ठीक २ प्लस ठीक ३" छोटा है।

तुलना से पहले समझदारी जाँच

`p`	खेल१	खेल२	टिप्पणी
०	०	०	दोनों असंभव
०.५	०.५	`3(0.25)-2(0.125)=0.5`	बराबर
१	१	१	दोनों निश्चित
०.२५	०.२५	`3(0.0625)-2(0.015625)=0.15625`	खेल१ बेहतर
०.७५	०.७५	`3(0.5625)-2(0.421875)=0.84375`	खेल२ बेहतर

अगर बंद रूप इन पाँच बिंदुओं पर फेल हो, असमानता से पहले सूत्र सुधारो।

४. बीजगणित: कब खेल १ बेहतर?

खेल १ तब पसंद जब P(Game1) > P(Game2):

p > 3p^2 - 2p^3
p - 3p^2 + 2p^3 > 0
p (1 - 3p + 2p^2) > 0
p (2p^2 - 3p + 1) > 0

द्विघात का गुणनखंड:

2p^2 - 3p + 1 = (2p - 1)(p - 1)

जाँच: (2p - 1)(p - 1) = 2p^2 - 2p - p + 1 = 2p^2 - 3p + 1। सही।

तो:

p (2p - 1)(p - 1) > 0

(0, 1) पर f(p) = p(2p-1)(p-1) का चिह्न चार्ट:

महत्त्वपूर्ण बिंदु: p = 0, p = 1/2, p = 1।
(0, 1/2) पर: p > 0, (2p-1) < 0, (p-1) < 0 → धनात्मक × ऋणात्मक × ऋणात्मक = धनात्मक → खेल१ बेहतर।
(1/2, 1) पर: p > 0, (2p-1) > 0, (p-1) < 0 → धनात्मक × धनात्मक × ऋणात्मक = ऋणात्मक → खेल२ बेहतर।
p = 1/2 पर: f = 0 → बराबर।
सिरों 0 और 1 पर: जीत प्रायिकता समान (दोनों ०, या दोनों १)।

जवाब (यह आकार याद रखो)

`p` का अंतराल	पसंद
`0 < p < 1/2`	खेल १ (एक शॉट)
`p = 0`, `p = 1/2`, या `p = 1`	बराबर
`1/2 < p < 1`	खेल २ (कम से कम २ में से ३)

शब्दों में: अगर आधे से कम शॉट घुसते हैं, अकेला शॉट लो। अगर आधे से ज़्यादा घुसते हैं, तीन वाला खेल लो। ठीक आधे पर (या तुच्छ सिरों पर) फर्क नहीं।

पार्क वाली समझ से मेल खाता है। कमज़ोर निशानेबाज दो सफलियों से डरते हैं। मजबूत निशानेबाज तीन प्रयासों को सुरक्षा जाल बनाते हैं।

५. जावा मददगार (गणना और तुलना)

शुद्ध व्हाइटबोर्ड गणित में कोड ज़रूरी नहीं, पर छोटा मददगार वक्र जाँचने लायक बनाता है।

public final class BasketballGames {

    /** P(win Game 1) = p. */
    public static double probGame1(double p) {
        return p;
    }

    /**
     * P(win Game 2) = C(3,2) p^2 (1-p) + C(3,3) p^3
     *               = 3p^2(1-p) + p^3
     *               = 3p^2 - 2p^3
     */
    public static double probGame2(double p) {
        return 3 * p * p * (1 - p) + p * p * p;
    }

    /**
     * +1 prefer Game1, -1 prefer Game2, 0 equal (within epsilon).
     */
    public static int compareGames(double p) {
        if (p < 0.0 || p > 1.0) {
            throw new IllegalArgumentException("p must be in [0, 1], got " + p);
        }
        double d = probGame1(p) - probGame2(p);
        final double eps = 1e-12;
        if (Math.abs(d) <= eps) {
            return 0;
        }
        return d > 0 ? 1 : -1;
    }

    /** Closed-form preference without floating noise near known roots. */
    public static String preferClosedForm(double p) {
        if (p < 0.0 || p > 1.0) {
            throw new IllegalArgumentException("p must be in [0, 1]");
        }
        if (p == 0.0 || p == 0.5 || p == 1.0) {
            return "indifferent";
        }
        return p < 0.5 ? "game1" : "game2";
    }
}

वैकल्पिक: अंतराल स्कैन करो और बदलाव छापो

public static void main(String[] args) {
    for (int i = 0; i <= 20; i++) {
        double p = i / 20.0;
        double g1 = BasketballGames.probGame1(p);
        double g2 = BasketballGames.probGame2(p);
        String who = BasketballGames.preferClosedForm(p);
        System.out.printf("p=%.2f  g1=%.5f  g2=%.5f  -> %s%n", p, g1, g2, who);
    }
    // p=0.00 ... indifferent
    // p=0.25 ... game1
    // p=0.50 ... indifferent
    // p=0.75 ... game2
    // p=1.00 ... indifferent
}

0.5 के पास फ्लोटिंग तुलना हिल सकती है; इंटरव्यू में बंद रूप p ? 1/2 बोलो। संख्यात्मक मददगार जाँच के लिए, अकेले स्कैन से सीमा खोजने के लिए नहीं।

६. संख्याएँ और एक आम गलत मोड़

मामला क: ठंडा निशाना, `p = 0.2`

P1 = 0.2
P2 = 3*(0.04)*(0.8) + 0.008 = 0.096 + 0.008 = 0.104

खेल १ जीतता है (0.2 > 0.104)। बीस प्रतिशत पर दो सफलियाँ कठिन हैं।

मामला ख: आधा-आधा, `p = 0.5`

P1 = 0.5
P2 = 3*(0.25)*(0.5) + 0.125 = 0.375 + 0.125 = 0.5

बराबर। बीजगणित की अच्छी जाँच।

मामला ग: गरम निशाना, `p = 0.8`

P1 = 0.8
P2 = 3*(0.64)*(0.2) + 0.512 = 0.384 + 0.512 = 0.896

खेल २ जीतता है। तीन में दो बार चूकना कम संभावित है।

लोग जो गलतियाँ करते हैं

१. सिर्फ ठीक दो सफलियाँ गिनना और तीन भूलना: खेल २ को p^3 से कम आँकना। २. खेल २ को "लगातार दो" समझना, किसी भी दो में से तीन नहीं: अलग घटना। ३. अपेक्षित सफलियों की संख्या की तुलना, जीत की प्रायिकता की नहीं: खेल १ में अपेक्षित p, खेल २ में 3p। अलग सवाल। मायने जीत का नियम रखता है। ४. बिना पूछे आश्रित शॉट मानना (थकान, दबाव)। स्वतंत्रता कहो जब तक इंटरव्यूअर और न जोड़े। ५. p = 3p^2 - 2p^3 हल करके रुक जाना बिना चिह्न चार्ट। सिर्फ मूल नहीं बताते कि किस तरफ़ कौन सा खेल।

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

विषय	जवाब
मॉडल	स्वतंत्र बर्नुली शॉट, सफलता `p`
पी(खेल१)	`p`
पी(खेल२)	`3p^2(1-p) + p^3 = 3p^2 - 2p^3`
खेल१ चुनो	`0 < p < 1/2`
खेल२ चुनो	`1/2 < p < 1`
बराबर	`p ∈ {0, 1/2, 1}`
समय (बंद रूप)	ओ(१) अंकगणित
अतिरिक्त जगह	ओ(१)

कैसे बोलो (४५ सेकंड वाला संस्करण):

१. खेल १ बस p है। २. खेल २ द्विपद: ठीक दो की तीन राहें, तीन की एक: 3p^2(1-p)+p^3। ३. p > 3p^2-2p^3 लगाओ, p(2p-1)(p-1) > 0 गुणनखंड करो। ४. (0,1) पर यह p < 1/2 के लिए सत्य। ५. सिरे और p = 1/2 बराबरी के रूप में जाँचो।

आगे के सवाल:

"एक शॉट बनाम n में से k" तक सामान्यीकरण: वही विचार, गंदे बहुपद।
अगर चूक के बाद प्रायिकता बदले? स्वतंत्रता मरती है; केसों का पेड़ चाहिए।
जोखिम: अगर इनाम बहुत बड़ा और तुम जोखिम-प्रेमी हो, उपयोगिता पी(जीत) न हो। क्लासिक सीटीसीआई जवाब पी(जीत) पर रहता है।

सीरीज़ के पड़ोसी:

इससे पहले वाली पहेली: भारी गोली।
अगली टाइलिंग / रंग शैली: डोमिनो।

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

बास्केटबॉल (समस्या ६.२) प्रायिकताओं की तुलना है, कोड की रगड़ नहीं।

१. खेल १ की जीत संभावना p है। २. खेल २: तीन स्वतंत्र शॉट में कम से कम दो: 3p^2(1-p) + p^3। ३. सरल रूप 3p^2 - 2p^3। ४. खेल १ तब जब p > 3p^2 - 2p^3, जो p(2p-1)(p-1) > 0 बनता है। ५. शून्य और एक के बीच, मूलों के बाहर: p < 1/2 हो तो एक शॉट, p > 1/2 हो तो दो-में-से-तीन। 0, 1/2 और 1 पर खेल बराबर।

अगर दोनों प्रायिकताएँ लिख सको, असमानता गुणनखंड कर सको, और आधे पर बदलाव बिना देखे नाम ले सको, तो समस्या ६.२ तुम्हारी है।