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

Description

ভূমিকা কম্বিনেটরিকসের জগতে তোমাকে স্বাগত! তুমি হয়তো ভ্রূ কুঁচকে ভাবছ কম্বিনেটরিকস আবার কী জিনিস? এটি বীজগণিত এবং জ্যামিতির মতো গণিতের একটি শাখা এবং আধুনিক কম্পিউটার বিজ্ঞানের আজকের অবস্থানে আসার পেছনে এর অত্যন্ত গুরুত্বপূর্ণ ভূমিকা আছে। ভাল প্রোগ্রামিং করতে পারার জন্য কম্বিনেটরিকস জানা অত্যাবশ্যক। গণিত অলিম্পিয়াডে ভাল করতে হলেও কম্বিনেটরিকসে দখল থাকতে হয়, কেননা প্রতিবছর বাংলাদেশ গণিত অলিম্পিয়াডের প্রতিটি ক্যাটেগরিতে বেশ কয়েকটি এবং আন্তর্জাতিক গণিত অলিম্পিয়াড (আইএমও)-তে অন্তত একটি কম্বিনেটরিকসের সমস্যা থাকে। বর্তমানে বাংলায় চমৎকার সব গণিতের বই প্রকাশিত হলেও, কেনো যেন কম্বিনেটরিকস বিষয়ে অলিম্পিয়াডের উপযোগী বই খুব বেশি লেখা হয়নি। মূলত সেজন্যই আমি, জয়দীপ ও জাওয়াদ মিলে কম্বিনেটরিক্সের উপরে একটি বই লিখি। আমরা যখন বইটি প্রকাশ করতে গেলাম, তখন প্রথম বুঝতে পারলাম এটি আকারে একটু বেশিই বড় হয়ে গিয়েছে! তাই দুই খণ্ডে সেটিকে ভাগ করতে হল। কিন্তু তুমি পড়ার সময় ধরে নেবে দুটি খণ্ড মিলিয়ে যেন অখণ্ড একটি বই। এই বইটি পড়তে তোমার কোন গাণিতিক জ্ঞান লাগবে না; শুধু লাগবে অবসরের খানিকটা সময় ও একটু কৌতূহল। এর একটি বড়ো অংশ জুড়ে রয়েছে গণিত অলিম্পিয়াডের কম্বিনেটরিকস। কারণ, যে অবিস্মরণীয় আনন্দময় সময় আমরা, লেখকেরা, গণিত অলিম্পিয়াড এবং গণিত ক্যাম্পে কাটিয়েছি, আমরা চেয়েছি তার অল্প একটু অংশ হলেও যেন তুমি পাও। আশা করি, এতে পাঠ্যবইয়ের ভারিক্কী ভাষায় লেখা বিন্যাস, সমাবেশ কিংবা সম্ভাব্যতার মতো বিষয়গুলো তোমার চোখে রঙিন হয়ে উঠবে, একইসঙ্গে গণিত অলিম্পিয়াডের প্রস্তুতি নিতেও এটি কাজে আসবে। আমরা বিশ্বাস করি প্রতিটি মানুষের গণিতের সৌন্দর্য উপভোগ করার মতো মন রয়েছে। কেউ গণিত ভয় পেলে তার দায়ভার মোটেই তার নয়, বরঞ্চ শিক্ষাপদ্ধতির। আমরা যদি তোমাকে এমনভাবে গণিত শেখাতে পারি, ঠিক যেমনভাবে গণিতকে আমাদের চোখে দেখি, তাহলেই আমাদের এই বই লেখা সার্থক হবে। আমাদের আরেকটি লক্ষ ছিল তোমাদের হাতে একটি নির্ভুল বই তুলে দেওয়া। তাই সম্পূর্ণ বইটি আমরা ল্যাটেক (LaTeX)-এ টাইপসেট করেছি। প্রতিটি বিদেশি নামের সঠিক উচ্চারণ দিতে সর্বোচ্চ চেষ্টা করেছি। পুরো বইয়ের দুশ’র বেশি ছবির প্রায় প্রতিটি Tikz ও Inkscape-এ ভেক্টর গ্রাফিক্স হিসেবে এঁকেছি, যাতে ছাপাখানার সীমাবদ্ধতায় তোমার পড়ার আনন্দটুকু মাটি না হয়। আর ইচ্ছে করেই বেশ মোটা মার্জিন রেখেছি যেন তুমি গণিতবিদ ফার্মার মতো বইয়ের সমস্যাগুলো পাতার ভাঁজেই সমাধান করতে পার, কিংবা নিজের বোঝার সুবিধার্থে কোনো নোট লিখে রাখতে পার। কে জানে, হয়তো এভাবে তুমিও কোনো চমৎকার উপপাদ্য আবিষ্কার করে ফেলবে!
বইটি কীভাবে পড়বে বইয়ের দুটি খণ্ড ভালোভাবে পড়তে তোমার ছয় মাস থেকে এক বছর সময় লাগবে। প্রথমেই পরিশিষ্ট অংশে গিয়ে বইয়ে ব্যবহৃত গাণিতিক প্রতীকগুলোতে একবার চোখ বুলিয়ে এসো। তাহলে বইটি পড়ার সময় বার বার পরিশিষ্ট অংশে গিয়ে প্রতীকগুলো খুঁজতে হবে না। আর অধ্যায়গুলো ক্রমানুসারে পড়া বাধ্যতামূলক নয়। কোনো একটি অধ্যায় ইন্টারেস্টিং মনে না হলে পরের অধ্যায়ে চলে যেতে পার। তবে মনে রাখবে, দ্রুত চোখ বুলিয়ে গেলে কোনো গণিতের বই পুরোপুরি বোঝা যায় না। এ জন্য তোমাকে সময় নিয়ে বইটি পড়তে হবে। যদি কোনো অধ্যায় বুঝতে অসুবিধা হয়, কিছুদিন পড়া বন্ধ রেখে আবার বইটি নিয়ে বসতে হবে, কিংবা কোনো শিক্ষক বা বড় ভাইয়া/আপুর সহযোগিতা নিতে হবে। এর পাশাপাশি তোমাকে প্রচুর সমস্যা সমাধান করতে হবে। এ বইয়ের উদাহরণ এবং অনুশীলনীতে বিভিন্ন বিখ্যাত গাণিতিক সমস্যা; আন্তর্জাতিক গণিত অলিম্পিয়াডের সমস্যা; বাংলাদেশ, যুক্তরাষ্ট্র, রোমানিয়া, রাশিয়া, বুলগেরিয়াসহ বিভিন্ন দেশের গণিত অলিম্পিয়াড এবং গণিত ক্যাম্পের কয়েকশ’ সমস্যা পাবে। আমরা আশা করব অনুশীলনীর সমস্যাগুলো তুমি নিজে নিজে চেষ্টা করবে, যদি একেবারেই সমাধান করতে না পার, তবে বাংলাদেশ গণিত অলিম্পিয়াড ফোরামে (http://matholympiad.org.bd/forum} পোস্ট করবে। এই সঙ্গে একটি ব্যাপার বলে দেওয়া প্রয়োজন যে, এই ছোট্ট বইটি তোমাকে কেবল কম্বিনেটরিকসের বিস্ময়কর জগতের সঙ্গে পরিচয় করিয়ে দিতে পারবে মাত্র। আইএমও পর্যায়ের কম্বিনেটরিকসের সমস্যা সমাধান করতে হলে এই বইয়ের বিষয়গুলো আরও অনেক বিস্তারিতভাবে জানতে হবে, এবং এর পাশাপাশি ডাবল কাউন্টিং (Double Counting), কম্বিনেটরিয়াল জ্যামিতি (Combinatorial Geometry), গেইম থিওরি (Game Theory) ইত্যাদি আরো অনেক বিষয় সম্পর্কে ধারণা থাকতে হবে। আমার খুব ইচ্ছে ছিলো এমন আরও কিছু বিষয় এই বইয়ে অন্তর্ভুক্ত করতে এবং কিছু বিষয় নিয়ে আরও বিস্তারিতভাবে লিখতে। সময়স্বল্পতার কারণে তা সম্ভব হল না। বইয়ের প্রায় প্রতিটি অধ্যায়ের শেষ অংশে উচ্চতর গণিত ও কম্পিউটার বিজ্ঞানে কম্বিনেটরিকসের প্রয়োগ নিয়ে লেখা হয়েছে। গণিত অলিম্পিয়াডের প্রস্তুতির জন্য এগুলো পড়া আবশ্যক নয়। তবে বিষয়গুলো আমাদের কাছে মজার মনে হয়েছে। আশা করি তুমিও সেগুলো পড়ে অভিভূত হবে।
কৃতজ্ঞতা গণিতের উপর একটি বই লেখার পরামর্শ আমাকে প্রথমে দেন আইয়ুব সরকার (আইয়ুব ভাই)। তাই সবার আগে বড় একটি ধন্যবাদ তাঁর প্রাপ্য। এর পরে বলতে হয় বাংলাদেশ গণিত অলিম্পিয়াডের সঙ্গে সংশ্লিষ্ট সকলের কথা, বিশেষ করে মুহম্মদ জাফর ইকবাল, মোহাম্মদ কায়কোবাদ, জামিলুর রেজা চৌধুরি, মুনির হাসান, মাহবুব মজুমদার, বায়েজিদ ভুঁইয়া জুয়েল, সৌমিত্র চক্রবর্তী, সাক্ষর সাহা ও জয়দীপ সুমন সরকার। তাঁদের এতদিনের শ্রমে গণিত অলিম্পিয়াডের মতো একটি মঞ্চ তৈরি হয়েছে বলেই আমিসহ আরও অনেকে গণিতকে ভালবাসতে শিখেছি। এবারে আসি গণিত ক্যাম্পের প্রাক্তন মেন্টরদের কথায়। তাঁদের সবার প্রতি কৃতজ্ঞতা জ্ঞাপন করছি। বিশেষভাবে উল্লেখ করতে হয় কিছু নাম: তারিক আদনান মুন, সামিন রিয়াসাত, ধনঞ্জয় বিশ্বাস, মুগ্ধ তানজীম শরিফ, সৌরভ দাস ও মাহি নূর মুহাম্মদ। গণিত ছাড়াও জীবনের আরও অনেক বিষয়ে পথপ্রদর্শনের জন্য তাঁদের কাছে আমি ও আমার পরবর্তী সময়ের সকলে ঋণী। এই বইটি রিভিউ করেছেন তানভীরুল ইসলাম এবং মো: মাহবুবুল হাসান। অতিব্যস্ততার মধ্যেও সময় করে বইটি পুঙ্খানুপুঙ্খভাবে পড়ে দেখার জন্য তাঁদেরকে অসংখ্য ধন্যবাদ জানাচ্ছি। সেই সঙ্গে বইটি প্রকাশ করার জন্য ধন্যবাদ জানাচ্ছি দ্বিমিকের তামিম শাহ‍রি‍য়ার সুবিন এবং তাহমিদ রাফি ভাইকে। বইটি লেখা ও ছবি আঁকায় অনেকখানি সাহায্য করেছে থানিক নূর সামীন। তার কাছে কৃতজ্ঞতা প্রকাশ করছি। এছাড়াও বইটি রিভিউ করা, অনুশীলনীর সমস্যা খুঁজে দেওয়া, বানান ঠিক করে দেওয়া ইত্যাদি নানা কাজে সহায়তা করেছে তন্ময়, লাযিম, নিনাদ, প্রমি, সাদমান, তাশকি, নাহিন, অতনু, ফারিহা, রিফা, এবং নাজিয়া। তাদের সবার জন্য অনেক অনেক ভালোবাসা ও শুভকামনা রইল। শেষ কথা ২০১৭ সালের ১৬ জুলাই আমরা বইটি লেখা শুরু করেছিলাম। প্রায় দেড় বছর সময় দেখতে দেখতে পার হয়ে গিয়েছে। বই লিখতে গিয়ে আমাদের কারো অ্যাসাইনমেন্ট লেট হয়েছে, রাতের ঘুম নষ্ট হয়েছে, কারো এইচএসসির পড়া বাকি পড়েছে। পুরোটাই আমরা করেছি তোমাদের মতো পাঠকদের কথা ভেবে। বইটি তোমাদের কেমন লেগেছে তা জানতে আমরা খুবই আগ্রহী। তোমাদের বই সম্পর্কিত মতামত, বইয়ের কোনো অংশ বুঝতে অসুবিধা হলো কি না, কিংবা মুদ্রণজনিত কোনো ভুল আছে কি না, তার সব লিখে পাঠাও এই ঠিকানায়: not-a-book@googlegroups.com. তোমাদের সবার জীবনের সেকেন্ড ডিফারেন্সিয়াল নেগেটিভ হোক। -আদীব হাসান
সূচীপত্র • কাউন্টিং (Counting) • এক-দুই-তিন-চার • যোগ নীতি • ভেন ডায়াগ্রাম (Venn Diagram) • গুণ নীতি • ফ্যাক্টোরিয়াল (Factorial) • পারমিউটেশন (Permutation) • কম্বিনেশন (Combination) • স্ট্রিং (String) • ওভার কাউন্টিং (Overcounting) • কেস ভাগ করা • পূরক গুণন (Complementary Counting) • সদৃশতা ও বিসদৃশতা • গ্রিডের মধ্যে পথের সংখ্যা • কিছু শিক্ষণীয় উদাহরণ • অনুশীলনী • সম্ভাব্যতার গণিত (Probability) • আবহাওয়ার পূর্বাভাস • যোগ নীতি • গুণ নীতি • পূরক সম্ভাব্যতা (Complementary Probability) • কিছু শিক্ষণীয় উদাহরণ • সম্ভাব্যতায় সিমেট্রি • কন্ডিশনাল সম্ভাব্যতা ও বায়েসের সুত্র • এক্সপেক্টেশন (Expectation) • কিছু বিখ্যাত সম্ভাবনার সমস্যা • সিম্পসনের প্যারাডক্স (Simpson’s Paradox) • জন্মদিন সমস্যা ও পোলার্ডের রো (ρ) অ্যালগরিদম • অনুশীলনী • পিজিয়নহোল প্রিন্সিপল (Pigeonhole principle) • সরল পিজিয়নহোল প্রিন্সিপল • বর্ধিত পিজিয়নহোল প্রিন্সিপল • অসীম পিজিয়নহোল প্রিন্সিপল • এরডশ-সেকেরেশ (Erdös-Szekeres) উপপাদ্য • ফাইনাইট অটোমাটা (Finite Automata) • অনুশীলনী • গ্রাফ থিওরি (Graph theory) • কনিসবার্গের সাত সেতু • গ্রাফ মানেই লেখচিত্র নয় • নানা রকমের গ্রাফ • পথ, সাইকেল এবং কানেক্টিভিটি • ট্রি • টুর্নামেন্ট • গ্রাফ কালারিং • রামসে (Ramsey) সংখ্যা • স্টেবল ম্যারেজ (Stable Marriage) সমস্যা • অনুশীলনী • ইনডাকশন (Induction) • অসীমের হাতছানি • সাধারণ ইনডাকশন • বিভিন্ন ধারায় ইনডাকশন • আরো স্ট্রং ইনডাকশন • কিছু শিক্ষণীয় উদাহরণ • ইনডাকশন ও কিছু লজিক পাজল • অনুশীলনী • কালারিং (Coloring) • যে পুরষ্কার কেউ পায়নি • ডমিনো, ট্রিমিনো আর টেট্রোমিনো • পর্যাবৃত্ত প্যাটার্নের কালারিং • ভারযুক্ত (weighted) কালারিং • আরো কিছু ক্রিয়েটিভ কালারিং • আর্ট গ্যালারি সমস্যা • অনুশীলনী • পরিশিষ্ট • গ্রন্থসূত্র