কম্বিনেটরিকসে হাতেখড়ি – ২য় খণ্ড

Description

ভূমিকা কম্বিনেটরিকসের জগতে তোমাকে স্বাগত! তুমি হয়তো ভ্রূ কুঁচকে ভাবছ কম্বিনেটরিকস আবার কী জিনিস? এটি বীজগণিত এবং জ্যামিতির মতো গণিতের একটি শাখা এবং আধুনিক কম্পিউটার বিজ্ঞানের আজকের অবস্থানে আসার পেছনে এর অত্যন্ত গুরুত্বপূর্ণ ভূমিকা আছে। ভাল প্রোগ্রামিং করতে পারার জন্য কম্বিনেটরিকস জানা অত্যাবশ্যক। গণিত অলিম্পিয়াডে ভাল করতে হলেও কম্বিনেটরিকসে দখল থাকতে হয়, কেননা প্রতিবছর বাংলাদেশ গণিত অলিম্পিয়াডের প্রতিটি ক্যাটেগরিতে বেশ কয়েকটি এবং আন্তর্জাতিক গণিত অলিম্পিয়াড (আইএমও)-তে অন্তত একটি কম্বিনেটরিকসের সমস্যা থাকে। বর্তমানে বাংলায় চমৎকার সব গণিতের বই প্রকাশিত হলেও, কেনো যেন কম্বিনেটরিকস বিষয়ে অলিম্পিয়াডের উপযোগী বই খুব বেশি লেখা হয়নি। মূলত সেজন্যই আমি, জয়দীপ ও জাওয়াদ মিলে কম্বিনেটরিক্সের উপরে একটি বই লিখি। আমরা যখন বইটি প্রকাশ করতে গেলাম, তখন প্রথম বুঝতে পারলাম এটি আকারে একটু বেশিই বড় হয়ে গিয়েছে! তাই দুই খণ্ডে সেটিকে ভাগ করতে হল। কিন্তু তুমি পড়ার সময় ধরে নেবে দুটি খণ্ড মিলিয়ে যেন অখণ্ড একটি বই। এই বইটি পড়তে তোমার কোন গাণিতিক জ্ঞান লাগবে না; শুধু লাগবে অবসরের খানিকটা সময় ও একটু কৌতূহল। এর একটি বড়ো অংশ জুড়ে রয়েছে গণিত অলিম্পিয়াডের কম্বিনেটরিকস। কারণ, যে অবিস্মরণীয় আনন্দময় সময় আমরা, লেখকেরা, গণিত অলিম্পিয়াড এবং গণিত ক্যাম্পে কাটিয়েছি, আমরা চেয়েছি তার অল্প একটু অংশ হলেও যেন তুমি পাও। আশা করি, এতে পাঠ্যবইয়ের ভারিক্কী ভাষায় লেখা বিন্যাস, সমাবেশ কিংবা সম্ভাব্যতার মতো বিষয়গুলো তোমার চোখে রঙিন হয়ে উঠবে, একইসঙ্গে গণিত অলিম্পিয়াডের প্রস্তুতি নিতেও এটি কাজে আসবে। আমরা বিশ্বাস করি প্রতিটি মানুষের গণিতের সৌন্দর্য উপভোগ করার মতো মন রয়েছে। কেউ গণিত ভয় পেলে তার দায়ভার মোটেই তার নয়, বরঞ্চ শিক্ষাপদ্ধতির। আমরা যদি তোমাকে এমনভাবে গণিত শেখাতে পারি, ঠিক যেমনভাবে গণিতকে আমাদের চোখে দেখি, তাহলেই আমাদের এই বই লেখা সার্থক হবে। আমাদের আরেকটি লক্ষ ছিল তোমাদের হাতে একটি নির্ভুল বই তুলে দেওয়া। তাই সম্পূর্ণ বইটি আমরা ল্যাটেক (LaTeX)-এ টাইপসেট করেছি। প্রতিটি বিদেশি নামের সঠিক উচ্চারণ দিতে সর্বোচ্চ চেষ্টা করেছি। পুরো বইয়ের দুশ’র বেশি ছবির প্রায় প্রতিটি Tikz ও Inkscape-এ ভেক্টর গ্রাফিক্স হিসেবে এঁকেছি, যাতে ছাপাখানার সীমাবদ্ধতায় তোমার পড়ার আনন্দটুকু মাটি না হয়। আর ইচ্ছে করেই বেশ মোটা মার্জিন রেখেছি যেন তুমি গণিতবিদ ফার্মার মতো বইয়ের সমস্যাগুলো পাতার ভাঁজেই সমাধান করতে পার, কিংবা নিজের বোঝার সুবিধার্থে কোনো নোট লিখে রাখতে পার। কে জানে, হয়তো এভাবে তুমিও কোনো চমৎকার উপপাদ্য আবিষ্কার করে ফেলবে! বইটি কীভাবে পড়বে বইয়ের দুটি খণ্ড ভালোভাবে পড়তে তোমার ছয় মাস থেকে এক বছর সময় লাগবে। প্রথমেই পরিশিষ্ট অংশে গিয়ে বইয়ে ব্যবহৃত গাণিতিক প্রতীকগুলোতে একবার চোখ বুলিয়ে এসো। তাহলে বইটি পড়ার সময় বার বার পরিশিষ্ট অংশে গিয়ে প্রতীকগুলো খুঁজতে হবে না। আর অধ্যায়গুলো ক্রমানুসারে পড়া বাধ্যতামূলক নয়। কোনো একটি অধ্যায় ইন্টারেস্টিং মনে না হলে পরের অধ্যায়ে চলে যেতে পার। তবে মনে রাখবে, দ্রুত চোখ বুলিয়ে গেলে কোনো গণিতের বই পুরোপুরি বোঝা যায় না। এ জন্য তোমাকে সময় নিয়ে বইটি পড়তে হবে। যদি কোনো অধ্যায় বুঝতে অসুবিধা হয়, কিছুদিন পড়া বন্ধ রেখে আবার বইটি নিয়ে বসতে হবে, কিংবা কোনো শিক্ষক বা বড় ভাইয়া/আপুর সহযোগিতা নিতে হবে। এর পাশাপাশি তোমাকে প্রচুর সমস্যা সমাধান করতে হবে। এ বইয়ের উদাহরণ এবং অনুশীলনীতে বিভিন্ন বিখ্যাত গাণিতিক সমস্যা; আন্তর্জাতিক গণিত অলিম্পিয়াডের সমস্যা; বাংলাদেশ, যুক্তরাষ্ট্র, রোমানিয়া, রাশিয়া, বুলগেরিয়াসহ বিভিন্ন দেশের গণিত অলিম্পিয়াড এবং গণিত ক্যাম্পের কয়েকশ’ সমস্যা পাবে। আমরা আশা করব অনুশীলনীর সমস্যাগুলো তুমি নিজে নিজে চেষ্টা করবে, যদি একেবারেই সমাধান করতে না পার, তবে বাংলাদেশ গণিত অলিম্পিয়াড ফোরামেClick matholympiad পোস্ট করবে। এই সঙ্গে একটি ব্যাপার বলে দেওয়া প্রয়োজন যে, এই ছোট্ট বইটি তোমাকে কেবল কম্বিনেটরিকসের বিস্ময়কর জগতের সঙ্গে পরিচয় করিয়ে দিতে পারবে মাত্র। আইএমও পর্যায়ের কম্বিনেটরিকসের সমস্যা সমাধান করতে হলে এই বইয়ের বিষয়গুলো আরও অনেক বিস্তারিতভাবে জানতে হবে, এবং এর পাশাপাশি ডাবল কাউন্টিং (Double Counting), কম্বিনেটরিয়াল জ্যামিতি (Combinatorial Geometry), গেইম থিওরি (Game Theory) ইত্যাদি আরো অনেক বিষয় সম্পর্কে ধারণা থাকতে হবে। আমার খুব ইচ্ছে ছিলো এমন আরও কিছু বিষয় এই বইয়ে অন্তর্ভুক্ত করতে এবং কিছু বিষয় নিয়ে আরও বিস্তারিতভাবে লিখতে। সময়স্বল্পতার কারণে তা সম্ভব হল না। বইয়ের প্রায় প্রতিটি অধ্যায়ের শেষ অংশে উচ্চতর গণিত ও কম্পিউটার বিজ্ঞানে কম্বিনেটরিকসের প্রয়োগ নিয়ে লেখা হয়েছে। গণিত অলিম্পিয়াডের প্রস্তুতির জন্য এগুলো পড়া আবশ্যক নয়। তবে বিষয়গুলো আমাদের কাছে মজার মনে হয়েছে। আশা করি তুমিও সেগুলো পড়ে অভিভূত হবে। কৃতজ্ঞতা গণিতের উপর একটি বই লেখার পরামর্শ আমাকে প্রথমে দেন আইয়ুব সরকার (আইয়ুব ভাই)। তাই সবার আগে বড় একটি ধন্যবাদ তাঁর প্রাপ্য। এর পরে বলতে হয় বাংলাদেশ গণিত অলিম্পিয়াডের সঙ্গে সংশ্লিষ্ট সকলের কথা, বিশেষ করে মুহম্মদ জাফর ইকবাল, মোহাম্মদ কায়কোবাদ, জামিলুর রেজা চৌধুরি, মুনির হাসান, মাহবুব মজুমদার, বায়েজিদ ভুঁইয়া জুয়েল, সৌমিত্র চক্রবর্তী, সাক্ষর সাহা ও জয়দীপ সুমন সরকার। তাঁদের এতদিনের শ্রমে গণিত অলিম্পিয়াডের মতো একটি মঞ্চ তৈরি হয়েছে বলেই আমিসহ আরও অনেকে গণিতকে ভালবাসতে শিখেছি। এবারে আসি গণিত ক্যাম্পের প্রাক্তন মেন্টরদের কথায়। তাঁদের সবার প্রতি কৃতজ্ঞতা জ্ঞাপন করছি। বিশেষভাবে উল্লেখ করতে হয় কিছু নাম: তারিক আদনান মুন, সামিন রিয়াসাত, ধনঞ্জয় বিশ্বাস, মুগ্ধ তানজীম শরিফ, সৌরভ দাস ও মাহি নূর মুহাম্মদ। গণিত ছাড়াও জীবনের আরও অনেক বিষয়ে পথপ্রদর্শনের জন্য তাঁদের কাছে আমি ও আমার পরবর্তী সময়ের সকলে ঋণী। এই বইটি রিভিউ করেছেন তানভীরুল ইসলাম এবং মো: মাহবুবুল হাসান। অতিব্যস্ততার মধ্যেও সময় করে বইটি পুঙ্খানুপুঙ্খভাবে পড়ে দেখার জন্য তাঁদেরকে অসংখ্য ধন্যবাদ জানাচ্ছি। সেই সঙ্গে বইটি প্রকাশ করার জন্য ধন্যবাদ জানাচ্ছি দ্বিমিকের তামিম শাহরিয়ার সুবিন এবং তাহমিদ রাফি ভাইকে। বইটি লেখা ও ছবি আঁকায় অনেকখানি সাহায্য করেছে থানিক নূর সামীন। তার কাছে কৃতজ্ঞতা প্রকাশ করছি। এছাড়াও বইটি রিভিউ করা, অনুশীলনীর সমস্যা খুঁজে দেওয়া, বানান ঠিক করে দেওয়া ইত্যাদি নানা কাজে সহায়তা করেছে তন্ময়, লাযিম, নিনাদ, প্রমি, সাদমান, তাশকি, নাহিন, অতনু, ফারিহা, রিফা, এবং নাজিয়া। তাদের সবার জন্য অনেক অনেক ভালোবাসা ও শুভকামনা রইল। শেষ কথা ২০১৭ সালের ১৬ জুলাই আমরা বইটি লেখা শুরু করেছিলাম। প্রায় দেড় বছর সময় দেখতে দেখতে পার হয়ে গিয়েছে। বই লিখতে গিয়ে আমাদের কারো অ্যাসাইনমেন্ট লেট হয়েছে, রাতের ঘুম নষ্ট হয়েছে, কারো এইচএসসির পড়া বাকি পড়েছে। পুরোটাই আমরা করেছি তোমাদের মতো পাঠকদের কথা ভেবে। বইটি তোমাদের কেমন লেগেছে তা জানতে আমরা খুবই আগ্রহী। তোমাদের বই সম্পর্কিত মতামত, বইয়ের কোনো অংশ বুঝতে অসুবিধা হলো কি না, কিংবা মুদ্রণজনিত কোনো ভুল আছে কি না, তার সব লিখে পাঠাও এই ঠিকানায়: not-a-book@googlegroups.com. তোমাদের সবার জীবনের সেকেন্ড ডিফারেন্সিয়াল নেগেটিভ হোক। -আদীব হাসান ক্যামব্রিজ, ম্যাসাচুসেটস ৮ ফেব্রুয়ারি, ২০১৯
সূচীপত্র প্যারিটি (Parity)* জোড় না বেজোড়* কিছু শিক্ষানিয় উদাহরণ* একটি বিখ্যাত সমস্যা* পারমিউটেশনের প্যারিটি* ১৫ পাজল* স্পারনারের লেমা (Sperner’s Lemma) * অনুশীলনী
ইনভ্যারিয়েন্ট এবং মনোভ্যারিয়েন্ট (Invariant and Monoavariant)* ইনভ্যারিয়েন্ট কী? * ভাগশেষের ইনভ্যারিয়েন্স* ইনভ্যারিয়েন্টের খোঁজে* অসম্ভব ক্রিয়েটিভ কিছু ইনভ্যারিয়েন্ট* মনোভ্যারিয়েন্ট* অলস মনোভ্যারিয়েন্ট* মনোভ্যারিয়েন্ট ও অ্যালগরিদম* পঞ্চভূজে পাল্টাপাল্টি* অদৃশ্য সীমানায় কনওয়ের সেনা* অনুশীলনী
এক্সাট্রিম প্রিন্সিপল* এক্সট্রিমের দিকে তাকাও* এক্সট্রিমের অস্তিত্ব* কিছু শিক্ষাণীয় উদাহরণ* সিলভেস্টারের সমস্যা (Sylverster’s Problem) * অস্তিত্ব (Existance) ও এক্সট্রিম* ইনফিনিট ডিসেন্ট* সীমা (Bound) নির্ণয়ে এক্সট্রিম প্রিন্সিপল* অনুশীলনী
আবার ও কাউন্টিং * গণনার প্রমান* কম্বিনেটরিয়াল যুক্তি* স্ট্রিং সম্পর্কিত কিছু প্রবলেম* কম্বিনেটরিয়াল অভেদ এবং প্যাস্কালের ত্রিভূজ* দ্বিপদী বিস্তৃতি* দুইদিকে গণনার কিছু টেকনিক* ফার্মার লিটল থিওরেম* বাইজেকশন* দ্বিতীয় প্রকার স্ট্রালিং সংখ্যা* গণনার বারো ভূঁইয়া* পার্টিশন* বৃত্তের ভাগ গণনা* বারোস-হুইলার ট্রান্সফর্ম* অনুশীলনী রৈখিক রিকারেন্স* ছোটবেলা একটি ধাঁধা* রকারেন্সের ব্যাবহার* রৈখিক ও হোমোজিনিয়াস রিকারেন্স* ধ্রুবসহগযুক্ত রৈখিক হেমোজিনিয়াস রিকারেন্সের সমাধান* ধ্রুবসহগযুক্ত রৈখিক নন-হেমোজিনিয়াস রিকারেন্সের সমাধান* লিন্ডেনমেয়ার সিস্টেম* অনুশীলনী
পরিশিষ্ট* ব্যাবহৃত গাণিতিক প্রতীকসমূহ* গ্রিক বর্ণমালা* অলিম্পিয়ার্ড পরিচিতি* সেট* কনগ্রুয়েন্স* সিগমা ও পাই নোটেশন দিয়ে যোগ/গুণ* ফাংশনঃ ইনজেক্টিভ, সারজেক্টিভ, এবং বাইজেক্টিভ* জটিল সংখ্যা* বহুভূজের শ্রেণিবিভাগ* গ্রন্থসূত্র