Skip to main content

केक कापायच्या विविध पद्धती

लेखक चिरोटा यांनी मंगळवार, 22/09/2009 00:11 या दिवशी प्रकाशित केले.

समजा एक केक दोन व्यक्तींमध्ये-अ आणि ब मध्ये समान वाटायचा आहे तर कसा वाटता येईल?
नेहमी वापरली जाणारी पद्धत-
१)तिसर्‍या व्यक्तीने(समजा क ने) एक छेद देवून केकचे दोन भाग करणे.
२)अ(किंवा ब ने ) ने प्रथम त्याच्या आवडीचा तुकडा उचलणे.
३)ब(किंवा अ ने) ने दुसरा तुकडा उचलणे.
वरील पद्धत fair(न्याय्य) म्हणता येईल का? क च्या द्रुष्टिकोनातून अर्थातच ती आहे पण अ किंवा ब च्या नजरेतून ती असेलच असे नाही.म्हणजे ब ला ही विभागणी ७०%-३०% ही वाटु शकेल व तो ही विभागणी अन्याय्य म्हणेल. म्हणजे इकडे समान वाटणी ही सापेक्ष आहे.
दुसरी पद्धत जी आपण नेहमी वापरतो-
१) अ ने छेद देवून केकचे दोन भाग करणे.
२)ब ने त्याच्या पसंतीचा तुकडा निवडणे.
३)अ ने दुसरा तुकडा घेणे.
अ च्या नजरेतून दोन्ही भाग ५०% आहेत.म्हणून त्याची कुठ्च्याही तुकड्यास पसंती असेल. ब ने प्रथम निवड केल्याने तो ही त्याच्या आवडीचा तुकडा(म्हणजे कमीत कमी ५०%) निवडू शकेल. दोघांच्याही नजरेतून विभागणी न्याय्य असल्याने ही विभागणीला(cut and choose) fair division म्हणतात.

१९४०च्या दशकात स्टीनहॉस्,बनाक्,नॅस्टर ह्या पोलिश गणितींनी न्याय्य विभागणीचा(simple fair division) हा प्रश्न वॉशिंग्टनमध्ये गणित आणि सामाजिक विज्ञान परिषदेत मांडला आणि तो सोडवण्यासाठी काही प्रणाली(algorithms) सुचवल्या. वरील पद्धतीत केवळ दोन व्यक्ती आहेत आणि विभागणी ५०% आहे. गणिताच्या द्रुष्टिकोनातून काही challenging प्रश्न तयार होतात.
१)केक तीन (किंवा अधिक व्यक्तींमध्ये) समान वाटायचा असेल तर कसा वाटायचा?
२)केक दोन किंवा अधिक व्यक्तींमध्ये वेगवेगळ्या प्रमाणात वाटायचा आहे.उ.दा.केक अ आणि ब मध्ये ८:५ ह्या गुणोत्तरात वाटायचा आहे.
३)कमीत कमी छेद देवून केक अनेक व्यक्तींमध्ये सर्वसमान कसा वाटायचा?

पहिल्या प्रश्नाचे उत्तर सोपे नसले तरी स्टीनहॉसनी सुचवलेली प्रणाली समजायला सोपी आहे. समजायला सोपे आणि गणिताची कमीत कमी पार्श्वभूमी लागणारे हे cake cutting problems गेल्या काही वर्षात गणिती वर्तुळांत लोकप्रिय झाले.
सध्या पहिल्या प्रश्नावर विचार करा आणि काही सुचते का सांगा.
भेंडी

वाचने 5913
प्रतिक्रिया 18

प्रतिक्रिया

श्रावण मोडक मंगळवार, 22/09/2009 00:31

आमच्या अ-गणिती डोक्यात आलेले काही मुद्दे (फक्त विचारार्थ):

  1. इतका डोक्याला खुराक असेल तर आपण तर तो केक फक्त आपलाच खुराक आहे असे समजून वागू!!! एरवी, "ए, केलेत हे तुकडे. हवं तर खा नाही तर चपला घालून चालू पड..." :)
  2. माणसांबाबतच असले प्रश्न येत असतील. प्राणीच फक्त एकमेकांना ओरबाडत अन्नही ओरबाडून घेत असावेत.
  3. पहिल्या उदाहरणात एका व्यक्तीने केक कापताना मोजपट्टी वापरली होती का? नसेल तर, तिथं फेअरनेस वगैरे हे केवळ काल्पनिक आहे. त्यामुळं पुढचे सिद्धांत वगैरे गारद होतात.
  4. एवीतेवी, गणिताची कमीतकमी पार्श्वभूमीच ना? मग होऊ द्या की थोडं - ए, तू मोठा तुकडा घेतलास, मलाच का छोटा? (या कमीतकमी पार्श्वभूमीवर, "चवीपुरतं मीठ", "हिंगाची चिमूट", "मूठभर..." हेच अंतिम सत्य असतं. कल्पना नव्हे).

...
म्हणजेच मुद्देही मोजता येणार नाहीत.
हे हलकेच घ्यावे. बाकी गणिती खेळ्या चालू द्या... गणिताशी दुश्मनी करण्याचा अजिबात इरादा नाहीये.

धनंजय मंगळवार, 22/09/2009 02:55

हे एक बर्‍यापैकी कठिण गणित आहे, असे ऐकून मी सोडून दिले होते. जमल्यास इथे उलगडा जरूर द्यावा.

(आताच विकीपेडियावर पद्धत वाचली. मोठी कल्पक पद्धत आहे.)

पाषाणभेद मंगळवार, 22/09/2009 03:17

१)केक कापतांना जवळ वजन काटा पण आहे का?
२)केक कापल्या नंतर तो वजन करून वाटप करायचे याला दोघांची मान्यता आहे काय?
३) केक काही मिली ग्रॅमध्ये सुरी, केकचा बॉक्स, वजनकाटा याला लागू शकतो. (तेही विस्कळीत (अनईव्हन) स्वरूपात). हे त्या दोघांनाही चालेल काय?
४) असे (३) चालत असल्यास तंतोतंत वाटपाचाच आग्रह का? हा झाला अगणिती प्रश्न.

मला कुत्रा. कोल्हा व सिंह या तिघांच्या शिकारीची गोष्ट आठवली. कालच मी ती ९ वी च्या सहामाईसाठी प्रश्नपत्रीकेत टाकलेली आहे. कुणाला ऐकायची (म्हणजे) वाचायची असेल तर सांगा.
(तशी पद्धत या दोघांना चालेल काय?)
-----------------------------------
आणि हो, सांगायच राहूनच गेलं, या विधानसभेच्या ईलेक्शनदरम्यान मी नविन कार घेणार आहे.

- पाषाणभेद उर्फ दगडफोडीची सजा मिळालेला दगडफोड्या

सुनील मंगळवार, 22/09/2009 09:47

निव्वळ गणितीय दृष्टीकोनातून पाहिले तर, कोणत्याही गोष्टीचे तीन एकसमान भाग करणे शक्य नाही. कारण १/३=०.३३३३३३३३३३३३३३३३३३३३३३३३३३३३३३३३...........

बाकी गणित आणि सामाजिक विज्ञान परिषद ही काय आहे ते कळले नाही. सामाजिक न्यायाचाच विचार केला तर, वाटणी करणार्‍याने सर्वात शेवटी उरलेला भाग उचलावा, हेच योग्य!

(केकच्या प्रतीक्षेत) सुनील

Doing what you like is freedom. Liking what you do is happiness.

विजुभाऊ मंगळवार, 22/09/2009 10:00

निव्वळ गणितीय दृष्टीकोनातून पाहिले तर, कोणत्याही गोष्टीचे तीन एकसमान भाग करणे शक्य नाही.
असहमत....
ज्या गोष्टीना तीन ने निखळ भाग जातो त्या सर्व गोष्टीना तीन च्या पटीतल्या संख्या असे म्हणतात. त्या सर्व संख्यांचे तीन भाग करता येतात.
१/३ = ०.३३३३३३३३३......
हे केकच्या बाबतीत बरोबर असून शकेल. कापताना खाली पडणारा चुरा तुम्ही गृहीत धरला नाहिय्ये

पाषाणभेद मंगळवार, 22/09/2009 10:06

तेच म्हणतो. वरील क्र. ३ चे ऑप्शन पहा. पण ते गणितीय विचार करत असल्याने त्यांच्या मनात काहितरी वेगळे असेल ते समजल्याशिवात उत्तर देणे अवघड आहे.
-----------------------------------
आणि हो, सांगायच राहूनच गेलं, या विधानसभेच्या ईलेक्शनदरम्यान मी नविन कार घेणार आहे.

- पाषाणभेद उर्फ दगडफोडीची सजा मिळालेला दगडफोड्या

चिरोटा मंगळवार, 22/09/2009 19:46

हा प्रश्न सोडवताना काही गोष्टी ग्रुहित धरल्या आहेत-
१)केक एकजिनसी असेलच नाही. वजन काटा,फुट पट्टी,वर्नियर कॅलिपर वापरुन नक्कीच समान भाग करता येतील. पण त्यासाठी केक एक्जिनसी(homogenous) हवा.
२)वर म्हंटल्याप्रमाणे 'समान वाटणी' ही सापेक्ष आहे.क ने समजा तीन समान भाग केले तर ते अ किंवा ब ला मंजूर होतीलच असे नाही.ब ला ती विभागणी ८०%-५%-१५% वाटेल तर अ ला ४०%-१०%-५०% वाटेल.
भेंडी
क्ष्^न + य्^न = झ्^न

कानडाऊ योगेशु मंगळवार, 22/09/2009 10:55

ह्यावरुन एक विनोद आठवला.
जॉनी आईने दिलेल्या एका केकचे दोन तुकडे करतो.मोठा स्वतःसाठी ठेवतो आणि छोटा त्याच्या भावाला देतो. हे पाहुन त्याचा भाऊ जॉनीला म्हणतो कि जर मी त्या केकचे तुकडे केले असते तर मोठा तुला दिला असता आणि छोटा मी घेतला असता.
जॉनी उत्तरतो म्हणुनच तर तुला छोटा तुकडा दिलाय ना!

परिकथेतील राजकुमार मंगळवार, 22/09/2009 13:56

पण मी म्हणतो ३ माणसात १ केक, हे कसले भिकार चाळे ? श्या !!!

उद्या ४ जणांच्यात एक निप प्याल लेको.

असो तो केक कोणी कसा का खाईना, आपले पोट थोडेच भरणार आहे ?

लष्कराच्या भाकर्‍या न भाजणारा
©º°¨¨°º© परा ©º°¨¨°º©
आमचे राज्य

मितालि मंगळवार, 22/09/2009 15:18

गोष्टीतील माकडाने जसा दोन मांजराना केक वाटुन दिला होता ना... अगदी तसेच करायचे.. मग कितीहि जणाना वाटुन द्या केक स्वतःलाच मिळेल :))

सचीन जी मंगळवार, 22/09/2009 16:01

च्या मारी !
या मिपाकरांचे काही खरे नाही!
एका चांगल्या शास्त्रीय कोड्यावर डोके चालवायची कोणाचीच ईच्छा दिसत नाही!
सगळे आपले पी जे मारण्यात दंग!

चिरोटा मंगळवार, 22/09/2009 18:59

हे एक बर्‍यापैकी कठिण गणित आहे, असे ऐकून मी सोडून दिले होते. जमल्यास इथे उलगडा जरूर द्यावा.

Envy free प्रणाली वेगळ्या आहेत्.सध्या simple fair division चाच विचार करु. म्हणजे प्रत्येकजण केवळ स्वतःला १/३ केक मिळाला आहे की नाही एवढाच विचार करेल.
Trimming method-
१)अ प्रथम १/३ तुकडा कापेल.
२)अ हा तुकडा ब ला दिला जाईल. जर ब ला हा तुकडा १/३ पेक्षा मोठा वाटला तर तो trim करेल. आणि तो तुकडा क ला देईल.
३)जर क ला हा तुकडा १/३ पेक्षा मोठा वाटला तर तो ही तुकडा trim करेल आणि स्वीकारेल. जर नाही वाटला तर तुकडा ब ला घ्यावा लागेल.
4) अ आणि (ब किंवा क) उरलेल्या केकवर cut and choose method वापरतील.
समजा, p1,p2..pn व्यक्ती आहेत तर वरील वरील पद्धत generalize करता येते-
१)Player p1 cuts the piece of size 1/n from cake.
2)Cut piece is passed successively to p2...p(n-1).Any player who thinks that piece exceeds 1/n th value trims it so that reduced value is exactly 1/n.
3)Player Pn takes the trimmed piece if Pn considers it atleast 1/n th of the cake.Otherwise trimmed piece is given to last player who trimmed it.The player receiving this piece drops out.
4)repeat steps 1,2,3 for remaining players.
(कचर्‍याचा(crumbs) चा विचार सध्या नाही करायचा. simple fair division मध्ये प्रत्येकाला त्याच्या नजरेतून 1/n th केक मिळाला की नाही एवढेच बघायचे आहे)
या शिवाय आणखी काही पद्धती आहेत.त्या नंतर बघु.
भेंडी.

क्ष्^न + य्^न = झ्^न

पक्या बुधवार, 23/09/2009 01:06

केकचा आकार काय आहे? केक गोलच आहे असे का गृहित धरले आहे?
केक आयताकृती किंवा अजुन वेगळ्या आकारात पण मिळतो.

चिरोटा बुधवार, 23/09/2009 10:05

कुठलाही आकार ग्रुहित धरायचा नाही.केक म्हणजे फक्त समर्याद वस्तु(finite object) एवढेच ग्रुहित धरायचे आहे.
भेंडी
क्ष्^न + य्^न = झ्^न