Tuesday, July 25, 2006

केक बराबर-बराबर बाँटना

यदि आप ने अपना जन्मदिन मनाया अथवा किसी के जन्मदिवस के समारोह में गये हों तो निश्चित ही आपने केक काटा या खाया भी होगा। निश्चित ही आपको छोटा टुकड़ा ही मिला होगा। क्या करें सभी को अपना-अपना टुकड़ा छोटा लगता है ये मुरफ़ी मरफ़ी (धन्यवाद रवि जी) का नियम[१]है। और यदि आपने कभी अपने एक से ज्यादा बच्‍चों में कुछ चीज (जिसकी गिनती ना की जा सके) बाँटने की कोशिश की होगी तो एक ना एक बार तो आप पर ये भी आरोप लगाया गया होगा कि आप 'छोटे बेटे'/'बहन'/आदि को बाकी बच्‍चों से ज्यादा प्यार करतें है और उसे बड़ा टुकड़ा देते हैं। यदि आप सोने के तराजू से भी तोलकर बाँटे तो भी आरोप आपका साथ नही छोड़ते, क्योंकि किसी को बराबर मिलना अलग बात होती है जबकि किसी को बराबर मिलने की संतुष्टि होना अलग। क्या कोई ऐसा तरीका है जिससे सभी को अपने अपने टुकड़े से खुशी हो? जिससे हर कोई सोचे कि उसका टुकड़ा किसी और से टुकड़े से क्षणिक भी छोटा नही, हाँ शायद थोड़ा बड़ा ही है? जिससे बराबर भले ही ना मिले पर सभी को लगे कि उनको बेहतर हिस्सा मिला?

जी बिलकुल है। इसे गणित में उचित केक काटनें की समस्या कहतें है। समस्या का सार है कि किसी केक (या अन्य चीज) को - जो की हर दिशा से समान हो - कुछ लोगों - जिनकी केक के विभिन्न भागों के बारें मे पसंद अलग ना हो और जो सभी केक का बड़ा से बड़ा टुकड़ा चाहतें हो - में सफलतापूर्वक कैसे बाँटा जाये? आपके पास काटने के चाकू के सिवा कुछ नही है।

चलिये दो लोगो से शुरू करते है। क्या हल हो सकता है इसका? ये तो सरल है, 'मैं काटू तू चुन'। एक व्यक्ति अपने हिसाब से बराबर-बराबर भागों मे काटेगा और दूसरा अपने हिसाब से बड़ा टुकड़ा चुनेगा, बचा हुआ पहले व्यक्ति का हिस्सा। चूँकि दूसरे ने पहले चुना उसे शिकायत नही कि उसे छोटा मिला, और चूँकि पहले ने अपने हिसाब से बराबर ही काटे थे तो उसको शिकायत नही उसे छोटा मिला क्योंकि उसे तो कोई भी मिले वो अच्छा।

अब तीन लोगों का सोचते हैं। पर जैसा कि गणित में अधिकतर होता है, जैसे ही खेल के खिलाड़ियों की संख्या बढ़ती है, सर्वश्रेष्ठ हल की कठिनाई भी तीव्र गति से बढ़ती है। इसके हल को तो मुझे ढूढ़ना तो दूर समझने में ही काफ़ी समय लग गया। अगर आप ढूँढ लेते है तो अपने को जीनियस मान कर पीठ थपथपा लीजिये। मानिये तीन लोग अमर, अकबर और एन्थोनी है। तो सबसे पहले अमर केक को अपने अनुसार तीन बराबर के टुकड़ों में काटेगा। अब अकबर उन तीन टुकड़ों को बड़े से छोटे क्रम में बाँटेगा। यदि पहले स्थान के लिये दो टुकड़े बिलकुल बराबर हैं अकबर की दृष्टि में तो वो कुछ नही करेगा (इससे फर्क नही पड़ता की तीसरा भी बराबर है या दोनो से छोटा है)। इसे स्थिती १ मान लें। और यदि ऐसा नही है तो अकबर सबसे बड़े (उसकी नज़र में) टुकड़े को काट कर उसे दूसरे स्थान पर आने वाले टुकड़े के बराबर कर देगा। कटे हुये केक के टुकड़े (इसे आगे से 'कतरन' कहा जायेगा) को अलग रख दिया जायेगा। इसे स्थिती २ मान लें। अब तीन टुकड़ों मे से एन्थोनी अपने हिसाब से सबसे बड़ा टुकड़ा चुन लेगा।

यदि हम स्थिती १ में है तो इसके बाद अकबर बाकी दोनो में से अपने लिये बड़ा टुकड़ा चुन लेगा, और अमर बचा हुआ टुकड़ा। चूँकी एन्थोनी ने सबसे पहले चुना है उसको कोई शिकायत नही होनी चाहिये। क्योंकि अकबर के अनुसार दो टुकड़े बराबर थे (तभी तो हम स्थिती १ में है, नही होते तो अकबर टुकड़े की कतरन काट लेता और मामला दूसरा होता) इसलिये यदि एन्थोनी ने सबसे बड़ा ले भी लिया तो भी उसके लिये भी सबसे बड़ा बचा है और वो उसे ले सकता है। और जब अमर ने अपने अनुसार सब बराबर ही काटे थे तो फिर उसको क्या चिंता बाकी दोनो क्या लें, उसका टुकड़ा निश्चित ही किसी से कम नही।

यदि हम स्थिती २ में है और हम अकबर द्वारा काट के अलग रखी गयी कतरन को भूल जायें तो पुनः स्थिती १ जैसी अवस्था हो जाती है क्योंकि अभी भी दो टुकड़े अकबर को बराबर लगते हैं। इनका बँटवारा भी वैसे ही हो सकता है: एन्थोनी पहले चुनेगा, तद्पश्चात अकबर और फिर अमर। एक छोटी सी बात है पर। यदि एन्थोनी ने उस टुकड़े को लिया जिसे अकबर ने काटा था और कतरन निकाली थी, तो अकबर बचे हुये टुकड़ों मे से बड़ा वाला चुन सकता है और अमर अंतिम टुकड़ा। पर यदि एन्थोनी ने कोई और टुकड़ा लिया (बिना कटे दो में से) तो अकबर को उसके द्वारा काटा गया ही लेना होगा। ऐसा करने पर हम उसके साथ अन्याय नही कर रहे क्योंकि कतरन निकालने के बाद वो टुकड़ा सबसे बड़ा टुकड़ा बन चुका है अकबर के अनुसार। हम उसे उसके अनुसार बड़ा ही दे रहे हैं। अंत मे अमर बचा टुकड़ा ले लेगा। हमे अकबर को कटा हुआ टुकड़ा देना पड़ेगा क्योंकि वो टुकड़ा उसकी नज़र मे सबसे बड़ा है जबकि अगर अकबर कटा टुकड़ा नही लेता तो अमर के लिये वो टुकड़ा बचेगा जिससे अमर निश्चित ही संतुष्ट नही होगा (क्योंकि उसने तो सब बराबर काटे थे, अकबर ने कतरन निकाली तो फिर वो तो अमर की दृष्टि में छोटा हो गया ना)। इस प्रक्रिया में चूँकि हमारा बँटवार स्थिती १ के अनुसार ही हुआ तो सभी संतुष्ट होने चाहिये और सभी को लगना चाहिये कि उसका टुकड़ा किसी छोटा नही।

लेकिन अभी वो कतरन तो बची हुई है। उसे भी तो बाँटना है। उसके लिये अकबर और एन्थोनी मे से किसी एक को उस कतरन के तीन बराबर-बराबर टुकड़े करने होंगे। फिर अकबर और एन्थोनी में से जिस ने टुकड़े नही किये अभी वो पहला टुकड़ा (कतरन का टुकड़ा) चुनेगा, और जिस ने टुकड़े करे वो दूसरा। अमर बचा हुआ कतरन का टुकड़ा लेगा। क्योंकि अकबर और एन्थोनी मे से जिसने टुकड़े करे उसके लिये तो सभी बरबर है, और जिसने पहले चुना उसको भी कोई शिकायत नही। पर चूँकि अमर ने शुरू मे तीन बराबर टुकड़े किये थे, कोई भी कतरन जो अकबर ने काटी अगर वो अमर को ना भी मिले तो उसे आपत्ति नही होनी चाहिये (यही कारण है कि स्थिती २ में अगर एन्थोनी अकबर द्वारा कतरा टुकड़ा नही लेता तो वो अकबर को ही लेना पड़ता क्योंकि अमर वो नही चाहेगा)। इसलिये यदि अमर को कतरन के तीन छोटे टुकड़ों मे से सबसे छोटा भी मिले तो भी वो खुश क्योंकि उसे जितना मिला उतना भला।

हम्फ!! तीन लोगो के साथ ये हाल हो गया समस्या सुलझाने मे तो चार या ज्यादा से क्या होगा? हांलाकि हल का तरीका लगभग वही रहेगा: पहला चार टुकड़े करे, फिर दूसरा दो की कतरन काट कर तीन बराबर बना दे, फिर तीसरा एक की कतरन काटकर दो बराबर बना दे और अंत मे चौथा अपना टुकड़ा चुने और बाकी विपरित क्रम मे चुने, इत्यादि...। अधिक जानकारी के लिये विकीपीडिया, ये पन्ना और गूगल खोज देखें।

सारी कहानी का सार? केक छोटा मिले तो चुपचाप खा लें, बड़े-बड़े के चक्कर में बहुत अक्कल खर्च होती है। और हाँ, बच्‍चे एक या दो बस :)

[जिन्हें बाल की खाल निकालनी हो उनके लिये: यदि पहला व्यक्ति, या हल की प्रक्रिया में कोई भी व्यक्ति, बराबर-बराबर हिस्सें करने की बजाय गलती से छोटा-बड़ा काट देता है तो हम इस समस्या को अलग हिस्सों के लिये अलग से हल कर सकतें हैं। अर्थात एक केक की बजाय तीन छोटे केक बाँटेंगे इसी तरह से।]

अंत मे इस प्रविष्टिं के पाठको से एक प्रश्न: क्या आपको मेरी लेखन शैली भाषणबाजी (patronizing) प्रतीत होती है? कुछ लोग कहतें है कि मैं ऐसा लिखता हूँ, और यदि ऐसा है तो मैं निश्चित ही सुधारना चाहता हूँ।

----------
↑[१] मुरफ़ी मरफ़ी के नियमानुसार: जब कोई काम गड़बड़ हो सकता है तो वो गड़बड़ हो के ही रहेगा।

Book Review - Music of the Primes by Marcus du Sautoy (2003)

I can say, with some modesty, that I am familiar with the subject of mathematics more than an average person is. Despite that I hadn’t ever ...