परिचित आणि अपरिचित व्यक्तींविषयीचे प्रमेय (Theorem on friends and strangers) हे गणितातील रॅम्झी सिद्धांताशी (Ramsey Theorem) संबंधित आहे. या प्रमेयाचे विधान (statement) पुढीलप्रमाणे : “कोणत्याही सहा व्यक्तींच्या समूहात किमान तीन व्यक्ती ह्या परस्परांच्या ओळखीच्या अथवा परस्परांना न ओळखणाऱ्या असतात”. उदा., एका समारंभाला काही माणसांना बोलवायचे आहे, परंतु या समारंभात ‘एकमेकांना ओळखणाऱ्या किमान तीन व्यक्ती असाव्यात अथवा एकमेकांना न ओळखणाऱ्या किमान तीन व्यक्ती असाव्यात’, तर किमान किती व्यक्तींना निमंत्रित करावे लागेल? हा प्रश्न परिचित आणि अपरिचित व्यक्तींविषयीच्या प्रमेयाच्या साहाय्याने सोडवता येतो.
परिचित आणि अपरिचित व्यक्तींविषयीचे प्रमेय आलेख सिद्धांतानुसार पुढीलप्रमाणे समजून घेता येईल. समजा सहा व्यक्ती ह्या सहा वेगवेगळ्या बिंदूंनी दर्शविल्या आहेत. ह्या सर्व व्यक्तींमधील संबंध पुढीलप्रमाणे दाखविता येईल : जर दोन व्यक्ती एकमेकांना ओळखणाऱ्या असतील, तर त्यांना दर्शवणारे बिंदू निळ्या रेषेने जोडले आणि जर त्यांची ओळख नसेल, तर ते बिंदू लाल रेषेने जोडले, तर ह्यामुळे सहा बिंदूंचा पूर्ण आलेख तयार होतो, ज्यामध्ये मधील प्रत्येक कडा लाल अथवा निळ्या रंगाची आहे.
आलेख सिद्धांतानुसार परिचित आणि अपरिचित व्यक्तींविषयीचे प्रमेय मांडण्याची पद्धत : सहा बिंदूच्या पूर्ण आलेखातील प्रत्येक कडा जर लाल अथवा निळ्या रंगाने रंगवली, तर सर्व भुजा एकाच रंगाच्या असणारा निदान एक त्रिकोण मिळतो. उदाहरणार्थ, आकृती 1 मध्ये △ACE हा सर्व कडा लाल असणारा त्रिकोण, म्हणजेच एकमेकांना न ओळखणाऱ्या तीन व्यक्तींचा त्रिकोण गट आहे, तर △BDF हा सर्व कडा निळ्या असणारा त्रिकोण, म्हणजेच एकमेकांना ओळखणाऱ्या तीन व्यक्तींचा त्रिकोण गट आहे.
प्रमेयाची सिद्धता : आलेखामधील प्रत्येक शिरोबिंदू हा उर्वरित पाच शिरोबिंदूंसोबत लाल अथवा निळ्या रेषेने जोडला गेला आहे. सहापैकी एका शिरोबिंदू A ला इतर पाच शिरोबिंदूंना जोडणाऱ्या पाच रंगीत कडा आहेत. कपोत गृहाच्या तत्‍त्वानुसार (Pigeonhole Principle) त्यातील कमीत कमी तीन कडा या एकाच रंगाच्या असायला हव्यात. जर A हा शिरोबिंदू C, D आणि E या शिरोबिंदूंना लाल कडांनी जोडला गेला आहे. म्हणजेच AC, AD आणि AE या लाल कडा आहेत. आता C, D आणि E हे शिरोबिंदूसुद्धा आपापसात लाल अथवा निळ्या कडांनी जोडलेले आहेत. जर CD, DE आणि EC यातील कुठलीही एक कडा लाल रंगाची असेल, तर सर्व भुजा लाल रंगांच्या असणारा त्रिकोण मिळतो आणि प्रमेय सिद्ध होते. उदा., आकृती 2 मध्ये CD ही कडा लाल रंगाची आहे व बाकीच्या निळ्या रंगाच्या आहेत. त्यामुळे इथे △ACDच्या सर्व भुजा लाल आहेत.
या उलट जर CD, DE आणि EC यांतील कुठलीही कडा लाल रंगाची नसेल, तर आपल्याला △CDE हा सर्व भुजा निळ्या रंगाच्या असणारा (पहा आकृती 3) त्रिकोण मिळतो, आणि प्रमेय सिद्ध होते.
आकृती 4 मध्ये सहा व्यक्तींमधील परिचितत्‍त्वाच्या आणि अपरिचितत्‍त्वाच्या सर्व अठ्ठ्याहत्तर शक्यता दर्शविलेल्या आहेत; प्रत्येक शक्यतेमध्ये सर्व भुजा लाल अथवा निळा असणारा त्रिकोण पाहायला मिळतो.
जर आलेखात सहापेक्षा कमी बिंदू असतील तर मात्र हे प्रमेय वैध ठरत नाही; याचा पडताळा थेट उदाहरणाने करता येतो. उदाहरणार्थ, आकृती 5 मध्ये पाच बिंदूंवरील पूर्ण आलेखाच्या कडा लाल आणि निळ्या रंगात रंगवल्या आहेत. मात्र ह्या उदाहरणात सर्व भुजा एकाच रंगाच्या असणारा त्रिकोण नाही. तीन आणि चार बिंदूवरील पूर्ण आलेखांकरितासुद्धा अशी उदाहरणे देता येतात. त्यामुळे परिचित आणि अपरिचित व्यक्तींविषयीचे प्रमेय वैध ठरण्याकरिता निदान सहा बिंदूंची आवश्यकता आहे.
संदर्भ :
- Brualdi, Richard A., Introductory Combinatorics, 5th ed., 2010.
- Harary, Frank, Graph Theory, 1972.
समीक्षक : रोहित होळकर
