Pigeonhole Principle — সহজ থেকে generalized রূপ | পর্ব ৩২

Q: Hash function-এ collision থাকা নিশ্চিত, তবু কেন একে “collision resistant” বলা হয়? SHA-1-এর ইতিহাস “অস্তিত্ব” আর “খুঁজে পাওয়া”-র পার্থক্য সম্পর্কে কী শেখায়?

SHA-1 যেকোনো দৈর্ঘ্যের ইনপুটকে 160 bit-এ নেয়। ইনপুট অসীম সংখ্যক, আউটপুট 2 160 টি, তাই pigeonhole অনুযায়ী অসীম সংখ্যক collision আছে, আর generalized রূপ বলে কিছু আউটপুটের পেছনে অসীম সংখ্যক ইনপুট। “Collision resistant” মানে তাই “collision নেই” নয়, বরং “বাস্তব সময়ে কেউ একটি collision খুঁজে বের করতে পারবেন না”। এটি গাণিতিক উপপাদ্য নয়, একটি কঠিনতার অনুমান। এলোমেলো চেষ্টায় n-bit hash-এ মোটামুটি 2 n/2 টি চেষ্টায় collision আশা করা যায় (birthday সীমা, পর্ব ৪২-এর বিষয়), তাই SHA-1-এর লক্ষ্য ছিল প্রায় 2 80 টি কাজের চেয়ে সহজ কোনো পথ না থাকা। ইতিহাস দেখায়, এই অনুমান ভাঙতে পারে। ২০০৫ সালে Xiaoyun Wang ও সহকর্মীরা দেখান, SHA-1-এ collision খুঁজতে 2 80 -এর চেয়ে অনেক কম কাজ লাগে বলে প্রকাশিত হয়। এরপর নির্দেশিকাগুলো ধীরে ধীরে SHA-1 থেকে সরে যেতে বলে।

Q: “আমাদের সফটওয়্যার যেকোনো ফাইলকে অর্ধেক করে দেয়, আর বারবার চালালে আরও ছোট হয়।” এমন দাবি শুনলে গণিত দিয়ে কীভাবে উত্তর দেবেন, আর তবু zip কেন বাস্তবে এত কাজের?

উপপাদ্য ৫.১ দাবিটিকে সরাসরি খণ্ডন করে। দৈর্ঘ্য n bit-এর ফাইল 2 n টি; অর্ধেক বা তার কম দৈর্ঘ্যের ফাইল মোট 2 n/2+1 − 1টির মতো (n জোড় হলে), যা 2 n -এর তুলনায় নগণ্য। one-to-one ফাংশন বড় সেট থেকে ছোট সেটে যেতে পারে না, তাই বেশিরভাগ ফাইলকে অর্ধেক করা অসম্ভব। “বারবার চালালে আরও ছোট” দাবিটি আরও খারাপ: তা সত্য হলে যেকোনো ফাইল শেষে এক bit-এ নেমে আসত, আর এক bit দিয়ে মাত্র দুটি ফাইল আলাদা করা যায়। উপপাদ্য ৫.২ আরও বলে: যে compressor কোনো ফাইল ছোট করে, সে অবশ্যই কোনো ফাইল বড়ও করে। ব্লক ৩-এ zlib এলোমেলো byte-এ ঠিক তাই করেছে। তাহলে zip কাজ করে কেন? কারণ আমরা যেসব ফাইল সত্যিই বানাই, যেমন লেখা, log, ছবি, সেগুলো সব সম্ভাব্য ফাইলের মধ্যে খুব ছোট, বিশেষ একটি অংশ, যেখানে পুনরাবৃত্তি আর ছাঁচ আছে। compressor সেই অংশকে ছোট করে, আর এলোমেলো দেখতে বিশাল বাকি অংশকে সামান্য বড় করে, যা আমরা প্রায় কখনো দেখি না।

Q: Erdős–Szekeres উপপাদ্য শুধু একটি সুন্দর ধাঁধা, নাকি কম্পিউটার বিজ্ঞানে এর বাস্তব প্রতিধ্বনি আছে? Longest increasing subsequence আর patience sorting-এর সঙ্গে সম্পর্ক কী?

উপপাদ্যের প্রমাণের label i k আসলে একটি algorithm-এর হৃদয়: “a k -এ শেষ হওয়া দীর্ঘতম increasing subsequence” হলো longest increasing subsequence (LIS) সমস্যার dynamic programming-এর অবস্থা। ব্লক ২-এর longest ফাংশন ঠিক সেটিই হিসাব করে, O(N 2 ) সময়ে। একটি চতুর উন্নতি O(N log N)-এ নামায়: প্রতিটি দৈর্ঘ্যের increasing subsequence-এর সবচেয়ে ছোট শেষ পদ রেখে binary search. এই পদ্ধতিকে তাসের একটি একা-খেলার নামে patience sorting বলা হয়, আর এর বিশ্লেষণে দেখা যায়, তাসের স্তূপের সংখ্যা ঠিক LIS-এর দৈর্ঘ্য। কোড DSA কোর্সের পর্ব ৫৩ -এ। Erdős–Szekeres এখানে একটি নিশ্চয়তা দেয়: N-টি ভিন্ন সংখ্যায় LIS আর longest decreasing subsequence-এর গুণফল অন্তত N (প্রমাণের label-যুক্তিতেই আসে, কারণ সব label আলাদা আর i ≤ LIS, d ≤ LDS). তাই দুটির একটি অন্তত √N. এর ব্যবহারিক অর্থ আছে: একটি তালিকা প্রায় সাজানো কি না মাপার অনেক পদ্ধতি LIS-এর সঙ্গে যুক্ত, যেমন “কয়টি পদ সরালে তালিকা সাজানো হয়” তার উত্তর N − LIS.

এক নজরে · TL;DR

মৌলিক নীতি: k-টি খোপে k + 1টি (বা বেশি) জিনিস রাখলে অন্তত একটি খোপে দুটি বা তার বেশি জিনিস থাকবে। প্রমাণ এক লাইনের বিরোধ: প্রতিটিতে বড়জোর একটি হলে মোট বড়জোর k.
Generalized রূপ: N-টি জিনিস k-টি খোপে রাখলে কোনো খোপে অন্তত ⌈N/k⌉টি থাকবে। ১০০টি অর্ডার ৭ দিনে হলে কোনো একদিনে অন্তত ১৫টি।
ক্লাসিক প্রয়োগ: n + 1টি সংখ্যার দুটির ভাগশেষ mod n সমান; যেকোনো n-টি সংখ্যায় পাশাপাশি একটি block-এর যোগফল n দিয়ে বিভাজ্য (prefix sum); 1..2n থেকে n + 1টি সংখ্যায় একটি অন্যটিকে ভাগ করে; n² + 1টি ভিন্ন সংখ্যার ক্রমে দৈর্ঘ্য n + 1-এর monotone subsequence আছে।
কম্পিউটারে: hash collision এড়ানো অসম্ভব, আর কোনো lossless compression প্রতিটি ফাইল ছোট করতে পারে না: দৈর্ঘ্য n-এর 2ⁿটি string-এর জন্য ছোট string মাত্র 2ⁿ − 1টি।
অস্তিত্ব বনাম খোঁজা: pigeonhole বলে জোড়াটি আছে, কোথায় আছে তা বলে না। কখনো খোঁজা সহজ (prefix sum), কখনো কার্যত অসম্ভব (SHA-256-এর collision). Ramsey-র R(3,3) = 6 এই নীতিরই একটি গভীর রূপ।

এই পর্বে যা শিখবেন

Pigeonhole principle-এর মৌলিক আর generalized রূপের সঠিক বিবৃতি আর প্রমাণ, আর “কমপক্ষে কয়টি হলে নিশ্চিত” ধরনের অঙ্কের সূত্র k(r − 1) + 1
কোনটি “খোপ” আর কোনটি “কবুতর”, তা বাছার কৌশল: ভাগশেষ, prefix sum, odd part আর (i, d) label
Erdős–Szekeres উপপাদ্যের প্রমাণ, আর কেন n² পদের ক্রমে নিশ্চয়তা নেই
Hash collision আর lossless compression-এর সীমার গাণিতিক প্রমাণ, Python আর zlib দিয়ে যাচাই
R(3,3) = 6-এর প্রমাণ, আর অস্তিত্বের প্রমাণ থেকে সত্যিকারের উদাহরণ খুঁজে পাওয়ার দূরত্ব

১ · খোপ আর কবুতর — নীতিটি কী বলে

পুরোনো ডাকঘরে চিঠি রাখার জন্য দেয়ালে সারি সারি খোপ থাকে। ধরুন খোপ ১০টি, আর আজ এসেছে ১১টি চিঠি। আপনি যেভাবেই সাজান, কোনো একটি খোপে অন্তত দুটি চিঠি পড়বেই। কোন খোপে, তা আগে থেকে বলা যায় না; কিন্তু “কোথাও না কোথাও” দুটি থাকবে, এটি নিশ্চিত। এত সরল কথাটির নাম pigeonhole principle, বাংলায় কবুতরের খোপের নীতি। ইংরেজি নামের ছবিটি হলো খোপওয়ালা কবুতরের ঘর: খোপের চেয়ে কবুতর বেশি হলে কোনো খোপে একাধিক কবুতর ঢুকবে।

বাজারঘরের ভাষায় আরও কয়েকটি উদাহরণ। গুদামের তাকে লাল, নীল আর কালো, তিন রঙের মোজার প্যাকেট এলোমেলো রাখা। অন্ধকারে কমপক্ষে কয়টি প্যাকেট তুললে নিশ্চিত হবেন যে দুটি একই রঙের? উত্তর ৪: তিনটি তুললে হয়তো তিন রঙের একটি করে পেলেন, কিন্তু চতুর্থটি তিনটির কোনো একটির সঙ্গে মিলবেই। এখানে খোপ হলো রং (৩টি), কবুতর হলো তোলা প্যাকেট। আরেকটি: বাজারঘরের ৩৬৭ জন কর্মী থাকলে অন্তত দুজনের জন্মদিন (মাস আর তারিখ) একই, কারণ ২৯ ফেব্রুয়ারিসহ সম্ভাব্য তারিখ ৩৬৬টি। লক্ষ করুন, ৩৬৬ জনে এই নিশ্চয়তা নেই। আবার সম্ভাবনার প্রশ্ন একেবারে আলাদা: মাত্র ২৩ জনেই একই জন্মদিনের সম্ভাবনা অর্ধেকের বেশি, যা পর্ব ৪২ “Birthday paradox, hash collision আর balls-into-bins”-এর বিষয়। pigeonhole দেয় নিশ্চয়তা, সম্ভাবনা নয়।

উপপাদ্য ১.১ (pigeonhole principle, মৌলিক রূপ)

k একটি ধনাত্মক পূর্ণসংখ্যা। k + 1টি বা তার বেশি বস্তু k-টি বাক্সে রাখলে অন্তত একটি বাক্সে দুটি বা তার বেশি বস্তু থাকবে।

ফাংশনের ভাষায়: A আর B সসীম সেট, |A| > |B| হলে কোনো ফাংশন f: A → B one-to-one নয়, অর্থাৎ এমন a ≠ a′ আছে যাতে f(a) = f(a′).

প্রমাণ (proof by contradiction, পর্ব ০৮):

ধরি, কোনো বাক্সেই দুটি বা তার বেশি বস্তু নেই, অর্থাৎ প্রতিটি বাক্সে বড়জোর একটি। — সিদ্ধান্তের negation
তাহলে বস্তুর মোট সংখ্যা বড়জোর 1 + 1 + ⋯ + 1 (k বার) = k. — বাক্সগুলোর যোগফল
কিন্তু বস্তু অন্তত k + 1টি, আর k + 1 > k. বিরোধ। তাই কোনো বাক্সে অন্তত দুটি বস্তু আছে। ∎ — বিরোধ থেকে সিদ্ধান্ত

ফাংশনের রূপটি একই কথা: A-এর প্রতিটি উপাদান একটি “বস্তু”, আর f(a) হলো সে কোন বাক্সে গেল। পর্ব ১৬-এ আমরা ঠিক এই যুক্তিতে দেখিয়েছিলাম যে m > n হলে m-উপাদানের সেট থেকে n-উপাদানের সেটে কোনো one-to-one ফাংশন নেই। এই পর্বে সেই বীজ থেকে পুরো গাছ গজাবে।

৫টি খোপ, ৬টি চিঠি

যেভাবেই সাজান, অন্তত একটি খোপে দুটি পড়বে। কমলা খোপটি সেই “ভিড়”।

নীতিটি এতই স্পষ্ট যে প্রথমে মনে হয়, এ দিয়ে আর কী প্রমাণ হবে? আসল শিল্পটি অন্য জায়গায়: সমস্যার মধ্যে কোনটি “বাক্স” আর কোনটি “বস্তু”, তা চিনে নেওয়া। পুরো পর্ব জুড়ে বাক্স হবে কখনো রং, কখনো ভাগশেষ, কখনো সংখ্যার বিজোড় অংশ, কখনো একজোড়া label. একবার ঠিক বাক্স বাছতে পারলে প্রমাণ এক-দুই লাইনের।

ইতিহাস: নীতিটির সবচেয়ে পরিচিত পুরোনো নাম জার্মান “Schubfachprinzip” (ড্রয়ারের নীতি), যা Peter Gustav Lejeune Dirichlet-এর সঙ্গে যুক্ত; তিনি ১৮৩০-১৮৪০-এর দশকে সংখ্যাতত্ত্বে (বিশেষ করে বাস্তব সংখ্যাকে ভগ্নাংশ দিয়ে আসন্ন করায়) এই যুক্তি ব্যবহার করেছিলেন বলে সাধারণত উল্লেখ করা হয়। তাই একে Dirichlet-এর box principle-ও বলে। ইতিহাসবিদেরা এরও আগের উদাহরণ পেয়েছেন: ১৬২২ সালের একটি ফরাসি বইয়ে (সাধারণত Jean Leurechon-এর বলে ধরা) মাথার চুলের সংখ্যা নিয়ে একই যুক্তি আছে বলে জানা যায়। “pigeonhole” নামটি ইংরেজি পাঠ্যবইয়ে বিংশ শতকে জনপ্রিয় হয়।

২ · Generalized pigeonhole — ⌈N/k⌉

বাজারঘর এক সপ্তাহে ১০০টি অর্ডার পেয়েছে। মৌলিক নীতি বলে, কোনো একদিনে অন্তত দুটি অর্ডার হয়েছে। কিন্তু এটি খুব দুর্বল কথা; আমরা আরও বেশি বলতে পারি। গড়ে প্রতিদিন 100/7 ≈ 14.29টি, আর সব দিন যদি গড়ের নিচে থাকত, তাহলে মোট ১০০ হতো না। গড়ের চেয়ে কম হলে পূর্ণসংখ্যায় বড়জোর ১৪টি, তাই কোনো একদিনে অন্তত ১৫টি। এই “গড়ের যুক্তি”-কে নিখুঁত করতে লাগে ceiling ⌈x⌉: x-এর সমান বা বড় সবচেয়ে ছোট পূর্ণসংখ্যা, যেমন ⌈14.29⌉ = 15 আর ⌈14⌉ = 14.

উপপাদ্য ২.১ (generalized pigeonhole principle)

N-টি বস্তু k-টি বাক্সে রাখলে (N, k ধনাত্মক পূর্ণসংখ্যা) অন্তত একটি বাক্সে কমপক্ষে ⌈N/k⌉টি বস্তু থাকবে।

প্রমাণ: প্রথমে একটি সহায়ক তথ্য: যেকোনো বাস্তব x-এর জন্য ⌈x⌉ < x + 1, কারণ ⌈x⌉ হলো x-এর সমান বা বড় সবচেয়ে ছোট পূর্ণসংখ্যা, আর ⌈x⌉ − 1 তাই x-এর চেয়ে ছোট।

ধরি, প্রতিটি বাক্সে বড়জোর ⌈N/k⌉ − 1টি বস্তু আছে। — সিদ্ধান্তের negation
তাহলে মোট বস্তু ≤ k(⌈N/k⌉ − 1). — k-টি বাক্সের যোগফল
⌈N/k⌉ < N/k + 1, তাই k(⌈N/k⌉ − 1) < k(N/k + 1 − 1) = N. — সহায়ক তথ্য, k > 0 দিয়ে গুণ
অর্থাৎ মোট বস্তু N-এর চেয়ে কম, অথচ বস্তু ঠিক N-টি। বিরোধ। ∎

Generalized pigeonhole principle-এ N = k + 1 বসালে ⌈(k + 1)/k⌉ = 2, অর্থাৎ মৌলিক রূপটি এর একটি বিশেষ ক্ষেত্র। আর সীমাটি নিখুঁত: বস্তুগুলো যতটা সম্ভব সমানভাবে ছড়ালে কোনো বাক্সে ⌈N/k⌉-এর বেশি পড়ে না, তাই এর চেয়ে বড় সংখ্যার নিশ্চয়তা দেওয়া যায় না। নিচের stepper এই দুটি দিক, প্রমাণ আর নিখুঁততা, ১০০টি অর্ডারের উদাহরণে দেখায়।

1N = 100 অর্ডার, k = 7 দিন2ধরি প্রতিদিন ≤ 143মোট ≤ 7 · 14 = 98498 ≠ 100 → বিরোধ5⌈100/7⌉ = ⌈14.28…⌉ = 15615+15+14+14+14+14+14

চলক

প্রতিদিন সর্বোচ্চ
মোট

সমস্যা। বস্তু = অর্ডার (N = 100), বাক্স = সপ্তাহের দিন (k = 7). গড় প্রায় 14.29, কিন্তু অর্ডার ভগ্নাংশে হয় না।
উল্টোটা ধরা। ধরি কোনো দিনেই 15 বা তার বেশি অর্ডার নেই, অর্থাৎ প্রতিদিন বড়জোর 14টি। তাহলে সাত দিনে বড়জোর 7 · 14 = 98টি।
বিরোধ। 98টি জায়গায় 100টি অর্ডার আঁটে না। তাই ধরে নেওয়াটি মিথ্যা।
সূত্রে। ⌈100/7⌉ = 15. কোনো একদিনে কমপক্ষে 15টি অর্ডার হয়েছে, কোন দিন তা জানা না থাকলেও।
নিখুঁততা। 15, 15, 14, 14, 14, 14, 14 বণ্টনে মোট 100, আর কোনো দিনে 16 নেই। তাই “অন্তত 16” দাবি করা যায় না; 15-ই সেরা উত্তর।

উল্টো প্রশ্ন: “কমপক্ষে কয়টি হলে নিশ্চিত?”

পরীক্ষায় প্রশ্ন প্রায়ই উল্টো দিক থেকে আসে: k-টি বাক্স থাকলে কমপক্ষে কয়টি বস্তু নিলে নিশ্চিত হবেন যে কোনো বাক্সে অন্তত r-টি আছে? উত্তর N = k(r − 1) + 1. কারণ, k(r − 1)টি বস্তু প্রতিটি বাক্সে ঠিক r − 1টি করে রাখা যায়, যেখানে কোনো বাক্সে r-টি নেই; আর আরও একটি যোগ করলে ⌈(k(r − 1) + 1)/k⌉ = r. উদাহরণ: বাংলাদেশের ৬৪টি জেলা। কমপক্ষে কতজন ক্রেতা হলে নিশ্চিত যে অন্তত ৩ জন একই জেলার? 64 · 2 + 1 = 129 জন।

গড়ের নীতি: generalized রূপের আরেকটি চেহারা হলো, কয়েকটি সংখ্যার মধ্যে অন্তত একটি তাদের গড়ের সমান বা বড়, আর অন্তত একটি গড়ের সমান বা ছোট। বস্তু গোনার বদলে বাস্তব সংখ্যার যোগফলেও এটি খাটে, আর অনেক প্রমাণে এই রূপটিই কাজে লাগে।

৩ · ভাগশেষ আর ভাগযোগ্যতার খেলা

সংখ্যাতত্ত্বে সবচেয়ে স্বাভাবিক বাক্স হলো ভাগশেষ। n দিয়ে ভাগ করলে ভাগশেষ মাত্র n রকম: 0, 1, …, n − 1 (পর্ব ২০-এর division algorithm). তাই n + 1টি পূর্ণসংখ্যার মধ্যে দুটির ভাগশেষ সমান হবেই। দুটি সংখ্যার ভাগশেষ সমান মানে তারা congruent mod n, আর তাদের পার্থক্য n দিয়ে বিভাজ্য (পর্ব ২২)।

উপপাদ্য ৩.১ (একই ভাগশেষ)

n ≥ 1. যেকোনো n + 1টি পূর্ণসংখ্যার মধ্যে এমন দুটি x ≠ y (তালিকায় আলাদা অবস্থানে) আছে, যাতে n ∣ (x − y).

প্রমাণ: বাক্স = ভাগশেষ {0, …, n − 1}, n-টি। বস্তু = n + 1টি সংখ্যা, প্রতিটি তার ভাগশেষের বাক্সে। মৌলিক নীতিতে একটি বাক্সে দুটি সংখ্যা x, y. x ≡ y (mod n), অর্থাৎ n ∣ (x − y). ∎

উল্টো দিকে, n-টি সংখ্যায় এটি নিশ্চিত নয়: 0, 1, …, n − 1-এর কোনো দুটির পার্থক্য n দিয়ে বিভাজ্য নয়। pigeonhole-এর প্রায় প্রতিটি ফলেই এমন একটি “ঠিক সীমার” উদাহরণ থাকে; সেটি খুঁজে নেওয়া ভালো অভ্যাস।

পাশাপাশি অর্ডারের block, যার যোগফল n দিয়ে বিভাজ্য

এবার একটি চমৎকার প্রয়োগ। বাজারঘর পাঁচ দিনে যথাক্রমে 4, 8, 6, 9, 7টি অর্ডার পেল। দাবি: পরপর কয়েকটি দিন বাছা যায়, যাদের মোট অর্ডার 5 দিয়ে বিভাজ্য। এটি শুধু এই সংখ্যাগুলোর জন্য নয়, যেকোনো n-টি পূর্ণসংখ্যার জন্য সত্য। বাক্স বাছার কৌশলটি হলো prefix sum: S₀ = 0, S_j = a₁ + ⋯ + a_j. পাশাপাশি block a_i+1 + ⋯ + a_j-এর যোগফল ঠিক S_j − S_i.

উপপাদ্য ৩.২ (বিভাজ্য block)

a₁, …, a_n যেকোনো n-টি পূর্ণসংখ্যা (n ≥ 1). তাহলে এমন 0 ≤ i < j ≤ n আছে, যাতে n ∣ (a_i+1 + a_i+2 + ⋯ + a_j). বিশেষ করে, সংখ্যাগুলোর একটি অশূন্য subset-এর যোগফল n দিয়ে বিভাজ্য।

প্রমাণ:

n + 1টি prefix sum S₀, S₁, …, S_n নিন। — বস্তু
প্রতিটিকে তার ভাগশেষ mod n-এর বাক্সে রাখুন; বাক্স n-টি। — বাক্স
মৌলিক নীতিতে দুটি সূচক i < j-এর জন্য S_i ≡ S_j (mod n). — pigeonhole
তাই n ∣ (S_j − S_i) = a_i+1 + ⋯ + a_j, আর i < j বলে block-টি ফাঁকা নয়। ∎ — উপপাদ্য ৩.১

S₀ = 0 যোগ করাটাই মূল চালাকি: সেটি ছাড়া মাত্র n-টি prefix sum থাকত, আর pigeonhole খাটত না (যদিও তখন কোনো S_j ≡ 0 হলে সরাসরি উত্তর মেলে; S₀ সেই ক্ষেত্রটিকে একই যুক্তির ভেতরে নিয়ে আসে)। নিচে বাজারঘরের পাঁচ দিনে প্রমাণটি চালানো হলো।

1S₀ = 0         → mod 5 = 02S₁ = 4         → 43S₂ = 4+8 = 12  → 24S₃ = 12+6 = 18 → 35S₄ = 18+9 = 27 → 2 ★6S₅ = 27+7 = 34 → 4 ★

চলক

ভরা বাক্স
পাওয়া block

শুরু। S₀ = 0, ভাগশেষ 0. মোট ৬টি prefix sum (S₀ থেকে S₅) আসবে, কিন্তু mod 5-এ বাক্স মাত্র ৫টি।
প্রথম দিন। S₁ = 4, ভাগশেষ 4. নতুন বাক্স, কোনো সংঘর্ষ নেই।
দ্বিতীয় দিন। S₂ = 12, ভাগশেষ 2. এখনো সব বাক্সে একজন করে।
তৃতীয় দিন। S₃ = 18, ভাগশেষ 3. চারটি বাক্স ভরা, শুধু বাক্স 1 খালি; বাকি দুটি prefix sum-এর অন্তত একটি পুরোনো বাক্সে পড়বেই।
সংঘর্ষ। S₄ = 27, ভাগশেষ 2, যা S₂-এর বাক্স। তাই S₄ − S₂ = a₃ + a₄ = 6 + 9 = 15, যা 5 দিয়ে বিভাজ্য: তৃতীয় আর চতুর্থ দিন।
আরেকটি। S₅ = 34, ভাগশেষ 4, যা S₁-এর বাক্স। S₅ − S₁ = 8 + 6 + 9 + 7 = 30, এটিও 5 দিয়ে বিভাজ্য। নীতি অন্তত একটি দেয়, এখানে দুটি মিলল।

1..2n-এ ভাজক-জোড়া — “বিজোড় অংশ” বাক্স

উপপাদ্য ৩.৩

n ≥ 1. {1, 2, …, 2n} থেকে যেকোনো n + 1টি ভিন্ন সংখ্যা বাছলে তাদের মধ্যে এমন দুটি a < b থাকবে, যাতে a ∣ b.

প্রমাণ:

প্রতিটি ধনাত্মক পূর্ণসংখ্যা x-কে অনন্যভাবে x = 2^k · m লেখা যায়, যেখানে k ≥ 0 আর m বিজোড়; m-কে বলি x-এর বিজোড় অংশ। — 2-এর ঘাত বারবার ভাগ করা (unique factorization)
x ≤ 2n হলে m ≤ 2n, আর m বিজোড়, তাই m ∈ {1, 3, 5, …, 2n − 1}: মাত্র n-টি সম্ভাবনা। — বাক্স n-টি
n + 1টি সংখ্যা, n-টি বাক্স: দুটি সংখ্যা a ≠ b-এর বিজোড় অংশ একই m. ধরি a = 2^sm, b = 2^tm. — pigeonhole
a ≠ b বলে s ≠ t; সাধারণতা না হারিয়ে s < t ধরি। তখন b = 2^{t − s} · a, অর্থাৎ a ∣ b. ∎

এখানেও সীমা নিখুঁত: {n + 1, n + 2, …, 2n} n-টি সংখ্যা, কিন্তু কোনো দুটির মধ্যে ভাগের সম্পর্ক নেই, কারণ এই সীমার ভেতরের a-এর সবচেয়ে ছোট বড়-গুণিতক 2a, যা 2n-এর বেশি। এই উপপাদ্যটি Paul Erdős তরুণ Lajos Pósa-কে জিজ্ঞেস করেছিলেন, আর Pósa দ্রুত এই প্রমাণটি দেন, এমন গল্প প্রচলিত আছে।

এবার Python-এ দুটি ফলই যাচাই করা যাক। প্রথম অংশ প্রমাণটিকে সরাসরি একটি algorithm বানায়: prefix sum-এর ভাগশেষ একটি dict-এ রাখা, আর প্রথম পুনরাবৃত্তিতে থামা। দ্বিতীয় অংশ ছোট n-এ {1..2n}-এর সব (n + 1)-উপাদানের subset পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
from itertools import combinations
random.seed(32)

def divisible_block(a):
    """Return (i, j) such that a[i] + ... + a[j-1] is divisible by n = len(a)."""
    n, s = len(a), 0
    seen = {0: 0}                       # remainder of a prefix sum -> its index
    for j, x in enumerate(a, start=1):
        s = (s + x) % n
        if s in seen:                   # two prefix sums in the same box
            return seen[s], j
        seen[s] = j
    raise AssertionError("pigeonhole says this line is never reached")

a = [4, 8, 6, 9, 7]                     # Bazarghar orders on 5 days
i, j = divisible_block(a)
print("orders", a, "-> block", a[i:j], "sum", sum(a[i:j]))

for n in (5, 12, 100, 500):
    latest = 0
    for _ in range(200):
        a = [random.randint(1, 10**6) for _ in range(n)]
        i, j = divisible_block(a)
        assert sum(a[i:j]) % n == 0
        latest = max(latest, j)
    print(f"n={n:3}: 200 random lists OK, latest stop at prefix {latest}")
def has_divisor_pair(s):
    return any(b % a == 0 for a, b in combinations(s, 2))   # s is sorted

for n in (3, 4, 5, 6):
    sets = list(combinations(range(1, 2 * n + 1), n + 1))
    top = range(n + 1, 2 * n + 1)       # n numbers, no divisor pair
    print(f"n={n}: {len(sets):3} sets of {n + 1} from 1..{2 * n}, all have a pair:",
          all(map(has_divisor_pair, sets)), "| top half:", has_divisor_pair(top))

আসল আউটপুট (ব্রাউজারের Python):

orders [4, 8, 6, 9, 7] -> block [6, 9] sum 15
n=  5: 200 random lists OK, latest stop at prefix 5
n= 12: 200 random lists OK, latest stop at prefix 11
n=100: 200 random lists OK, latest stop at prefix 32
n=500: 200 random lists OK, latest stop at prefix 86
n=3:  15 sets of 4 from 1..6, all have a pair: True | top half: False
n=4:  56 sets of 5 from 1..8, all have a pair: True | top half: False
n=5: 210 sets of 6 from 1..10, all have a pair: True | top half: False
n=6: 792 sets of 7 from 1..12, all have a pair: True | top half: False

প্রথম লাইনে stepper-এর উত্তরই এসেছে: block [6, 9], যোগফল 15. এরপর প্রতিটি n-এ ২০০টি এলোমেলো তালিকায় একটিও ব্যর্থতা নেই, ঠিক যেমন প্রমাণ বলে। “latest stop” কলামটি মজার: n = 5-এ কখনো কখনো শেষ prefix পর্যন্ত যেতে হয়েছে, কিন্তু n = 500-এ সবচেয়ে দেরিতেও ৮৬তম prefix-এ সংঘর্ষ মিলেছে। এলোমেলো তালিকায় সংঘর্ষ অনেক আগেই আসে, যা birthday paradox-এর ছায়া (পর্ব ৪২). প্রমাণ শুধু সবচেয়ে খারাপ ক্ষেত্রের সীমা দেয়: n + 1টি prefix-এর মধ্যে। শেষ চার লাইনে প্রতিটি n-এ সব subset-এ ভাজক-জোড়া আছে, আর “top half” {n + 1, …, 2n}-এ নেই, অর্থাৎ n + 1 সংখ্যাটি কমানো যায় না। এই algorithm-টি O(n) সময়ে চলে; একই prefix sum কৌশলের কোড DSA কোর্সের পর্ব ১৭-এ আছে।

৪ · Erdős–Szekeres — এলোমেলো ক্রমেও শৃঙ্খলা

বাজারঘরের দশজন ডেলিভারি রাইডার এলোমেলো ক্রমে লাইনে দাঁড়িয়েছেন, সবার উচ্চতা আলাদা। দাবি: লাইন থেকে কাউকে না সরিয়ে, শুধু কয়েকজনকে বেছে, এমন চারজন পাওয়া যাবে যাঁরা বাঁ থেকে ডানে ক্রমশ লম্বা, অথবা ক্রমশ খাটো। ক্রমের ভেতর থেকে কিছু পদ বাদ দিয়ে, বাকিদের ক্রম না বদলে যা থাকে, তাকে বলে subsequence. যে subsequence ক্রমশ বাড়ে বা ক্রমশ কমে, সেটি monotone subsequence.

উপপাদ্য ৪.১ (Erdős–Szekeres, ১৯৩৫)

n ≥ 1. n² + 1টি ভিন্ন বাস্তব সংখ্যার যেকোনো sequence-এ দৈর্ঘ্য n + 1-এর একটি strictly increasing বা একটি strictly decreasing subsequence আছে।

Erdős–Szekeres উপপাদ্যের প্রমাণে বাক্স বাছা একটু সূক্ষ্ম। প্রতিটি পদ a_k-কে দুটি সংখ্যার label দিন: i_k = a_k-এ শেষ হওয়া দীর্ঘতম increasing subsequence-এর দৈর্ঘ্য, আর d_k = a_k-এ শেষ হওয়া দীর্ঘতম decreasing subsequence-এর দৈর্ঘ্য। a_k নিজে একাই দৈর্ঘ্য 1-এর দুটোই, তাই i_k, d_k ≥ 1. বাক্স হবে label-জোড়া (i, d).

প্রমাণ (label-এর এই প্রমাণটি A. Seidenberg ১৯৫৯ সালে দেন বলে উল্লেখ করা হয়):

ধরি, দৈর্ঘ্য n + 1-এর কোনো monotone subsequence নেই। তাহলে প্রতিটি k-তে 1 ≤ i_k ≤ n আর 1 ≤ d_k ≤ n. — বিরোধের জন্য ধরে নেওয়া
সম্ভাব্য জোড়া (i, d) তাই বড়জোর n · n = n²টি, কিন্তু পদ n² + 1টি। দুটি সূচক j < k-এর label একই: i_j = i_k আর d_j = d_k. — pigeonhole (গুণের নিয়মে n²টি বাক্স)
পদগুলো ভিন্ন, তাই a_j < a_k অথবা a_j > a_k. — দুটি ক্ষেত্র
যদি a_j < a_k: a_j-এ শেষ হওয়া দীর্ঘতম increasing subsequence-এর পরে a_k জুড়ে দিলে দৈর্ঘ্য i_j + 1-এর increasing subsequence পাই, যা a_k-এ শেষ। তাই i_k ≥ i_j + 1 > i_j, বিরোধ। — সংজ্ঞা
যদি a_j > a_k: একইভাবে d_k ≥ d_j + 1, বিরোধ। দুই ক্ষেত্রেই বিরোধ, তাই ধরে নেওয়াটি মিথ্যা। ∎

প্রমাণের ভেতরের তথ্যটি আরও শক্ত: আলাদা দুটি পদের label কখনো সমান হয় না, শর্ত ছাড়াই। নিচের stepper একটি ১০ পদের ক্রমে (n = 3, তাই n² + 1 = 10) label বসায়, আর দেখায় কীভাবে দৈর্ঘ্য 4-এর subsequence বেরিয়ে আসে।

1a₁ = 5   (i, d) = (1, 1)2a₂ = 9   (2, 1)3a₃ = 2   (1, 2)4a₄ = 7   (2, 2)5a₅ = 1   (1, 3)6a₆ = 8   (3, 2)7a₇ = 3   (2, 3)8a₈ = 10  (4, 1)9a₉ = 6   (3, 3)10a₁₀ = 4  (3, 4)

চলক

এ পর্যন্ত বড় i
এ পর্যন্ত বড় d
পাওয়া ক্রম

প্রস্তুতি। 10টি ভিন্ন সংখ্যা, n = 3. উপপাদ্য বলে দৈর্ঘ্য 4-এর monotone subsequence আছে। প্রতিটি পদে (i, d) label বসাব, বাঁ থেকে ডানে।
5, 9, 2. 5 একা: (1, 1). 9 > 5, তাই 5, 9: i = 2; d = 1. 2 দুজনের চেয়েই ছোট: i = 1, আর 5, 2 বা 9, 2-এ d = 2.
7, 1, 8. 7: 5, 7 বা 2, 7 থেকে i = 2; 9, 7 থেকে d = 2. 1: 9, 2, 1-এ d = 3. 8: 5, 7, 8-এ i = 3; 9, 8-এ d = 2.
3, 10. 3: 2, 3 বা 1, 3-এ i = 2; 9, 7, 3-এ d = 3. 10: 8-এর i = 3-এর পরে বসে, তাই i = 4. পাওয়া গেল 5, 7, 8, 10 ↑.
6, 4. 6: 2, 3, 6-এ i = 3, আর 9, 7, 6-এ d = 3. 4: 2, 3, 4-এ i = 3, আর 9, 7, 6, 4-এ d = 4. পাওয়া গেল 9, 7, 6, 4 ↓.
শিক্ষা। দশটি label (1,1), (2,1), (1,2), (2,2), (1,3), (3,2), (2,3), (4,1), (3,3), (3,4) সব আলাদা। i, d ≤ 3 হলে জোড়া মাত্র 9টি হতো, দশটি আলাদা label অসম্ভব।

উপপাদ্যটি নিখুঁত: n²টি পদে নিশ্চয়তা নেই। n = 3-এ 3, 2, 1, 6, 5, 4, 9, 8, 7 দেখুন: তিনটি করে ক্রমশ কমা খণ্ড, খণ্ডগুলো ক্রমশ বড়। increasing subsequence প্রতিটি খণ্ড থেকে বড়জোর একটি নিতে পারে (দৈর্ঘ্য ≤ 3), decreasing subsequence একটি খণ্ডের ভেতরেই থাকে (দৈর্ঘ্য ≤ 3). নিচের ব্লক এলোমেলো ক্রমে উপপাদ্যটি পরীক্ষা করে, প্রতিটি ক্ষেত্রে একটি দীর্ঘতম monotone subsequence খুঁজে বের করে, আর এই “ঠিক সীমার” উদাহরণও চালায়।

import random
random.seed(1935)

def longest(seq, up=True):
    """One longest increasing (up=True) or decreasing subsequence."""
    L, prev = [], []                    # L[k] = longest one ending at seq[k]
    for k, x in enumerate(seq):
        js = [j for j in range(k) if (seq[j] < x) == up]
        j = max(js, key=lambda j: L[j], default=None)
        L.append(1 if j is None else L[j] + 1)
        prev.append(j)
    k = max(range(len(seq)), key=L.__getitem__)
    path = []
    while k is not None:
        path.append(seq[k])
        k = prev[k]
    return path[::-1]

seq = [5, 9, 2, 7, 1, 8, 3, 10, 6, 4]
print("up:", longest(seq), " down:", longest(seq, False))

for n in (2, 3, 4, 5, 6):
    m, worst = n * n + 1, n * n + 1
    for _ in range(400):
        s = random.sample(range(1000), m)
        best = max(len(longest(s)), len(longest(s, False)))
        assert best >= n + 1, s         # would be a counterexample
        worst = min(worst, best)
    print(f"n={n}: 400 random sequences of {m:2} terms, smallest best = {worst} (theorem: >= {n + 1})")

for n in (3, 4):                        # n*n terms with no run of n + 1
    tight = [b * n + n - i for b in range(n) for i in range(n)]
    print(f"{n * n} terms:", tight, "->", len(longest(tight)), len(longest(tight, False)))

আসল আউটপুট (ব্রাউজারের Python):

up: [5, 7, 8, 10]  down: [9, 7, 6, 4]
n=2: 400 random sequences of  5 terms, smallest best = 3 (theorem: >= 3)
n=3: 400 random sequences of 10 terms, smallest best = 4 (theorem: >= 4)
n=4: 400 random sequences of 17 terms, smallest best = 5 (theorem: >= 5)
n=5: 400 random sequences of 26 terms, smallest best = 6 (theorem: >= 6)
n=6: 400 random sequences of 37 terms, smallest best = 8 (theorem: >= 7)
9 terms: [3, 2, 1, 6, 5, 4, 9, 8, 7] -> 3 3
16 terms: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13] -> 4 4

প্রথম লাইন stepper-এর দুটি উত্তরই দিয়েছে। L[k] ঠিক label i_k (বা d_k), আর prev দিয়ে পেছনে হেঁটে subsequence-টি তৈরি হয়। n = 2 থেকে 5-এ ৪০০টি এলোমেলো ক্রমের অন্তত একটিতে সেরা দৈর্ঘ্য ঠিক n + 1, অর্থাৎ উপপাদ্যের সীমা প্রায়ই ঠিক ছোঁয়া হয়; n = 6-এ এই ৪০০টির সবচেয়ে খারাপটিতেও 8 মিলেছে, যা 7-এর বেশি। কোনো assert ব্যর্থ হয়নি। শেষ দুই লাইনে n² পদের বিশেষ ক্রমে দুই দিকেই দৈর্ঘ্য মাত্র n: এক পদ কম হলেই নিশ্চয়তা যায়। এই O(n²) DP-টিই longest increasing subsequence সমস্যার সরল সমাধান; O(n log n) রূপ DSA কোর্সের পর্ব ৫৩-এ আছে।

৫ · কম্পিউটার বিজ্ঞানে pigeonhole — hash আর compression

Hash collision এড়ানো যায় না

বাজারঘর লাখ লাখ ক্রেতার id-কে একটি hash function h দিয়ে m-টি bucket-এ ভাগ করে (পর্ব ২৬-এ h(k) = k mod m দেখেছেন)। সম্ভাব্য key-এর সেট U যদি m-এর চেয়ে বড় হয়, তবে মৌলিক নীতিতে দুটি আলাদা key একই bucket পাবে: এটিই collision. Generalized রূপ আরও বলে: কোনো একটি bucket-এ অন্তত ⌈|U|/m⌉টি সম্ভাব্য key পড়ে। ফলে যে কেউ hash function জানেন, তিনি সেই bucket-এর key-গুলো বেছে পাঠিয়ে টেবিলটিকে একটি লম্বা তালিকা বানিয়ে দিতে পারেন। এই কারণে বাস্তবের hash table collision এড়ায় না, সামলায় (chaining বা probing), আর কখনো কখনো hash function-এ এলোমেলো seed ব্যবহার করে। কোডের দিক DSA কোর্সের পর্ব ৩২-এ, আর cryptographic hash-এর দিক Cybersecurity কোর্সের পর্ব ০৯-এ।

কোনো compression সব ফাইল ছোট করতে পারে না

Lossless compression (যেমন zip) একটি ফাইলকে ছোট করে, আর খুললে হুবহু আগের ফাইল ফেরত দেয়। গণিতের ভাষায় compressor একটি ফাংশন C: {সব bit string} → {সব bit string}, আর হুবহু ফেরত পেতে হলে C অবশ্যই one-to-one, নইলে দুটি আলাদা ফাইলের একই সংকুচিত রূপ হতো আর decompressor বুঝত না কোনটি ফেরত দেবে।

উপপাদ্য ৫.১ (compression-এর সীমা)

n ≥ 1. কোনো one-to-one ফাংশন C দৈর্ঘ্য n-এর প্রতিটি bit string-কে দৈর্ঘ্য n-এর চেয়ে ছোট bit string-এ নিতে পারে না।

প্রমাণ:

দৈর্ঘ্য n-এর bit string 2ⁿটি। — গুণের নিয়ম (পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”)
দৈর্ঘ্য 0, 1, …, n − 1-এর bit string মোট 2⁰ + 2¹ + ⋯ + 2ⁿ⁻¹ = 2ⁿ − 1টি (ফাঁকা string-সহ)। — যোগের নিয়ম আর geometric sum, পর্ব ১৭
2ⁿ > 2ⁿ − 1, তাই দৈর্ঘ্য n-এর string থেকে ছোট string-এর সেটে কোনো ফাংশন one-to-one নয়। ∎ — উপপাদ্য ১.১, ফাংশনের রূপ

উপপাদ্য ৫.২ (কিছু ছোট হলে কিছু বড় হবেই)

একটি one-to-one C যদি অন্তত একটি bit string-কে ছোট করে, তবে অন্তত একটি bit string-কে বড়ও করে।

প্রমাণ:

ধরি, C কোনো string বড় করে না। যে string ছোট হয়, তাদের মধ্যে সবচেয়ে কম দৈর্ঘ্য m নিন, আর x এমন একটি, |x| = m. — বিরোধের জন্য ধরে নেওয়া; well-ordering
দৈর্ঘ্য m-এর কম প্রতিটি string w ছোট হয় না (m সবচেয়ে কম) আর বড়ও হয় না, তাই |C(w)| = |w|. — m-এর সংজ্ঞা
প্রতিটি দৈর্ঘ্য ℓ < m-এ C দৈর্ঘ্য ℓ-এর 2^ℓটি string-কে দৈর্ঘ্য ℓ-এর 2^ℓটি string-এ one-to-one নেয়; সমান মাপের সসীম সেটে তা onto-ও (পর্ব ১৬)। তাই দৈর্ঘ্য m-এর কম সব string ইতিমধ্যে কারো ছবি। — সসীম সেটে one-to-one ⇒ onto
কিন্তু |C(x)| < m, তাই C(x) = C(w) কোনো w-এর জন্য, যেখানে |w| < m, অর্থাৎ w ≠ x. C one-to-one নয়, বিরোধ। ∎

অর্থাৎ “সব ফাইল অর্ধেক করে দেয়” এমন সফটওয়্যারের দাবি গাণিতিকভাবে অসম্ভব, আর বারবার compress করে একটি ফাইলকে এক byte-এ নামানোর গল্পও। একই গণনা আরও বলে: দৈর্ঘ্য n-এর string-এর মধ্যে বড়জোর 2^n−c+1 − 1টি অন্তত c bit ছোট হতে পারে, অর্থাৎ মোটের 2^1−c অংশেরও কম। Compression কাজ করে কারণ বাস্তব ফাইল এলোমেলো নয়, তাতে পুনরাবৃত্তি আর ছাঁচ থাকে। নিচের ব্লক গণনাটি দেখায়, তারপর একটি সত্যিকারের compressor, zlib (DEFLATE, zip-এর মূল পদ্ধতি) চালায়।

import random, zlib
random.seed(26)

for n in (1, 2, 3, 8, 16):
    shorter = 2 ** n - 1                # lengths 0..n-1: 1 + 2 + ... + 2^(n-1)
    print(f"n={n:2}: {2 ** n:5} bit strings of length n, only {shorter:5} shorter ones")

n = 16                                  # how many can lose at least c bits?
for c in (2, 8, 12):
    room = 2 ** (n - c + 1) - 1         # strings of length <= n - c
    print(f"  lose >= {c:2} bits: at most {room:5} of {2 ** n} ({room / 2 ** n:.4f})")

data = {
    "order log": b"ORDER;Dhaka;rice;2kg\n" * 200,
    "random bytes": random.randbytes(4200),
}
for name, d in data.items():            # a real compressor: zlib (DEFLATE)
    print(f"{name:12}: {len(d)} bytes -> {len(zlib.compress(d, 9))} bytes")

grew = sum(len(zlib.compress(bytes([x]), 9)) > 1 for x in range(256))
print("all 256 one-byte inputs: output longer than input for", grew)

আসল আউটপুট (ব্রাউজারের Python):

n= 1:     2 bit strings of length n, only     1 shorter ones
n= 2:     4 bit strings of length n, only     3 shorter ones
n= 3:     8 bit strings of length n, only     7 shorter ones
n= 8:   256 bit strings of length n, only   255 shorter ones
n=16: 65536 bit strings of length n, only 65535 shorter ones
  lose >=  2 bits: at most 32767 of 65536 (0.5000)
  lose >=  8 bits: at most   511 of 65536 (0.0078)
  lose >= 12 bits: at most    31 of 65536 (0.0005)
order log   : 4200 bytes -> 60 bytes
random bytes: 4200 bytes -> 4211 bytes
all 256 one-byte inputs: output longer than input for 256

প্রথম পাঁচ লাইনে উপপাদ্য ৫.১-এর গণনা: সবসময় ঠিক একটি জায়গা কম পড়ে। পরের তিন লাইনে, ১৬ bit-এর string-এর বড়জোর অর্ধেক 2 bit ছোট হতে পারে, আর 12 bit ছোট হতে পারে মাত্র 31টি। তারপর বাস্তব: একই লাইন ২০০ বার লেখা অর্ডার-লগ 4200 byte থেকে খুব ছোট হয়ে গেছে, কারণ তাতে পুনরাবৃত্তি ভরা। কিন্তু এলোমেলো byte-এ zlib উল্টো কয়েক byte বাড়িয়েছে: সংকোচনের মতো কিছু পায়নি, আর নিজের header ও কাঠামোর খরচ যোগ করেছে। শেষ লাইনে প্রতিটি এক-byte ইনপুটই বড় হয়েছে। উপপাদ্য ৫.২ এটিকে অনিবার্য বলে: কোনো ফাইল ছোট করতে পারলে কোনো ফাইল বড় করতেই হবে। ফাইলে কতটা “ছাঁচ” আছে, তার মাপ entropy, যা AI Foundations কোর্সের পর্ব ৩৮-এ, আর একটি বাস্তব compression algorithm DSA কোর্সের পর্ব ৫১-এ।

৬ · Ramsey-র এক ঝলক আর “আছে” বনাম “খুঁজে পাওয়া”

বাজারঘরের যেকোনো ছয়জন রাইডার নিন। প্রতি দুজন হয় আগে একসঙ্গে কাজ করেছেন, নয়তো করেননি। দাবি: ছয়জনের মধ্যে এমন তিনজন সবসময় আছেন, যাঁরা হয় পরস্পর সবাই সহকর্মী, নয়তো পরস্পর সবাই অপরিচিত। পাঁচজনে এটি নিশ্চিত নয়। গ্রাফের ভাষায় (graph; বিস্তারিত মডিউল ১০-এ, পর্ব ৫৭ থেকে): ছয়জন হলো complete graph K₆-এর ৬টি vertex, প্রতিটি জোড়ার মধ্যে একটি edge, আর edge-এ লাল (সহকর্মী) বা নীল (অপরিচিত) রং।

উপপাদ্য ৬.১ (R(3,3) ≤ 6)

K₆-এর ১৫টি edge-কে লাল আর নীল, দুই রঙে যেভাবেই রাঙানো হোক, এমন একটি ত্রিভুজ থাকবে যার তিনটি edge একই রঙের।

প্রমাণ:

যেকোনো একটি vertex v নিন। v থেকে বাকি ৫ জনের দিকে ৫টি edge, রং ২টি। — বস্তু ৫, বাক্স ২
Generalized pigeonhole-এ ⌈5/2⌉ = 3: অন্তত ৩টি edge একই রঙের। সাধারণতা না হারিয়ে ধরি vx, vy, vz লাল। — উপপাদ্য ২.১
যদি xy, xz, yz-এর কোনো একটি লাল হয়, ধরি xy, তবে v, x, y একটি লাল ত্রিভুজ। — ক্ষেত্র ১
নইলে xy, xz, yz তিনটিই নীল, আর x, y, z একটি নীল ত্রিভুজ। ∎ — ক্ষেত্র ২

আর ৫ জনে নিশ্চয়তা নেই: পাঁচজনকে একটি বৃত্তে বসিয়ে পাশাপাশি দুজনের edge লাল (পঞ্চভুজের বাহু) আর বাকিগুলো নীল (কর্ণ) করলে লাল edge একটি ৫-চক্র, আর নীল edge-ও একটি ৫-চক্র (তারকা), কোনোটিতেই ত্রিভুজ নেই। দুটি তথ্য মিলে বলে Ramsey number R(3,3) = 6: সবচেয়ে ছোট N, যাতে K_N-এর প্রতিটি দুই-রঙা রঙে একরঙা ত্রিভুজ থাকে।

K₅: একরঙা ত্রিভুজ ছাড়া রং

লাল: পঞ্চভুজের বাহু; নীল (ড্যাশ): কর্ণ, যা একটি তারকা। কোনো তিনটি বিন্দুর তিনটি edge-ই একই রঙের নয়।

দুটি দাবিই একটি ছোট ব্লক সব রং পরীক্ষা করে যাচাই করতে পারে: K₅-এর 2¹⁰ = 1024টি রং আর K₆-এর 2¹⁵ = 32768টি রং। প্রতিটি রং একটি সংখ্যার bit, আর প্রতিটি ত্রিভুজে তিনটি bit-এর যোগফল 0 বা 3 হলে সেটি একরঙা।

from itertools import combinations

def colourings_without_triangle(n):
    """Count red/blue colourings of the edges of K_n with no one-colour triangle."""
    edges = list(combinations(range(n), 2))
    pos = {e: i for i, e in enumerate(edges)}
    tris = [(pos[a, b], pos[a, c], pos[b, c]) for a, b, c in combinations(range(n), 3)]
    good, example = 0, None
    for mask in range(2 ** len(edges)):          # bit i = colour of edge i
        if all(0 < ((mask >> x) & 1) + ((mask >> y) & 1) + ((mask >> z) & 1) < 3
               for x, y, z in tris):
            good += 1
            example = example or [e for e in edges if (mask >> pos[e]) & 1]
    return 2 ** len(edges), good, example

for n in (3, 4, 5, 6):
    total, good, ex = colourings_without_triangle(n)
    print(f"K{n}: {total:5} colourings, {good:3} without a one-colour triangle")
    if n == 5:
        print("   one good K5 colouring, blue edges:", ex)

আসল আউটপুট (ব্রাউজারের Python):

K3:     8 colourings,   6 without a one-colour triangle
K4:    64 colourings,  18 without a one-colour triangle
K5:  1024 colourings,  12 without a one-colour triangle
   one good K5 colouring, blue edges: [(0, 3), (0, 4), (1, 2), (1, 4), (2, 3)]
K6: 32768 colourings,   0 without a one-colour triangle

K₅-এ ১২টি “ভালো” রং আছে, আর প্রথমটির নীল edge 0–3–2–1–4–0 একটি ৫-চক্র, অর্থাৎ ছবির পঞ্চভুজই, শুধু বিন্দুর নাম বদলে। K₆-এ ৩২৭৬৮টির একটিও ভালো নয়: উপপাদ্য ৬.১-এর সম্পূর্ণ যাচাই। লক্ষ করুন দুটি ভিন্ন ধরনের নিশ্চয়তা: প্রমাণ চার লাইনে সব রঙের কথা বলে; brute force একই কথা বলে ৩২৭৬৮টি ক্ষেত্র গুনে। N বাড়লে 2^N(N−1)/2 দ্রুত অসম্ভব হয়ে যায়: K₁₀-এই 2⁴⁵টি রং। তখন শুধু প্রমাণই চলে।

অস্তিত্ব আছে, কিন্তু কোথায়?

Pigeonhole-এর প্রমাণ সাধারণত non-constructive: বলে যে দুটি বস্তু একই বাক্সে আছে, কিন্তু কোন দুটি, তা দেখায় না (পর্ব ০৯). কখনো প্রমাণটিকে সহজেই algorithm বানানো যায়: বিভাজ্য block-এর জন্য বাক্সগুলো একে একে ভরতে থাকলে বড়জোর n + 1 ধাপে জোড়া মেলে। কখনো যায় না। SHA-256 প্রতিটি ইনপুটকে 256 bit-এ নেয়, আর ইনপুট অসীম সংখ্যক, তাই collision অসীম সংখ্যক আছে; তবু আজ পর্যন্ত একটিও প্রকাশ্যে পাওয়া গেছে বলে জানা নেই, কারণ সেরা জানা সাধারণ পদ্ধতিতে মোটামুটি 2¹²⁸টি hash লাগে (birthday সীমা, পর্ব ৪২)। Cryptographic hash-এর নিরাপত্তা ঠিক এই দূরত্বের ওপর দাঁড়িয়ে: অস্তিত্ব গাণিতিক সত্য, খুঁজে পাওয়া কার্যত অসম্ভব।

৭ · পরীক্ষার অঙ্ক আর দুটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় pigeonhole-এর যে ধাঁচের অঙ্ক আসে, তার পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: গ্রেড পাঁচটি (A, B, C, D, F). কমপক্ষে কতজন পরীক্ষার্থী হলে নিশ্চিত যে অন্তত ৬ জন একই গ্রেড পেয়েছেন?

বাক্স k = 5 (গ্রেড), চাই r = 6. সূত্র N = k(r − 1) + 1.
N = 5 · 5 + 1 = 26. যাচাই: ⌈26/5⌉ = 6 ✓.
২৫ জনে যথেষ্ট নয়: প্রতি গ্রেডে ঠিক ৫ জন হলে কোনো গ্রেডে ৬ জন নেই। তাই উত্তর ২৬.

অঙ্ক ২: বাজারঘরের ডেলিভারি এলাকা একটি 2 km × 2 km বর্গ। এর ভেতরে যেকোনো ৫টি ডেলিভারি ঠিকানা থাকলে দেখান, দুটির দূরত্ব বড়জোর √2 km.

বর্গটিকে মাঝখান দিয়ে দুটি রেখা টেনে চারটি 1 km × 1 km বর্গে ভাগ করুন (সীমারেখার বিন্দু যেকোনো একটি পাশের বর্গে ধরুন)। — বাক্স ৪টি
৫টি ঠিকানা, ৪টি ছোট বর্গ: একটি ছোট বর্গে অন্তত দুটি ঠিকানা। — pigeonhole
1 km বাহুর বর্গের ভেতরের দুটি বিন্দুর দূরত্ব বড়জোর তার কর্ণ, √(1 + 1) = √2 ≈ 1.414 km. ∎

প্রমাণের ভুল ধরুন ১: “ছোট করে ভাগ”

একজন লিখলেন: “১০০টি অর্ডার ৭ দিনে। গড় 100/7 ≈ 14.28, আর অর্ডার পূর্ণসংখ্যা, তাই ⌊14.28⌋ = 14. অতএব কোনো একদিনে অন্তত ১৪টি অর্ডার, আর এর বেশি কিছু বলা যায় না।” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: দাবিটি মিথ্যা নয়, কিন্তু দুর্বল, আর শেষ বাক্যটি ভুল। সঠিক সীমা ceiling দিয়ে: ⌈100/7⌉ = 15, কারণ সব দিন ১৪ বা কম হলে মোট বড়জোর ৯৮. floor ব্যবহার গড়ের নিচের দিকে গোল করে, যা “অন্তত একটি বাক্সে” প্রশ্নের ভুল দিক। পরীক্ষায় এই ভুলে পূর্ণ নম্বর যায় না, তাই প্রতিবার উল্টোটা ধরে মোট গুনে যাচাই করুন।

প্রমাণের ভুল ধরুন ২: “নয় পদেই যথেষ্ট”

আরেকজন লিখলেন: “দাবি: ৯টি ভিন্ন সংখ্যার যেকোনো ক্রমে দৈর্ঘ্য ৪-এর monotone subsequence আছে। প্রমাণ: প্রতিটি পদে (i, d) label দিই। দৈর্ঘ্য ৪ না থাকলে i, d ∈ {1, 2, 3}, তাই ৯টি জোড়া। পদ ৯টি, জোড়া ৯টি, তাই দুটি পদের label সমান, যা অসম্ভব। ∎”

ভুল কোথায়: pigeonhole-এ বস্তু বাক্সের চেয়ে বেশি হতে হয়। ৯টি পদ আর ৯টি বাক্সে প্রতিটি পদ নিজের আলাদা বাক্সে বসতে পারে, কোনো সংঘর্ষ লাগে না। দাবিটি নিজেও মিথ্যা: counterexample 3, 2, 1, 6, 5, 4, 9, 8, 7, যার দুই দিকেই সর্বোচ্চ দৈর্ঘ্য ৩ (ব্লক ২-এর শেষ লাইন)। n² + 1 সংখ্যাটির “+ 1” প্রমাণের প্রাণ।

আরও গভীরে: Erdős আর Szekeres-এর ১৯৩৫ সালের প্রবন্ধের আসল প্রশ্ন ছিল জ্যামিতিক: সমতলে সাধারণ অবস্থানে কতগুলো বিন্দু থাকলে n-টি বিন্দু একটি উত্তল (convex) বহুভুজ গঠন করবেই? Esther Klein দেখিয়েছিলেন ৫টি বিন্দুতে একটি উত্তল চতুর্ভুজ থাকে; এই প্রশ্নটি “Happy Ending problem” নামে পরিচিত, কারণ এ নিয়ে আলোচনার সূত্রে Klein আর Szekeres-এর বিয়ে হয় বলে গল্প প্রচলিত। অনুমান করা হয় উত্তরটি 2ⁿ⁻² + 1, যা এখনো সাধারণভাবে প্রমাণিত নয় বলে জানা যায়। আর এলোমেলো ক্রমে দীর্ঘতম increasing subsequence-এর দৈর্ঘ্য মোটামুটি 2√N, এই ফল আর তার সূক্ষ্ম বণ্টন বিংশ শতকের শেষভাগের গুরুত্বপূর্ণ গবেষণা (Vershik–Kerov, Logan–Shepp, Baik–Deift–Johansson).

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

১০০ জনের মধ্যে কমপক্ষে কতজন একই মাসে জন্মেছেন? ⌈100/12⌉ = 9 জন।
যেকোনো ৫টি পূর্ণসংখ্যায় দুটির পার্থক্য কি 4 দিয়ে বিভাজ্য? হ্যাঁ, ভাগশেষ mod 4 মাত্র ৪টি।
1..20 থেকে কমপক্ষে কয়টি সংখ্যা বাছলে একটি অন্যটিকে ভাগ করবেই? ১১টি; ১০টি {11, …, 20}-এ যথেষ্ট নয়।
কেন কোনো compressor সব ফাইল ছোট করতে পারে না? দৈর্ঘ্য n-এর 2ⁿটি string, ছোট string 2ⁿ − 1টি; one-to-one অসম্ভব।
ছয়জনের যেকোনো দলে কী নিশ্চিত? তিনজন পরস্পর পরিচিত বা তিনজন পরস্পর অপরিচিত (R(3,3) = 6).

৮ · AI-এর যুগে — pigeonhole যুক্তি যাচাই

Pigeonhole প্রমাণ ছোট, তাই AI সহকারী সেগুলো দ্রুত লিখে দেয়। কিন্তু ছোট প্রমাণে একটি ভুল পুরো প্রমাণকে মিথ্যা করে দেয়, আর AI-এর কয়েকটি ভুল নিয়মিত দেখা যায়:

AI-এর ভুল	কীভাবে ধরবেন
বস্তু আর বাক্স সমান সংখ্যক রেখেই “pigeonhole অনুযায়ী” সংঘর্ষ দাবি (off-by-one)	বস্তু > বাক্স কি না নিজে গুনুন; ঠিক সীমায় একটি counterexample খুঁজুন
⌈N/k⌉-এর বদলে ⌊N/k⌋ বা N/k − 1, বা k(r − 1) + 1-এর বদলে kr	উল্টোটা ধরে মোট গুনুন; সমান বণ্টনের উদাহরণ বানিয়ে পরীক্ষা করুন
বাক্সগুলো সব ক্ষেত্র ঢাকে না (যেমন ভাগশেষ 0 বাদ পড়া, বা S₀ = 0 ভুলে যাওয়া)	প্রতিটি বস্তু ঠিক একটি বাক্সে যায় কি না, অর্থাৎ বাক্স বাছাই একটি ফাংশন কি না, দেখুন
“দুটি একই বাক্সে” থেকে শর্ত ছাড়া সিদ্ধান্ত, যেমন Erdős–Szekeres-এ পদ ভিন্ন হওয়ার শর্ত বাদ	উপপাদ্যের পূর্ণ বিবৃতি আর শর্ত চেয়ে নিন; সমান পদ দিয়ে counterexample চেষ্টা করুন
সম্ভাবনা আর নিশ্চয়তা গুলিয়ে ফেলা (২৩ জনে জন্মদিন “নিশ্চিত” মেলে)	pigeonhole নিশ্চয়তা দেয় ৩৬৭ জনে; ২৩ জনের কথা সম্ভাবনার
বানানো ইতিহাস বা উৎস: ভুল সাল, অস্তিত্বহীন বই, “সব ফাইল ছোট করে” এমন compressor-এর গল্প	Dirichlet, Erdős–Szekeres ১৯৩৫-এর মতো তথ্য বিশ্বস্ত উৎসে মেলান; অসম্ভব দাবিতে উপপাদ্য ৫.১ মনে করুন

AI-এর কাছে pigeonhole প্রমাণ বা হিসাব চাইলে এমন কাঠামো দিন, যাতে প্রতিটি অংশ আলাদা করে যাচাই করা যায়:

নিচের দাবিটি pigeonhole principle দিয়ে প্রমাণ করো: দাবি: [যেমন যেকোনো n-টি পূর্ণসংখ্যায় পাশাপাশি একটি block-এর যোগফল n দিয়ে বিভাজ্য] ১. প্রথমে স্পষ্ট লেখো: বস্তু কী, কয়টি; বাক্স কী, কয়টি; প্রতিটি বস্তু কোন নিয়মে ঠিক একটি বাক্সে যায়। ২. মৌলিক না generalized রূপ ব্যবহার করছ, বলো, আর ⌈N/k⌉-এর মান হিসাব করে দেখাও। ৩. "একই বাক্সে দুটি বস্তু" থেকে সিদ্ধান্তে যাওয়ার প্রতিটি ধাপের কারণ লেখো, আর প্রতিটি শর্ত (ভিন্ন সংখ্যা, n ≥ 1 ইত্যাদি) কোথায় লাগল, দেখাও। ৪. সীমাটি যে নিখুঁত, তার একটি উদাহরণ দাও: এক কম বস্তুতে দাবিটি ভাঙে এমন নির্দিষ্ট সংখ্যা। ৫. ছোট n-এ দাবিটি brute force করে পরীক্ষার একটি Python কোড দাও (শুধু standard library).

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

বস্তুর সংখ্যা বাক্সের চেয়ে সত্যিই বেশি, নিজে গুনে দেখেছি
প্রতিটি বস্তু ঠিক একটি বাক্সে যায়, কোনো ক্ষেত্র বাদ পড়েনি
⌈N/k⌉ বা k(r − 1) + 1 নিজে হিসাব করেছি, আর এক কম বস্তুর counterexample বানিয়েছি
উপপাদ্যের সব শর্ত (ভিন্ন পদ, ধনাত্মক n) প্রমাণে ব্যবহৃত হয়েছে কি না দেখেছি
ছোট n-এ Python-এ brute force আর এলোমেলো ইনপুটে দাবিটি চালিয়েছি
ইতিহাস আর উৎস (সাল, নাম, বই) বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Pigeonhole-এর প্রায় প্রতিটি দাবি ছোট n-এ এক সেকেন্ডে brute force করা যায়, আর প্রতিটির একটি “ঠিক সীমার” উদাহরণ থাকে। AI-এর প্রমাণ পেলে আগে সেই দুটি পরীক্ষা চালান, তারপর ধাপগুলো পড়ুন।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১এত স্পষ্ট একটি কথা, “খোপের চেয়ে কবুতর বেশি হলে কোনো খোপে দুটি”, গণিতের ইতিহাসে এত শক্তিশালী হাতিয়ার হলো কীভাবে? Dirichlet এটি কোথায় ব্যবহার করেছিলেন?

নীতিটির শক্তি এর বিবৃতিতে নয়, প্রয়োগের কৌশলে। সবচেয়ে বিখ্যাত পুরোনো প্রয়োগ Dirichlet-এর approximation theorem, যা সাধারণত ১৮৪০-এর দশকের কাজ বলে উল্লেখ করা হয়। প্রশ্নটি ছিল: একটি অমূলদ সংখ্যা α-কে (যেমন √2) কত ভালোভাবে একটি ভগ্নাংশ p/q দিয়ে আসন্ন করা যায়? Dirichlet দেখান, যেকোনো ধনাত্মক পূর্ণসংখ্যা N-এর জন্য এমন q আছে, 1 ≤ q ≤ N, যাতে |qα − p| < 1/N কোনো পূর্ণসংখ্যা p-এর জন্য। প্রমাণে বস্তু হলো 0, α, 2α, …, Nα-এর ভগ্নাংশ অংশ, অর্থাৎ N + 1টি সংখ্যা [0, 1) ব্যবধিতে, আর বাক্স হলো ব্যবধিটির N-টি সমান টুকরো। দুটি একই টুকরোয় পড়ে, তাদের পার্থক্য থেকে q আর p বেরিয়ে আসে। এখান থেকেই আসে |α − p/q| < 1/q² ধরনের অসীম সংখ্যক ভগ্নাংশ, যা সংখ্যাতত্ত্বের Diophantine approximation শাখার ভিত্তি।

এই প্রমাণে কয়েকটি শিক্ষা আছে। প্রথমত, বাক্স সবসময় চোখের সামনে থাকে না; Dirichlet-কে একটি অবিচ্ছিন্ন ব্যবধিকে টুকরো করে বাক্স বানাতে হয়েছিল, ঠিক যেমন এই পর্বের অঙ্ক ২-এ বর্গটিকে চার ভাগ করা হয়েছে। দ্বিতীয়ত, ফলটি অস্তিত্বের: q আছে, কিন্তু কোনটি, তা সরাসরি বলে না; তা খুঁজতে পরে continued fraction-এর মতো constructive পদ্ধতি লাগে। তৃতীয়ত, সরল যুক্তি প্রায়ই সেরা সম্ভাব্য সীমা দেয়, আর তা উন্নত করা কঠিন গবেষণার প্রশ্ন হয়ে দাঁড়ায়।

নামের ইতিহাসও শিক্ষণীয়। জার্মানে “Schubfach” মানে ড্রয়ার বা খোপ, আর ফরাসি ও রুশ পাঠ্যবইয়ে এটি এখনো প্রায়ই “Dirichlet-এর নীতি” বা “ড্রয়ারের নীতি” নামে পরিচিত বলে জানা যায়। তবে Dirichlet-এর আগেও যুক্তিটি ব্যবহৃত হয়েছে বলে ইতিহাসবিদেরা দেখিয়েছেন, তাই “আবিষ্কারক” বলার চেয়ে “জনপ্রিয় করা ব্যবহারকারী” বলা নিরাপদ। ইংরেজি “pigeonhole” শব্দটি অফিসের চিঠির খোপ বোঝায়, পায়রার ঘর থেকে এসেছে।

মূল উপলব্ধি: pigeonhole-এর কঠিন অংশ নীতি নয়, সমস্যার ভেতরে সঠিক “বাক্স” আবিষ্কার করা; সেই আবিষ্কারটিই প্রমাণের সৃজনশীল ধাপ।

প্র ০২Hash function-এ collision থাকা নিশ্চিত, তবু কেন একে “collision resistant” বলা হয়? SHA-1-এর ইতিহাস “অস্তিত্ব” আর “খুঁজে পাওয়া”-র পার্থক্য সম্পর্কে কী শেখায়?

SHA-1 যেকোনো দৈর্ঘ্যের ইনপুটকে 160 bit-এ নেয়। ইনপুট অসীম সংখ্যক, আউটপুট 2¹⁶⁰টি, তাই pigeonhole অনুযায়ী অসীম সংখ্যক collision আছে, আর generalized রূপ বলে কিছু আউটপুটের পেছনে অসীম সংখ্যক ইনপুট। “Collision resistant” মানে তাই “collision নেই” নয়, বরং “বাস্তব সময়ে কেউ একটি collision খুঁজে বের করতে পারবেন না”। এটি গাণিতিক উপপাদ্য নয়, একটি কঠিনতার অনুমান। এলোমেলো চেষ্টায় n-bit hash-এ মোটামুটি 2^n/2টি চেষ্টায় collision আশা করা যায় (birthday সীমা, পর্ব ৪২-এর বিষয়), তাই SHA-1-এর লক্ষ্য ছিল প্রায় 2⁸⁰টি কাজের চেয়ে সহজ কোনো পথ না থাকা।

ইতিহাস দেখায়, এই অনুমান ভাঙতে পারে। ২০০৫ সালে Xiaoyun Wang ও সহকর্মীরা দেখান, SHA-1-এ collision খুঁজতে 2⁸⁰-এর চেয়ে অনেক কম কাজ লাগে বলে প্রকাশিত হয়। এরপর নির্দেশিকাগুলো ধীরে ধীরে SHA-1 থেকে সরে যেতে বলে। ২০১৭ সালে আমস্টারডামের গবেষণা প্রতিষ্ঠান CWI আর একটি বড় প্রযুক্তি প্রতিষ্ঠানের গবেষকেরা প্রথম প্রকাশ্য SHA-1 collision দেখান: দুটি আলাদা PDF ফাইল, একই SHA-1 মান, যার জন্য বিপুল পরিমাণ হিসাব লেগেছিল বলে জানানো হয়। অর্থাৎ pigeonhole যা ১৯৯৫ সালেই নিশ্চিত করেছিল, তা “খুঁজে পাওয়া” হয়ে উঠতে বাইশ বছর আর নতুন গাণিতিক কৌশল লেগেছে।

এখান থেকে একটি তাত্ত্বিক প্রশ্নও আসে: যেসব সমস্যায় উত্তরের অস্তিত্ব pigeonhole নিশ্চিত করে, সেগুলোর কঠিনতা কেমন? Christos Papadimitriou ১৯৯৪ সালের একটি প্রবন্ধে এমন সমস্যার জন্য PPP (Polynomial Pigeonhole Principle) নামে একটি complexity class সংজ্ঞায়িত করেন বলে উল্লেখ করা হয়। সেখানে প্রশ্ন “জোড়া আছে কি?” নয়, কারণ উত্তর সবসময় হ্যাঁ; প্রশ্ন হলো “জোড়াটি দ্রুত দেখাতে পারবেন কি?”। Hash-এর ব্যবহারিক দিক Cybersecurity কোর্সের পর্ব ০৯-এ।

মূল উপলব্ধি: গণিত collision-এর অস্তিত্ব নিশ্চিত করে; নিরাপত্তা দাঁড়িয়ে থাকে শুধু খুঁজে পাওয়ার কঠিনতার ওপর, আর সেই কঠিনতা নতুন গবেষণায় কমে যেতে পারে।

প্র ০৩“আমাদের সফটওয়্যার যেকোনো ফাইলকে অর্ধেক করে দেয়, আর বারবার চালালে আরও ছোট হয়।” এমন দাবি শুনলে গণিত দিয়ে কীভাবে উত্তর দেবেন, আর তবু zip কেন বাস্তবে এত কাজের?

উপপাদ্য ৫.১ দাবিটিকে সরাসরি খণ্ডন করে। দৈর্ঘ্য n bit-এর ফাইল 2ⁿটি; অর্ধেক বা তার কম দৈর্ঘ্যের ফাইল মোট 2^n/2+1 − 1টির মতো (n জোড় হলে), যা 2ⁿ-এর তুলনায় নগণ্য। one-to-one ফাংশন বড় সেট থেকে ছোট সেটে যেতে পারে না, তাই বেশিরভাগ ফাইলকে অর্ধেক করা অসম্ভব। “বারবার চালালে আরও ছোট” দাবিটি আরও খারাপ: তা সত্য হলে যেকোনো ফাইল শেষে এক bit-এ নেমে আসত, আর এক bit দিয়ে মাত্র দুটি ফাইল আলাদা করা যায়। উপপাদ্য ৫.২ আরও বলে: যে compressor কোনো ফাইল ছোট করে, সে অবশ্যই কোনো ফাইল বড়ও করে। ব্লক ৩-এ zlib এলোমেলো byte-এ ঠিক তাই করেছে।

তাহলে zip কাজ করে কেন? কারণ আমরা যেসব ফাইল সত্যিই বানাই, যেমন লেখা, log, ছবি, সেগুলো সব সম্ভাব্য ফাইলের মধ্যে খুব ছোট, বিশেষ একটি অংশ, যেখানে পুনরাবৃত্তি আর ছাঁচ আছে। compressor সেই অংশকে ছোট করে, আর এলোমেলো দেখতে বিশাল বাকি অংশকে সামান্য বড় করে, যা আমরা প্রায় কখনো দেখি না। এই ধারণাকে আনুষ্ঠানিক রূপ দেয় Kolmogorov complexity: একটি string-এর জটিলতা হলো তাকে ছাপে এমন সবচেয়ে ছোট প্রোগ্রামের দৈর্ঘ্য। ১৯৬০-এর দশকে Ray Solomonoff, Andrey Kolmogorov আর Gregory Chaitin স্বাধীনভাবে এই ধারণা দেন বলে উল্লেখ করা হয়। একই গণনায় দেখা যায়, বেশিরভাগ string-এর Kolmogorov complexity তার দৈর্ঘ্যের প্রায় সমান: তারা “এলোমেলো”, সংকোচন-অযোগ্য।

অন্যদিকে, Claude Shannon ১৯৪৮ সালে দেখান যে একটি উৎসের গড় সংকোচনের সীমা তার entropy; এই দৃষ্টিভঙ্গি সম্ভাবনার, আর AI Foundations কোর্সের পর্ব ৩৮-এ আছে। দুটি দৃষ্টিভঙ্গি পরস্পরের পরিপূরক: pigeonhole বলে “সব ফাইল নয়”, entropy বলে “গড়ে কতটা”।

মূল উপলব্ধি: compression কোনো জাদু নয়, একটি বিনিময়: সাধারণ ফাইল ছোট করার দাম হিসেবে অস্বাভাবিক ফাইল বড় হয়; সব ফাইল ছোট করার দাবি গণনার একটি সরল ভুল।

প্র ০৪R(3,3) = 6 চার লাইনে প্রমাণ হলো। তাহলে R(5,5)-এর মান আজও অজানা কেন, আর Ramsey theory-র মূল বার্তা কী?

Frank Ramsey ১৯৩০ সালে গাণিতিক যুক্তিবিদ্যার একটি প্রবন্ধে দেখান যে যথেষ্ট বড় যেকোনো কাঠামোয় কিছু না কিছু শৃঙ্খলা অনিবার্য; সেখান থেকেই এই শাখার নাম। R(s, t) হলো সবচেয়ে ছোট N, যাতে K_N-এর প্রতিটি লাল-নীল রঙে একটি লাল K_s বা একটি নীল K_t থাকে। R(3,3) = 6 আর R(4,4) = 18 জানা; দ্বিতীয়টি ১৯৫৫ সালে Greenwood আর Gleason-এর কাজ বলে উল্লেখ করা হয়। কিন্তু R(5,5)-এর জন্য আজও শুধু সীমা জানা: নিচের সীমা 43 বহু আগের কাজ থেকে, আর ২০২৪ সালে একটি কম্পিউটার-সহায়ক গবেষণায় (Angeltveit আর McKay) উপরের সীমা 46-এ নামানো হয়েছে বলে প্রকাশিত, তাই মানটি 43 থেকে 46-এর মধ্যে।

কেন এত কঠিন? উপরের সীমা প্রমাণ করতে হয় যে প্রতিটি রঙে একরঙা K₅ আছে, আর K₄₃-এর রঙের সংখ্যা 2⁹⁰³, যা কোনো কম্পিউটার গুনে শেষ করতে পারবে না। ব্লক ৪-এর brute force K₆-এ চলেছিল কারণ সেখানে মাত্র 2¹⁵টি রং। তাই প্রতিসাম্য আর চতুর যুক্তি দিয়ে খোঁজার পরিসর ছাঁটতে হয়। নিচের সীমার জন্য একটি ভালো রং খুঁজে বের করতে হয়, যা নিজেও কঠিন। Paul Erdős ১৯৪৭ সালে একটি সম্ভাবনার যুক্তি দিয়ে দেখান যে এলোমেলো রঙে বড় একরঙা clique প্রায়ই থাকে না, ফলে R(k, k) অন্তত 2^k/2-এর মতো দ্রুত বাড়ে। কিন্তু সেই রং নির্দিষ্টভাবে বানানোর ভালো পদ্ধতি আজও অজানা: আবার “অস্তিত্ব বনাম খুঁজে পাওয়া”। ২০২৩ সালে Campos, Griffiths, Morris আর Sahasrabudhe উপরের সীমায় দশকের পর দশক পরে একটি ঘাতীয় উন্নতি দেখান বলে প্রকাশিত হয়েছে।

মূল বার্তাটি প্রায়ই এক বাক্যে বলা হয়: “সম্পূর্ণ বিশৃঙ্খলা অসম্ভব”। Erdős–Szekeres-ও একই পরিবারের: যথেষ্ট লম্বা ক্রমে monotone অংশ অনিবার্য। এর গভীর রূপ পর্ব ৭৬ “Ramsey theory আর extremal combinatorics-এর পরিচয়”-এ আসবে।

মূল উপলব্ধি: pigeonhole-এর একটি সরল প্রয়োগ ছোট ক্ষেত্রে পূর্ণ উত্তর দেয়, কিন্তু একই প্রশ্ন সামান্য বড় হলেই গণনার বিস্ফোরণে গণিতের সবচেয়ে কঠিন খোলা সমস্যাগুলোর একটি হয়ে যায়।

প্র ০৫Erdős–Szekeres উপপাদ্য শুধু একটি সুন্দর ধাঁধা, নাকি কম্পিউটার বিজ্ঞানে এর বাস্তব প্রতিধ্বনি আছে? Longest increasing subsequence আর patience sorting-এর সঙ্গে সম্পর্ক কী?

উপপাদ্যের প্রমাণের label i_k আসলে একটি algorithm-এর হৃদয়: “a_k-এ শেষ হওয়া দীর্ঘতম increasing subsequence” হলো longest increasing subsequence (LIS) সমস্যার dynamic programming-এর অবস্থা। ব্লক ২-এর longest ফাংশন ঠিক সেটিই হিসাব করে, O(N²) সময়ে। একটি চতুর উন্নতি O(N log N)-এ নামায়: প্রতিটি দৈর্ঘ্যের increasing subsequence-এর সবচেয়ে ছোট শেষ পদ রেখে binary search. এই পদ্ধতিকে তাসের একটি একা-খেলার নামে patience sorting বলা হয়, আর এর বিশ্লেষণে দেখা যায়, তাসের স্তূপের সংখ্যা ঠিক LIS-এর দৈর্ঘ্য। কোড DSA কোর্সের পর্ব ৫৩-এ।

Erdős–Szekeres এখানে একটি নিশ্চয়তা দেয়: N-টি ভিন্ন সংখ্যায় LIS আর longest decreasing subsequence-এর গুণফল অন্তত N (প্রমাণের label-যুক্তিতেই আসে, কারণ সব label আলাদা আর i ≤ LIS, d ≤ LDS). তাই দুটির একটি অন্তত √N. এর ব্যবহারিক অর্থ আছে: একটি তালিকা প্রায় সাজানো কি না মাপার অনেক পদ্ধতি LIS-এর সঙ্গে যুক্ত, যেমন “কয়টি পদ সরালে তালিকা সাজানো হয়” তার উত্তর N − LIS. diff-এর মতো টুলে দুটি ফাইলের মিল খুঁজতে longest common subsequence লাগে, যা LIS-এর ঘনিষ্ঠ আত্মীয়।

গবেষণার দিকেও গল্পটি লম্বা। Stanisław Ulam ১৯৬০-এর দশকের শুরুতে প্রশ্ন তোলেন, এলোমেলো permutation-এ LIS-এর গড় দৈর্ঘ্য কত। ১৯৭৭ সালে Vershik–Kerov আর আলাদাভাবে Logan–Shepp দেখান, তা মোটামুটি 2√N, আর ১৯৯৯ সালে Baik, Deift আর Johansson এর ওঠানামার সূক্ষ্ম বণ্টন বের করেন বলে উল্লেখ করা হয়, যা random matrix theory-র সঙ্গে একটি অপ্রত্যাশিত সংযোগ। ব্লক ২-এ n = 6 (N = 37)-এ ৪০০টি এলোমেলো ক্রমের প্রতিটিতেই সেরা দৈর্ঘ্য 7-এর বেশি এসেছিল (সবচেয়ে কম 8), এই প্রবণতার সঙ্গে মিলে।

মূল উপলব্ধি: একটি অস্তিত্বের প্রমাণের ভেতরের হিসাব (label) প্রায়ই নিজেই একটি algorithm; প্রমাণটি পড়ে “কী আছে” ছাড়াও “কীভাবে খুঁজব” শেখা যায়।

অনুশীলন

আগে খাতায় করুন, তারপর উত্তর খুলে মেলান।

প্রমাণ: প্রমাণ করুন, যেকোনো ৭টি পূর্ণসংখ্যার মধ্যে এমন দুটি আছে যাদের যোগফল বা পার্থক্য 10 দিয়ে বিভাজ্য। দেখান যে ৬টি সংখ্যায় এটি নিশ্চিত নয়।
1. বাক্স বানান ভাগশেষ mod 10 দিয়ে, কিন্তু জোড়ায় জোড়ায়: {0}, {5}, {1, 9}, {2, 8}, {3, 7}, {4, 6}. মোট ৬টি বাক্স, আর প্রতিটি ভাগশেষ ঠিক একটি বাক্সে। — বাক্স
2. ৭টি সংখ্যা, ৬টি বাক্স: দুটি সংখ্যা x, y একই বাক্সে। — pigeonhole
3. যদি তাদের ভাগশেষ সমান, তবে 10 ∣ (x − y). যদি আলাদা, তবে বাক্সটি {r, 10 − r}, তাই ভাগশেষের যোগফল 10, আর 10 ∣ (x + y). ∎
৬টিতে নিশ্চয়তা নেই: 0, 1, 2, 3, 4, 5. পার্থক্যগুলো 1 থেকে 5, যোগফলগুলো 1 থেকে 9, কোনোটিই 10 দিয়ে বিভাজ্য নয় (scratch-এ যাচাই করা)।
হিসাব: (ক) বাজারঘরের ৫০ জন রাইডার ৬টি zone-এ কাজ করেন। কোনো zone-এ কমপক্ষে কতজন? (খ) কমপক্ষে কতজন ক্রেতা হলে নিশ্চিত যে অন্তত ৩ জন একই জেলার (৬৪টি জেলা)? (গ) কোনো সংখ্যা না দেখে 1..30 থেকে কমপক্ষে কয়টি সংখ্যা তুললে নিশ্চিত যে একটি অন্যটিকে ভাগ করে?

(ক) ⌈50/6⌉ = ⌈8.33…⌉ = 9 জন। (৬ · ৮ = ৪৮ < ৫০, তাই সব zone-এ ৮ বা কম হতে পারে না।)

(খ) k(r − 1) + 1 = 64 · 2 + 1 = 129 জন। ১২৮ জনে প্রতি জেলায় ঠিক দুজন সম্ভব।

(গ) 2n = 30, তাই n = 15, আর উত্তর n + 1 = 16টি (উপপাদ্য ৩.৩)। ১৫টি যথেষ্ট নয়: {16, 17, …, 30}-এ কোনো ভাজক-জোড়া নেই। সব সংখ্যা scratch-এ যাচাই করা।
আউটপুট অনুমান: কোড না চালিয়ে বলুন কী ছাপা হবে। তারপর যেকোনো Python-এ চালিয়ে মেলান।
```
from collections import Counter
orders = [17, 3, 25, 9, 31, 12, 40, 5]
box = Counter(x % 7 for x in orders)
print(sorted(box.items()))
print(max(box.values()), -(-len(orders) // 7))
```
```
[(2, 1), (3, 3), (4, 1), (5, 3)]
3 2
```
ভাগশেষ mod 7: 17 → 3, 3 → 3, 25 → 4, 9 → 2, 31 → 3, 12 → 5, 40 → 5, 5 → 5. তাই বাক্স 3-এ তিনটি, বাক্স 5-এ তিনটি। দ্বিতীয় লাইনে সবচেয়ে ভরা বাক্সে 3টি, আর -(-8 // 7) হলো ⌈8/7⌉ = 2, Python-এ ceiling-এর একটি প্রচলিত কৌশল। শিক্ষা: pigeonhole শুধু নিচের সীমা (এখানে 2) নিশ্চিত করে; আসল তথ্যে সবচেয়ে ভরা বাক্স তার চেয়ে বেশিও হতে পারে।
প্রমাণের ভুল ধরুন: একজন লিখলেন: “দাবি: যেকোনো n-টি পূর্ণসংখ্যার মধ্যে দুটির ভাগশেষ mod n সমান। প্রমাণ: ভাগশেষ n-টি সম্ভব, আর সংখ্যাও n-টি, তাই pigeonhole অনুযায়ী দুটি একই ভাগশেষে পড়ে। ∎ এর ফলে, যেকোনো n-টি সংখ্যায় দুটির পার্থক্য n দিয়ে বিভাজ্য।” ভুলটি কোথায়? একটি counterexample দিন, আর দাবিটি কীভাবে ঠিক করবেন বলুন।
- ভুল: বস্তু (n) আর বাক্স (n) সমান। মৌলিক নীতি লাগে বস্তু > বাক্স; সমান হলে প্রতিটি বস্তু আলাদা বাক্সে বসতে পারে।
- Counterexample: n = 4, সংখ্যা 0, 1, 2, 3 (বা 8, 5, 2, 7): ভাগশেষ সব আলাদা, আর কোনো পার্থক্য 4 দিয়ে বিভাজ্য নয়।
- সংশোধন: “যেকোনো n + 1টি পূর্ণসংখ্যা” লিখলে দাবিটি সত্য (উপপাদ্য ৩.১)। আর n-টি সংখ্যায় যা সত্য, তা অন্য কথা: পাশাপাশি একটি block-এর যোগফল n দিয়ে বিভাজ্য (উপপাদ্য ৩.২), যেখানে S₀ যোগ করে n + 1টি বস্তু বানানো হয়।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রম“যেকোনো n-টি পূর্ণসংখ্যায় একটি পাশাপাশি block-এর যোগফল n দিয়ে বিভাজ্য”, এর প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

S₀ = 0 আর S_j = a₁ + ⋯ + a_j দিয়ে n + 1টি prefix sum বানানো
প্রতিটি prefix sum-কে তার ভাগশেষ mod n-এর বাক্সে রাখা (n-টি বাক্স)
pigeonhole দিয়ে i < j পাওয়া, যাতে S_i ≡ S_j (mod n)
S_j − S_i = a_i+1 + ⋯ + a_j লেখা
সিদ্ধান্ত: এই ফাঁকা নয় এমন block-এর যোগফল n দিয়ে বিভাজ্য

একটি দোকান সপ্তাহের ৭ দিনই খোলা। কমপক্ষে কয়টি অর্ডার হলে নিশ্চিত যে কোনো একদিনে অন্তত ৪টি অর্ডার হয়েছে?

৫০ জন রাইডারকে ৬টি zone-এ ভাগ করা হলো (প্রত্যেকে ঠিক একটি zone-এ)। কোন বিবৃতি সবসময় সত্য?

প্রতিটি zone-এ ঠিক ৮ জন
কোনো zone-এ অন্তত ১০ জন
কোনো zone-এ অন্তত ৯ জন
কোনো একটি zone খালি

১৭টি ভিন্ন সংখ্যার যেকোনো ক্রমে কোন দৈর্ঘ্যের strictly increasing বা strictly decreasing subsequence থাকবেই (Erdős–Szekeres অনুযায়ী সবচেয়ে বড় নিশ্চিত দৈর্ঘ্য)?

একটি lossless compressor দৈর্ঘ্য 8-এর প্রতিটি bit string-কে দৈর্ঘ্য 8-এর চেয়ে ছোট (০ থেকে ৭ bit) string-এ নিতে পারে না। এর সবচেয়ে সরাসরি কারণ কোনটি?

string 256টি কিন্তু ছোট string মাত্র 255টি, তাই compressor one-to-one থাকতে পারে না
কম্পিউটার যথেষ্ট দ্রুত নয়
দৈর্ঘ্য 8-এর আর ছোট string-এর সংখ্যা সমান
শুধু entropy-র কারণে, pigeonhole এখানে খাটে না

“{1, 2, …, 10} থেকে যেকোনো ৬টি সংখ্যায় একটি অন্যটিকে ভাগ করে”, এর pigeonhole প্রমাণে বাক্স কোনগুলো?

ভাগশেষ mod 5
জোড় আর বিজোড়
সবচেয়ে ছোট মৌলিক উৎপাদক
বিজোড় অংশ 1, 3, 5, 7, 9 (x = 2^k · m লিখে)

K₆-এর প্রতিটি edge লাল বা নীল রঙে রাঙানো। একটি vertex v থেকে ৫টি edge. R(3,3) ≤ 6-এর প্রমাণে প্রথম ধাপে কী বলা হয়?

v-এর সব edge একই রঙের
v-এর অন্তত ৪টি edge একই রঙের
v-এর অন্তত ৩টি edge একই রঙের (generalized pigeonhole)
v-এর লাল আর নীল edge সমান সংখ্যক

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

নীতি: k + 1টি বস্তু k-টি বাক্সে ⇒ কোনো বাক্সে অন্তত ২টি। N-টি বস্তু ⇒ কোনো বাক্সে অন্তত ⌈N/k⌉টি। নিশ্চিত করতে r-টি: N = k(r − 1) + 1.
প্রমাণের ধাঁচ: উল্টোটা ধরে মোট গোনা; প্রতিটি সীমা নিখুঁত, আর এক কম বস্তুর একটি counterexample থাকে।
বাক্স বাছাই: ভাগশেষ (n + 1 সংখ্যা), prefix sum mod n (বিভাজ্য block), বিজোড় অংশ (1..2n-এ ভাজক-জোড়া), (i, d) label (Erdős–Szekeres, n² + 1 পদে দৈর্ঘ্য n + 1).
কম্পিউটারে: |U| > m হলে hash collision অনিবার্য; lossless compression সব ফাইল ছোট করতে পারে না (2ⁿ বনাম 2ⁿ − 1), আর কিছু ছোট করলে কিছু বড় করে।
অস্তিত্ব বনাম খোঁজা: pigeonhole সাধারণত non-constructive; R(3,3) = 6 প্রমাণ সহজ, কিন্তু বড় Ramsey number আর SHA-256 collision খুঁজে পাওয়া আজও নাগালের বাইরে।

পরের পর্বে: পর্ব ৩৩ “Permutation আর combination”: P(n, r) আর C(n, r)-এর সূত্র গুণ আর ভাগের নিয়ম থেকে প্রমাণ, পুনরাবৃত্ত অক্ষরের সাজানো, আর শর্তসহ ক্রিকেট দল বাছাইয়ের হিসাব।

Pigeonhole principle — সহজ থেকে generalized

এই পর্বে যা শিখবেন

১ · খোপ আর কবুতর — নীতিটি কী বলে

২ · Generalized pigeonhole — ⌈N/k⌉

উল্টো প্রশ্ন: “কমপক্ষে কয়টি হলে নিশ্চিত?”

৩ · ভাগশেষ আর ভাগযোগ্যতার খেলা

পাশাপাশি অর্ডারের block, যার যোগফল n দিয়ে বিভাজ্য

1..2n-এ ভাজক-জোড়া — “বিজোড় অংশ” বাক্স

৪ · Erdős–Szekeres — এলোমেলো ক্রমেও শৃঙ্খলা

৫ · কম্পিউটার বিজ্ঞানে pigeonhole — hash আর compression

Hash collision এড়ানো যায় না

কোনো compression সব ফাইল ছোট করতে পারে না

৬ · Ramsey-র এক ঝলক আর “আছে” বনাম “খুঁজে পাওয়া”

অস্তিত্ব আছে, কিন্তু কোথায়?

৭ · পরীক্ষার অঙ্ক আর দুটি ভুল প্রমাণ

অঙ্ক ১: গ্রেড পাঁচটি (A, B, C, D, F). কমপক্ষে কতজন পরীক্ষার্থী হলে নিশ্চিত যে অন্তত ৬ জন একই গ্রেড পেয়েছেন?

প্রমাণের ভুল ধরুন ১: “ছোট করে ভাগ”

প্রমাণের ভুল ধরুন ২: “নয় পদেই যথেষ্ট”

৮ · AI-এর যুগে — pigeonhole যুক্তি যাচাই

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ