পায়রার বাক্সে স্থান-সঙ্কুলান সমস্যা

নীলাব্জ চ্যাটার্জি

(University of Oslo)

 

13 Feb 2017

Link: https://bigyan.org.in/pigeonhole

স্কুলপাঠ্য বিজ্ঞান বিষয়গুলির মধ্যে যেমন ছাত্র ছাত্রীদের কাছে সাধারণতঃ সবচেয়ে ভয়ের বিষয়, সবচেয়ে কঠিন বিষয় গণিত, তেমনই নিন্দুকদের পক্ষ থেকে গণিতের গবেষককে করে থাকা একটি তীর্যক প্রশ্ন হলো, ¨এই যে আপনার গবেষণা, এটা বাস্তব জীবনে কী উপকারটা করবে?¨ আজ গণিতেরই এমন এক ‘ফলাফল’ (result)-এর উল্লেখ করবো যা একদিকে অবশ্যই বাস্তব জীবনের কথা মাথায় রাখে, কিন্তু অন্য দিকে শুধু সারল্য ও সৌন্দর্যের জন্য যে কোনো ছাত্র-ছাত্রীর গণিতের প্রতি আগ্রহ বাড়িয়ে তুলতে পারে।

ফলাফল-টাতে যাওয়ার আগে একটা অতি পরিচিত দৃশ্যে চোখ বোলানো যাক। মধ্য কলিকাতা, অনেক সাবেকি বাড়ি এখনো টিকে আছে। বাড়িগুলোর ঘুলঘুলিতে পায়রার বাসা। ধরা যাক : কার্নিশের গা ঘেঁষে ৭ টা পায়রার খোপ রয়েছে। অথচ ওই খোপগুলোতে বসবাসকারী পায়রা পরিবারের সদস্য সংখ্যা ৮। তা হলে আধুনিক শহুরে নাগরিক জীবনের মতোই একটু স্থান-সঙ্কুলান সমস্যা দেখা দেবে না কী? হ্যাঁ, অবশ্যই দেবে। যদি না কোনো পায়রা গৃহত্যাগ করে। মোদ্দা কথা হলো: পরিস্থিতির চাপে অন্ততঃ এরকম একটা খোপ থাকবেই যেখানে কমপক্ষে দুটি পায়রা থাকবে। আর সহজ সরল এই পর্যবেক্ষণ থেকেই জন্ম নেয় ‘পিজিয়ন-হোল প্রিন্সিপল’ (Pigeonhole Principle)।

আরেকটা উদাহরণ নেওয়া যাক : একটি ঘরে জন্মদিনের নিমন্ত্রণবাড়ি উপলক্ষে ‘n’-জন উপস্হিত (তর্কের খাতিরে ধরে নিলাম ‘n’-এর মান ২০১৬, অর্থাৎ নিমন্ত্রিতের সংখ্যা ২০১৬ জন)। নিমন্ত্রিতের মধ্যে কেউ কেউ অপর কোনো নিমন্ত্রিতর পরিচিত। আবার কেউ কেউ কেবল বাড়ির কর্তারই (কর্ত্রী ও হতে পারে) পরিচিত। এবার গাণিতিক প্রশ্নটা হলো: এই অভ্যাগতদের মধ্যে কমপক্ষে এমন দুই জন কী আছেন, যাঁদের পরিচিতিসংখ্যা সমান?  ‘সমান পরিচিতিসংখ্যা’-র একটা সহজ উদাহরণ হলো: ‘ক’ ‘খ’ কে চিনলে ‘খ’-ও ‘ক’-কে চিনবে , এবং আমরা বলবো ‘ক’ ও ‘খ’-এর পরিচিতিসংখ্যা ‘এক’।

প্রশ্নটা শুনে একটু দৈত্যাকার সমস্যা বলে মনে হলেও সমাধানের চেষ্টা করা যাক। পাঠকবন্ধুদের মাথা হয়তো ঘুরে যাচ্ছে ‘২০১৬’ সংখ্যাটির জন্য (এখানে লক্ষণীয় ২০১৬-র পরিবর্তে যে কোনো পূর্ণ সংখ্যা নিয়ে আমরা ভাবা শুরু করতে পারি)। ধরা যাক নিমন্ত্রণ বাড়িতে ২ জন নিমন্ত্রিত। যদি কেউ কাউকে না চেনেন, তাহলে তাঁদের পরিচিতি সংখ্যা সমান এবং এই সংখ্যাটি হলো শূন্য। যদি একজন আরেকজনকে চেনেন তাহলেও তাঁদের পরিচিতি সংখ্যা সমান এবং এই সংখ্যাটি হলো এক। সুতরাং, ২ জন নিমন্ত্রিতের ক্ষেত্রে আমাদের উত্তর হলো ‘হ্যাঁ’, ওই উপরীউক্ত শর্ত মেনে দুইজন অভ্যাগতকে আমরা অবশ্যই পাবো।

এবার পরিস্থিতিটাকে একটু জটিল করা যাক। ধরা যাক নিমন্ত্রিতের সংখ্যা তিন (সুবিধার্থে তাঁদের নামকরণও করলাম : A, B, ও C)। কি কি সম্ভাবনা হতে পারে ?

(১) প্রথম সম্ভাবনা : কেউই কাউকে চেনেন না। সুতরাং A, B, ও C সকলেরই পরিচিতির সংখ্যা সমান, তা হলো শূন্য|

(২) দ্বিতীয় সম্ভাবনা : যে কোনো একজন সকলকে চেনে। ধরে নিলাম সেই একজন হলো A, অর্থাৎ A-র পরিচিতির সংখ্যা দুই (B ও C) এবং এখনো পর্যন্ত B ও C -র পরিচিতিসংখ্যা সমান, তা হলো এক (যেহেতু দুজনেই A-কে চেনে এবং পরস্পরকে চেনে না)। একথা খুবই পরিষ্কার A-এর পরিবর্তে B বা C যদি অপর দুইজনকে চিনতো তাহলে একইভাবে সেই দুইজনের পরিচিতি সংখ্যা সমান হতো।

(৩) তৃতীয় সম্ভাবনা : সকলেই সকলকে চেনে।  এক্ষেত্রে A, B, ও C সকলেরই পরিচিতিসংখ্যা সমান এবং তা হলো দুই।

সুতরাং, ৩ জন নিমন্ত্রিতের ক্ষেত্রে আমাদের উত্তর হলো ‘হ্যাঁ’, ওই উপরীউক্ত শর্ত মেনে কমপক্ষে দুইজন অভ্যাগতকে আমরা অবশ্যই পাবো।

বোঝাই যাচ্ছে নিমন্ত্রিতের সংখ্যা বাড়তে বাড়তে ২০১৬ অবধি গেলে এরকম একাধিক জটিল সম্ভাবনা আসবে। সমস্ত সম্ভাবনাগুলোর তালিকা না বানিয়েও এই প্রশ্নটার উত্তর দেওয়া যায়। সেই সমাধানই আমাদের হাতে তুলে দেয় ‘পিজিয়ন-হোল প্রিন্সিপল’ (Pigeonhole Principle) বা ‘বক্স প্রিন্সিপল’(Box Principle)। এই ফলাফল অনুসারে আমরা আরও কয়েকধাপ এগিয়ে গিয়ে বলতে পারি: ২০১৬ কেন, যত সংখ্যক (‘n’-জন) নিমন্ত্রিতই আসুন না কেন, তাঁদের মধ্যে কমপক্ষে দুই জন নিমন্ত্রিত সর্বদা থাকবেন যাঁদের পরিচিতিসংখ্যা সমান।

কিন্তু গণিতশাস্ত্রে প্রমাণহীন দাবী মূল্যহীন। সুতরাং প্রশ্ন ওঠে: এই দাবীর যুক্তি বা প্রমাণ কোথায়?

যেহেতু নিমন্ত্রণবাড়িতে ‘n’-জন নিমন্ত্রিত, সুতরাং কোনো একজন নিমন্ত্রিতের পরিচিতিসংখ্যা সর্বাধিক ‘n – ১’ হতে পারে (যেহেতু নিজেই নিজের সাথে পরিচিত, এই ধারণা বাস্তব জগতের মতো গণিতের জগতেও হাস্যকর)। আবার কোনো একজন নিমন্ত্রিতের সর্বনিম্ন পরিচিতিসংখ্যা শূন্য-ও হতে পারে (খুব অসামাজিক কোনো ব্যক্তি অপর কাউকে নাও চিনতে পারেন)। কল্পনা করা যাক, ‘n’-সংখ্যক বড় বড় ঘর রাখা হলো। এক একটা ঘরকে ০ থেকে শুরু করে n – ১ অব্দি একটা করে নম্বর দেওয়া হলো। নিয়ম হলো, কোনো নিমন্ত্রিতের পরিচিতিসংখ্যা যদি ‘i’ হয়, তাঁকে ‘i’-নম্বর ঘরে যেতে হবে। এই নিয়মটা মানতে গেলে দেখা যাবে যে একই সাথে ০ নম্বর ঘরে এবং n – ১ নম্বর ঘরে একজন নিমন্ত্রিত থাকবেন, এটা কোনো অবস্থাতেই সম্ভব নয়। অর্থাৎ, যদি এমন কোনো নিমন্ত্রিত থাকেন যিনি অপর সকলকে চেনেন, তাহলে পরিচিতিসংখ্যা ০ এমন কেউ থাকতে পারেন না। সুতরাং n-জন নিমন্ত্রিত কে n – ১ টি ঘরে স্থান দিতে হবে। অর্থাৎ: কোনো একটি ঘরে কমপক্ষে দুইজন নিমন্ত্রিত থাকবেন-ই। সুতরাং নিমন্ত্রিতসংখ্যা যাই হোক, এমন দুইজন নিমন্ত্রিত অবশ্যই পাওয়া যাবে যাদের পরিচিতিসংখ্যা সর্বদা সমান।

আরও নিখুঁত করে বললে, আমরা ‘জেনেরালাইজড পিজিয়ন-হোল প্রিন্সিপল’ (Generalised Pigeonhole Principle) বক্তব্যটা এইভাবে রাখতে পারি : যদি ‘n’-টি পায়রা ‘k’-টি পায়রার খোপে বসতে যায় (যেখানে n > k), তাহলে কমপক্ষে একটি পায়রার খোপ পাওয়া যাবেই যাতে কমপক্ষে [n / k] ( [n / k] := ফ্লোর (n / k) )-টি পায়রা থাকবে। এমন কথার প্রমাণ তুলনামূলকভাবে কঠিন না। প্রমাণ করার জন্য আমরা method of contradiction* ব্যবহার করবো। ধরা যাক এরকম কোনো পায়রার খোপই পাওয়া যাবে না। অর্থাৎ সকল খোপেই (n / k)-র চেয়ে কম পায়রা আছে। সুতরাং:

মোট পায়রার সংখ্যা < (n / k) × (পায়রার বাক্সের সংখ্যা) = (n / k) × k = n

যা আমাদের সমস্যায় প্রদত্ত শর্তের সরাসরি বিরোধিতা করে (কারণ : পায়রার সংখ্যা = n, একথা প্রদত্ত)। সুতরাং আমরা যা কল্পনা করেছি, অর্থাৎ ‘ধরা যাক এরকম কোনো পায়রার খোপই পাওয়া যাবে না’, এই কথা সর্বৈব মিথ্যে। যা ‘জেনেরালাইজড পিজিয়ন-হোল প্রিন্সিপল’ (Generalised Pigeonhole Principle)-কেই সত্যি বলে প্রমাণিত করে।

‘জেনেরালাইজড পিজিয়ন-হোল প্রিন্সিপল’ গণিতের এক প্রধান শাখা ‘Combinatorics’ এর এক মূল ভিত্তিপ্রস্তর যার অগুন্তি ব্যবহার লক্ষ্য করা যায় নাম্বার থিওরী, সম্ভাবনা-তত্ত্বের মতো গাণিতিক শাখাতে।

(প্রচ্ছদের ছবির উৎস)

* method of contradiction: ধরা যাক একটি গাণিতিক বক্তব্য “A” আমাদের সত্যি হিসেবে প্রমাণ করতে হবে। এই “method of contradiction” অনুসারে আমরা প্রথমে “কল্পনা” করবো যে “A” বক্তব্যটি মিথ্যা। যুক্তিশাস্ত্র (Logic)-এর নিয়মানুসারে “A বক্তব্যটি মিথ্যা => -A বক্তব্যটি সত্য।” এইবার আমরা “-A”-এর সত্যতাকে হাতিয়ার করে দুটি পরস্পরবিরোধী বক্তব্য “B” ও “-B” (নামকরণের সুবিধার্থে B নিলাম… তোমরা এই বক্তব্যকে যে কোনো বর্ণ দিয়েই চিহ্নিত করতে পারো)-এর সত্যতা প্রমাণ করবো; যা অবশ্যই অসম্ভব। সুতরাং আমাদের প্রকল্প (Hypothesis), অর্থাৎ “-A” -এর সত্যতা সঠিক নয়। সুতরাং “-A” মিথ্যা => A সত্য।

উৎসাহী পাঠকবন্ধুরা নিচের বইগুলিতে চোখ বোলাতে পারো :

(১) Mathematical Circles: (Russian Experience) by Dmitrii Vladimirovich Fomin and Sergei Aleksandrovich Genkin.

(২) Problem Solving Strategies by Arthur Engel

লেখাটি অনলাইন পড়তে হলে নিচের কোডটি স্ক্যান করো।

Scan the above code to read the post online.

Link: https://bigyan.org.in/pigeonhole

print