এই পর্বে যা শিখবেন
- একটি বিবৃতির অনুমান, সিদ্ধান্ত আর quantifier আলাদা করে পড়া, আর আকার দেখে প্রমাণের পদ্ধতি বাছা
- প্রতিটি ধাপের পাশে কারণ লিখে, ক্ষেত্রগুলো পূর্ণ রেখে, ∎ পর্যন্ত পরিষ্কার প্রমাণ লেখা
- Induction-এর basis, hypothesis আর step আলাদা করে লেখা; strong আর structural রূপ কখন লাগে তা চেনা
- Double counting, bijection, pigeonhole, invariant আর extremal যুক্তি দিয়ে প্রমাণ সাজানো
- ভুল প্রমাণের ঠিক কোন লাইনে ফাঁক, তা দেখিয়ে সংশোধিত প্রমাণ লেখা
১ · প্রমাণ লেখার কাঠামো — পড়া, পদ্ধতি বাছাই, লেখা, যাচাই
প্রমাণ লেখা অনেকটা রিকশাওয়ালাকে পথ বোঝানোর মতো: “বাজার থেকে বাঁয়ে, মসজিদের পরে ডানে” — প্রতিটি মোড় বলা থাকলে অচেনা লোকও পৌঁছে যান। পরীক্ষকও আপনার প্রতিটি মোড় মেলান। একটি ধাপ বাদ পড়লে, বা “স্পষ্টতই” লিখে লাফ দিলে, পথ সেখানেই হারায়। পদ্ধতিগুলো এই কোর্সে শেখানো হয়েছে: পর্ব ০৮ “প্রমাণের পদ্ধতি”, পর্ব ০৯ “প্রমাণের কৌশল”, পর্ব ১০ “Mathematical induction”, পর্ব ১১ “Strong induction আর well-ordering” আর পর্ব ১২ “Recursive সংজ্ঞা আর structural induction”. এখানে সেগুলো পরীক্ষার খাতায় লেখার অনুশীলন।
- পড়া: বিবৃতিকে “∀x (P(x) → Q(x))” ধরনের আকারে লিখুন। কোনটি দেওয়া (hypothesis), কোনটি দেখাতে হবে, আর x কোন সেটে, তা আলাদা করুন।
- পদ্ধতি: নিচের ছবির সংকেত দেখে বাছুন। প্রথম লাইনেই লিখুন “Contrapositive দিয়ে প্রমাণ করি” — পরীক্ষক তখন পথটি আগে থেকে জানেন।
- লেখা: প্রতিটি লাইনের পাশে একটি কারণ: সংজ্ঞা, আগের উপপাদ্য, বীজগণিত, inductive hypothesis. শেষ লাইনে মূল দাবিটি আবার লিখে ∎.
- যাচাই: খসড়ায় দু-তিনটি ছোট মানে দাবি মেলান। মিলে গেলেও তা প্রমাণ নয়; না মিললে দাবি বা আপনার পড়া ভুল।
ছবি ৮২.১ — দাবির সংকেত থেকে প্রমাণের পদ্ধতি
বাঁয়ে বিবৃতিতে যা দেখবেন, ডানে প্রথমে যে পদ্ধতি চেষ্টা করবেন
ছবিটি নিয়ম নয়, প্রথম চেষ্টার দিক। একই দাবির একাধিক প্রমাণ থাকে: n³ − n-কে ৬ ভাগ করে, তা induction-এ (গ-০২) বা তিনটি পরপর সংখ্যার গুণফল হিসেবে case দিয়েও দেখানো যায়। নিচের stepper-এ একটি ১০ নম্বরের উত্তর শুরু থেকে ∎ পর্যন্ত গড়া হয়েছে।
| ধাপ | |
| খাতায় যা লিখলেন | |
| জমা নম্বর |
- পড়া — ১ নম্বর। অনুমান 3 ∤ n, সিদ্ধান্ত n² ভাগ ৩-এর ভাগশেষ ১, আর n যেকোনো পূর্ণসংখ্যা। এক লাইনে প্রতীকে লিখলেই পরীক্ষক বোঝেন আপনি দাবিটি ঠিক পড়েছেন।
- পদ্ধতি — আরও ১। অনুমানটি “ভাগশেষ ১ বা ২” মাত্র দুটি সম্ভাবনায় ভাঙে, তাই proof by cases. ক্ষেত্রগুলো কোথা থেকে এল, তা division algorithm দিয়ে বলা জরুরি।
- ক্ষেত্র ১ — আরও ৩। বর্গ করে ৩-এর গুণিতক আলাদা করা: 3(3k² + 2k) + 1. বন্ধনীর ভেতরটা পূর্ণসংখ্যা, এটি একবার বলা।
- ক্ষেত্র ২ — আরও ৩। 4 = 3 + 1 ভেঙে ৩-এর গুণিতকে মেলানো। এখানেই অনেকে “9k² + 12k + 4 ≡ 4” লিখে থেমে যান; 4 ≡ 1 (mod 3) কথাটি লিখতে হয়।
- উপসংহার — শেষ ২। মূল দাবি আবার লেখা, আর “ক্ষেত্রগুলো পূর্ণ” কথাটি। এটি বাদ দিলে সাধারণত ১ নম্বর কাটে।
- খসড়া। ১ থেকে ১০-এর মধ্যে ৩ দিয়ে বিভাজ্য নয় এমন সাতটি n-এ মিলিয়ে দেখা (scratch script-এ মেলানো)। এটি নম্বর আনে না, কিন্তু ভুল দাবিতে সময় নষ্ট থেকে বাঁচায়।
| প্রশ্নের ধরন | পড়া ও পদ্ধতি | মূল ধাপ | পূর্ণতা (ক্ষেত্র, basis) | উপসংহার |
|---|---|---|---|---|
| ৫ নম্বর | ১ | ২ | ১ | ১ |
| ১০ নম্বর | ২ | ৫ | ২ | ১ |
| অংশ | পদ্ধতি | মূল পর্ব | প্রশ্ন |
|---|---|---|---|
| ২ | Direct, contrapositive, যদি এবং কেবল যদি | ০৮, ১৪–১৬ | ক-০১–ক-০৪ |
| ৩ | Contradiction, case, অস্তিত্ব, counterexample | ০৮, ০৯, ২০ | খ-০১–খ-০৫ |
| ৪ | Induction: সাধারণ, strong, structural | ১০–১২ | গ-০১–গ-০৫ |
| ৫ | Combinatorial, bijective, pigeonhole | ৩২, ৩৪, ৩৭, ৫৭ | ঘ-০১–ঘ-০৫ |
| ৬ | সংখ্যাতত্ত্ব, relation, graph, tree, group | ২১, ৫৫, ৬২, ৬৫, ৭০ | ঙ-০১–ঙ-০৫ |
| ৭ | Invariant, diagonal, অসম্ভবতা | ১৩, ১৮, ৭৪ | চ-০১–চ-০৪ |
| ৮ | ভুল প্রমাণ ধরা আর সংশোধন | ০৮, ১০, ৩১, ৫৯ | ত-০১–ত-০৬ |
এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠান থেকে নেওয়া নয়; এ ধরনের প্রমাণ discrete math-এর কোর্সে, চাকরির লিখিত পরীক্ষায় আর ইন্টারভিউতে প্রায়ই আসে। প্রতিটি প্রশ্ন নিজে লেখার চেষ্টা করুন, তারপর খুলে মেলান। ছয়টি ব্লক ব্রাউজারে Python (Pyodide) চালায়; প্রথমবার নামতে কয়েক সেকেন্ড লাগে। ব্যাখ্যা-আর-তুলনার লিখিত প্রশ্ন আর ভাইভা পর্ব ৮১ “লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — Discrete Mathematics”-এ, হিসাবের অনুশীলন পর্ব ৭৯ “Numerical সমস্যার অনুশীলন”-এ, MCQ পর্ব ৮০ “MCQ প্রশ্নব্যাংক”-এ।
২ · অংশ ক — Direct, contrapositive আর “যদি এবং কেবল যদি”
রিভিশন: পর্ব ০৮ “প্রমাণের পদ্ধতি” (direct, contrapositive, দুই দিকের প্রমাণ), পর্ব ১৫ “সেটের অপারেশন” (element chasing), পর্ব ১৬ “ফাংশন” (one-to-one, onto). এই দলের প্রশ্নে নম্বর আসে সংজ্ঞা ঠিকভাবে খোলা থেকে।
ক-০১প্রমাণ করুন: দুটি বিজোড় পূর্ণসংখ্যার যোগফল জোড়। — ৫ নম্বর (সহজ)
Direct proof: সংজ্ঞা খুলে সোজা পথে।
- ধরি m আর n বিজোড়। তাহলে কোনো পূর্ণসংখ্যা a, b-এর জন্য m = 2a + 1, n = 2b + 1. — বিজোড়ের সংজ্ঞা; a আর b আলাদা অক্ষর
- m + n = 2a + 2b + 2 = 2(a + b + 1). — বীজগণিত
- a + b + 1 পূর্ণসংখ্যা, তাই m + n জোড়। ∎ — জোড়ের সংজ্ঞা
নম্বর-ভাগ: সংজ্ঞা দিয়ে শুরু (১), আলাদা অক্ষর (১), বীজগণিত (২), উপসংহার (১)। যেখানে নম্বর কাটে: দুটির জন্য একই k (m = 2k + 1, n = 2k + 1) লেখা: তাতে শুধু m = n-এর ক্ষেত্র প্রমাণ হয়। “৩ + ৫ = ৮ জোড়” — উদাহরণ প্রমাণ নয়।
ক-০২n একটি পূর্ণসংখ্যা। প্রমাণ করুন: n² জোড় হলে n জোড়। — ৫ নম্বর (সহজ)
সোজা পথে n² = 2k থেকে n বের করা কঠিন (√ নিতে হয়)। তাই contrapositive: “n জোড় নয় ⇒ n² জোড় নয়”, যা মূল দাবির সমতুল্য।
- ধরি n বিজোড়: n = 2k + 1. — contrapositive-এর অনুমান
- n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, তাই n² বিজোড়। — বীজগণিত, বিজোড়ের সংজ্ঞা
- ¬(n জোড়) → ¬(n² জোড়) প্রমাণ হলো; contrapositive সমতুল্য বলে n² জোড় ⇒ n জোড়। ∎ — p → q ≡ ¬q → ¬p
নম্বর-ভাগ: কোন পদ্ধতি আর কেন (১), contrapositive সঠিকভাবে লেখা (১), বীজগণিত (২), উপসংহারে সমতুল্যতার কথা (১)। যেখানে নম্বর কাটে: converse (“n জোড় ⇒ n² জোড়”) প্রমাণ করা; অংশ ৮-এর ত-০১ দেখুন।
ক-০৩A আর B যেকোনো দুটি সেট। প্রমাণ করুন: A ⊆ B যদি এবং কেবল যদি A ∩ B = A. — ১০ নম্বর (মাঝারি)
যদি এবং কেবল যদি মানে দুটি আলাদা প্রমাণ; আর সেটের সমতা মানে দুই দিকের ⊆ (double inclusion).
- (⇒) ধরি A ⊆ B. A ∩ B ⊆ A সবসময় সত্য, কারণ x ∈ A ∩ B হলে x ∈ A. — intersection-এর সংজ্ঞা
- উল্টো দিক: x ∈ A নিন। A ⊆ B বলে x ∈ B; তাই x ∈ A ∩ B. সুতরাং A ⊆ A ∩ B. — অনুমান, element chasing
- দুই দিকের ⊆ থেকে A ∩ B = A. — সেটের সমতার সংজ্ঞা
- (⇐) ধরি A ∩ B = A. x ∈ A নিন; তাহলে x ∈ A ∩ B, তাই x ∈ B. সুতরাং A ⊆ B. ∎ — অনুমানে প্রতিস্থাপন, intersection
নম্বর-ভাগ: দুই দিক ঘোষণা (২), (⇒)-এর দুটি ⊆ (৪), (⇐) (৩), উপসংহার (১)। যেখানে নম্বর কাটে: Venn diagram এঁকে “দেখা যাচ্ছে” লেখা — ছবি একটি উদাহরণ, প্রমাণ নয়; শুধু এক দিক প্রমাণ।
ক-০৪f: A → B আর g: B → C দুটি ফাংশন। প্রমাণ করুন: (ক) f আর g দুটিই one-to-one হলে g ∘ f one-to-one; (খ) g ∘ f onto হলে g onto. — ১০ নম্বর (মাঝারি)
- (ক) ধরি g(f(x₁)) = g(f(x₂)), x₁, x₂ ∈ A. — one-to-one-এর সংজ্ঞা অনুযায়ী এটি থেকে শুরু
- g one-to-one, তাই f(x₁) = f(x₂). — g-এর ধর্ম
- f one-to-one, তাই x₁ = x₂. সুতরাং g ∘ f one-to-one. — f-এর ধর্ম
- (খ) যেকোনো c ∈ C নিন। g ∘ f onto বলে কোনো a ∈ A-এর জন্য g(f(a)) = c. — onto-এর সংজ্ঞা
- b = f(a) ∈ B নিলে g(b) = c. প্রতিটি c-এর জন্য এমন b আছে, তাই g onto. ∎ — witness নির্মাণ
নম্বর-ভাগ: (ক) সঠিক শুরু আর ক্রম: আগে g, পরে f (৫); (খ) witness b = f(a) দেখানো (৪); উপসংহার (১)। যেখানে নম্বর কাটে: (খ)-তে “f-ও onto” দাবি করা — মিথ্যা: A = {1}, B = {1, 2}, C = {1}, f(1) = 1, g ধ্রুবক; g ∘ f onto, কিন্তু f নয়।
৩ · অংশ খ — Contradiction, case, অস্তিত্ব আর counterexample
রিভিশন: পর্ব ০৮ (√2, মৌলিক সংখ্যা অসীম), পর্ব ০৯ “প্রমাণের কৌশল” (case, অস্তিত্ব, counterexample), পর্ব ২০ “বিভাজ্যতা আর মৌলিক সংখ্যা”। Contradiction-এর প্রথম লাইন সবসময় একই: “বিপরীতে ধরি …”, আর শেষে কোন দুটি কথা পরস্পরবিরোধী, তা নাম ধরে বলা।
খ-০১প্রমাণ করুন: √2 মূলদ সংখ্যা নয়। — ১০ নম্বর (মাঝারি)
- বিপরীতে ধরি √2 = p/q, যেখানে p, q পূর্ণসংখ্যা, q ≠ 0, আর ভগ্নাংশটি লঘিষ্ঠ আকারে (gcd(p, q) = 1). — মূলদের সংজ্ঞা; লঘিষ্ঠ আকার সবসময় সম্ভব
- বর্গ করে 2q² = p², তাই p² জোড়। — বীজগণিত
- ক-০২ অনুযায়ী p জোড়: p = 2r. — আগের ফল
- বসালে 2q² = 4r², অর্থাৎ q² = 2r², তাই q²-ও জোড়, আর q জোড়। — একই যুক্তি আবার
- p আর q দুটিই জোড়, তাই ২ উভয়কে ভাগ করে; এটি gcd(p, q) = 1-এর বিরোধী। অতএব √2 অমূলদ। ∎ — বিরোধ নাম ধরে
নম্বর-ভাগ: বিপরীত অনুমান আর লঘিষ্ঠ আকার (২), p জোড় কারণসহ (৩), q জোড় (৩), বিরোধ স্পষ্ট (২)। যেখানে নম্বর কাটে: “p² জোড় তাই p জোড়” কারণ ছাড়া; লঘিষ্ঠ আকার না বলা — তখন বিরোধটাই থাকে না।
খ-০২প্রমাণ করুন: মৌলিক সংখ্যা অসীমসংখ্যক। — ১০ নম্বর (মাঝারি)
- বিপরীতে ধরি মৌলিক সংখ্যা সসীম: p₁, p₂, …, pk, সবগুলো। — বিপরীত অনুমান
- N = p₁p₂…pk + 1 নিন। N ≥ 3 > 1, তাই N-এর অন্তত একটি মৌলিক উৎপাদক q আছে। — পাটিগণিতের মৌলিক উপপাদ্য (পর্ব ১১-এ strong induction-এ প্রমাণিত)
- q তালিকার কোনো pi. তাহলে q ∣ p₁…pk আর q ∣ N, তাই q ∣ N − p₁…pk = 1. — দুটি গুণিতকের পার্থক্যও গুণিতক
- কোনো মৌলিক সংখ্যা ১-কে ভাগ করে না: বিরোধ। তাই মৌলিক সংখ্যা অসীম। ∎
নম্বর-ভাগ: অনুমান (১), N-এর নির্মাণ (২), মৌলিক উৎপাদকের অস্তিত্ব কারণসহ (২), q ∣ 1 (৩), বিরোধ (২)। যেখানে নম্বর কাটে: “N নিজেই মৌলিক” লেখা — ভুল; প্রথম ছয়টি মৌলিক নিলে N = 30031 = 59 × 509 (নিচের ব্লক)। দাবি শুধু এটুকু: N-এর মৌলিক উৎপাদক তালিকার বাইরে।
খ-০৩প্রমাণ করুন: যেকোনো পূর্ণসংখ্যা n-এর জন্য n² ≡ 0 বা 1 (mod 4). এ থেকে দেখান যে 4k + 3 আকারের কোনো সংখ্যা দুটি পূর্ণবর্গের যোগফল নয়। — ১০ নম্বর (মাঝারি)
Proof by cases, তারপর একটি corollary.
- ক্ষেত্র ১: n জোড়, n = 2k. n² = 4k² ≡ 0 (mod 4). — বীজগণিত
- ক্ষেত্র ২: n বিজোড়, n = 2k + 1. n² = 4(k² + k) + 1 ≡ 1 (mod 4). প্রতিটি পূর্ণসংখ্যা জোড় বা বিজোড়, তাই ক্ষেত্র পূর্ণ। — বীজগণিত, ক্ষেত্রের পূর্ণতা
- Corollary: a² + b²-এর ভাগশেষ (mod 4) হতে পারে 0 + 0, 0 + 1 বা 1 + 1, অর্থাৎ 0, 1 বা 2. — প্রথম অংশ দুবার
- 4k + 3 ≡ 3 (mod 4), যা তালিকায় নেই; তাই 4k + 3 = a² + b² অসম্ভব। ∎ — congruence-এর তুলনা
নম্বর-ভাগ: দুটি ক্ষেত্র (২ + ২), পূর্ণতার কথা (১), যোগফলের সম্ভাব্য ভাগশেষ (৩), উপসংহার (২)। যেখানে নম্বর কাটে: n-কে শুধু ধনাত্মক ধরা (দাবি সব পূর্ণসংখ্যার); ঋণাত্মক n-এও একই হিসাব খাটে, এক লাইনে বলুন।
খ-০৪প্রমাণ করুন: এমন দুটি অমূলদ সংখ্যা a, b আছে যাতে ab মূলদ। একটি non-constructive আর একটি constructive প্রমাণ দিন। — ১০ নম্বর (কঠিন)
Non-constructive (অস্তিত্ব দেখায়, কোনটি তা বলে না):
- x = √2√2 নিন। x মূলদ হলে a = b = √2 নিলেই হলো (খ-০১ অনুযায়ী √2 অমূলদ)। — ক্ষেত্র ১
- x অমূলদ হলে a = x, b = √2: ab = √2√2·√2 = √2² = 2, মূলদ। — ক্ষেত্র ২, ঘাতের নিয়ম
- দুই ক্ষেত্রের একটি সত্য, তাই এমন a, b আছে; কিন্তু কোন জোড়াটি, প্রমাণ তা বলে না। ∎
Constructive (witness হাতে দেয়): a = √2, b = log₂9.
- ab = 2(1/2)·log₂9 = 2log₂3 = 3, মূলদ। — লগারিদমের নিয়ম
- b অমূলদ: বিপরীতে ধরি log₂9 = p/q, p, q ধনাত্মক পূর্ণসংখ্যা। তাহলে 2p = 9q. বাঁ দিক জোড়, ডান দিক বিজোড়: বিরোধ। ∎ — contradiction, parity
নম্বর-ভাগ: দুই ক্ষেত্রের যুক্তি (৪), non-constructive কেন তা বলা (১), constructive উদাহরণ (২), b-এর অমূলদতা (৩)। যেখানে নম্বর কাটে: constructive অংশে b অমূলদ, তা প্রমাণ না করা।
খ-০৫দাবি: “প্রতিটি অঋণাত্মক পূর্ণসংখ্যা n-এর জন্য n² + n + 41 মৌলিক।” দাবিটি সত্য না মিথ্যা? প্রমাণ দিন। — ৫ নম্বর (সহজ)
- দাবিটি সর্বজনীন (∀n), তাই একটি counterexample-ই যথেষ্ট। — ¬∀n P(n) ≡ ∃n ¬P(n)
- n = 40: 40² + 40 + 41 = 40(40 + 1) + 41 = 41 · 40 + 41 = 41². — বীজগণিত
- 41² = 1681 মৌলিক নয় (৪১ দিয়ে বিভাজ্য), তাই দাবি মিথ্যা। ∎
নম্বর-ভাগ: “মিথ্যা” সিদ্ধান্ত (১), counterexample (২), কেন মৌলিক নয় দেখানো (২)। n = 0 থেকে 39 পর্যন্ত মানগুলো মৌলিক (ব্লকে মেলানো), তাই ৪০টি উদাহরণ মিলে গেলেও দাবি প্রমাণ হয় না — এটাই শিক্ষা।
নিচের ব্লক অংশ খ-এর দাবিগুলো ছোট পরিসরে মেলায়। মনে রাখবেন: সসীম পরিসরে মিল প্রমাণ নয়; কিন্তু খ-০২-এর “N মৌলিক” ধরনের ভুল দাবি এক নিমেষে ধরা পড়ে।
from math import isqrt, prod
# 1) squares mod 4 take only the values 0 and 1
print("n^2 mod 4 values:", sorted({n * n % 4 for n in range(-50, 51)}))
# 2) no number 4k+3 below 2000 is a sum of two squares
two_sq = {a * a + b * b for a in range(45) for b in range(45)}
bad = [m for m in range(3, 2000, 4) if m in two_sq]
print("4k+3 that are sums of two squares:", bad)
# 3) p^2 = 2 q^2 has no solution with 1 <= q <= 10**5
hits = [q for q in range(1, 10**5 + 1) if isqrt(2 * q * q) ** 2 == 2 * q * q]
print("q with 2q^2 a perfect square:", hits)
# 4) Euclid's N = p1*...*pk + 1 is NOT always prime
def smallest_factor(n):
return next((d for d in range(2, isqrt(n) + 1) if n % d == 0), n)
for ps in ([2, 3, 5], [2, 3, 5, 7], [2, 3, 5, 7, 11, 13]):
N = prod(ps) + 1
d = smallest_factor(N)
print(ps, "N =", N, "prime" if d == N else f"= {d} * {N // d}")
# 5) the counterexample to "n^2 + n + 41 is always prime"
def is_prime(m):
return m > 1 and all(m % d for d in range(2, isqrt(m) + 1))
n = next(n for n in range(100) if not is_prime(n * n + n + 41))
print("first n:", n, "value:", n * n + n + 41, "=", isqrt(n * n + n + 41), "squared")আসল আউটপুট (ব্রাউজারের Python):
n^2 mod 4 values: [0, 1]
4k+3 that are sums of two squares: []
q with 2q^2 a perfect square: []
[2, 3, 5] N = 31 prime
[2, 3, 5, 7] N = 211 prime
[2, 3, 5, 7, 11, 13] N = 30031 = 59 * 509
first n: 40 value: 1681 = 41 squaredবর্গের ভাগশেষ (mod 4) শুধু 0 আর 1, আর ২০০০-এর নিচে 4k + 3 আকারের কোনো সংখ্যা দুটি বর্গের যোগফল নয়: খ-০৩ মিলেছে। p² = 2q²-এর কোনো সমাধান q ≤ 10⁵-এ নেই, খ-০১-এর সঙ্গে সংগত (তবে এটি প্রমাণ নয়)। Euclid-এর N প্রথম দুই সারিতে মৌলিক, কিন্তু 30031 = 59 × 509: তাই খ-০২-এ “N মৌলিক” লেখা ভুল। আর n² + n + 41 প্রথম ভাঙে n = 40-এ, মান 1681 = 41².
৪ · অংশ গ — Induction: সাধারণ, strong আর structural
রিভিশন: পর্ব ১০ “Mathematical induction”, পর্ব ১১ “Strong induction আর well-ordering”, পর্ব ১২ “Recursive সংজ্ঞা আর structural induction”. খাতায় চারটি অংশ আলাদা শিরোনামে লিখুন: P(n) কী, basis, inductive hypothesis, inductive step. Step-এ “P(k+1)-এর ভেতরে P(k) কোথায়” দেখানোই আসল কাজ।
গ-০১প্রমাণ করুন: প্রতিটি ধনাত্মক পূর্ণসংখ্যা n-এর জন্য 1 + 3 + 5 + … + (2n − 1) = n². — ৫ নম্বর (সহজ)
- P(n): প্রথম n বিজোড় সংখ্যার যোগফল n². Basis n = 1: বাঁ দিক 1, ডান দিক 1² = 1. — সরাসরি হিসাব
- Hypothesis: কোনো k ≥ 1-এর জন্য 1 + 3 + … + (2k − 1) = k². — P(k) ধরে নেওয়া
- Step: 1 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)². — hypothesis বসিয়ে, তারপর বীজগণিত
- তাই P(k) ⇒ P(k + 1); basis আর step মিলে সব n ≥ 1-এর জন্য P(n). ∎ — induction-এর নীতি
নম্বর-ভাগ: P(n) আর basis (১), hypothesis (১), step-এ hypothesis-এর ব্যবহার স্পষ্ট (২), উপসংহার (১)। যেখানে নম্বর কাটে: step-এ বাঁ আর ডান দিক একসঙ্গে বদলে “দুই দিক সমান” থেকে শুরু করা — এটি প্রমাণ করার বদলে ধরে নেওয়া।
গ-০২Induction দিয়ে প্রমাণ করুন: প্রতিটি অঋণাত্মক পূর্ণসংখ্যা n-এর জন্য 6 ∣ n³ − n. — ১০ নম্বর (মাঝারি)
- P(n): 6 ∣ n³ − n. Basis n = 0: 0 − 0 = 0, আর 6 ∣ 0. — সংজ্ঞা: 0 = 6 · 0
- Hypothesis: কোনো k ≥ 0-এর জন্য k³ − k = 6m. — P(k)
- Step: (k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3k(k + 1). — বিস্তার, P(k)-কে আলাদা করা
- k(k + 1) দুটি পরপর পূর্ণসংখ্যার গুণফল, তাই জোড়: k(k + 1) = 2t. অতএব 3k(k + 1) = 6t. — একটি জোড়, অন্যটি বিজোড়
- (k + 1)³ − (k + 1) = 6m + 6t = 6(m + t), তাই P(k + 1). Induction-এ সব n ≥ 0-এর জন্য সত্য। ∎
নম্বর-ভাগ: basis (১), hypothesis (১), বিস্তার আর P(k) আলাদা (৪), k(k + 1) জোড় কারণসহ (৩), উপসংহার (১)। বিকল্প: n³ − n = (n − 1)n(n + 1), তিনটি পরপর সংখ্যা, তাই ২ আর ৩ দুটিই ভাগ করে, আর gcd(2, 3) = 1 বলে ৬-ও; প্রশ্ন induction চাইলে এটি পুরো নম্বর না-ও পেতে পারে।
গ-০৩প্রমাণ করুন: প্রতিটি পূর্ণসংখ্যা n ≥ 5-এর জন্য 2ⁿ > n². Basis কেন ৫ থেকে, তাও ব্যাখ্যা করুন। — ১০ নম্বর (মাঝারি)
- Basis n = 5: 2⁵ = 32 > 25 = 5². — হিসাব
- Hypothesis: কোনো k ≥ 5-এর জন্য 2k > k². — P(k)
- 2k+1 = 2 · 2k > 2k². — hypothesis, দুই দিকে ২ দিয়ে গুণ
- দেখাতে হবে 2k² ≥ (k + 1)², অর্থাৎ k² − 2k − 1 ≥ 0, অর্থাৎ (k − 1)² ≥ 2. k ≥ 5 হলে (k − 1)² ≥ 16 ≥ 2. — বীজগণিত; এখানে k ≥ 5 লাগল (আসলে k ≥ 3-ই যথেষ্ট)
- তাই 2k+1 > 2k² ≥ (k + 1)², P(k + 1) সত্য। ∎
কেন ৫: দাবিটি n = 2, 3, 4-এ মিথ্যা (4 = 4, 8 < 9, 16 = 16; নিচের ব্লকে মেলানো)। Step নিজে k ≥ 3 থেকে চলে, কিন্তু basis-কে সত্য হতে হয়; প্রথম সত্য মান যেখান থেকে আর কখনো ভাঙে না, সেটি ৫. নম্বর-ভাগ: basis (১), hypothesis (১), গুণ (২), অসমতার ধাপ শর্তসহ (৪), basis-এর ব্যাখ্যা (২)।
গ-০৪বাজারঘরের টিকিট শুধু ৩ টাকা আর ৫ টাকার। Strong induction দিয়ে প্রমাণ করুন: প্রতিটি পূর্ণসংখ্যা n ≥ 8-এর জন্য n = 3a + 5b, যেখানে a, b অঋণাত্মক পূর্ণসংখ্যা। — ১০ নম্বর (মাঝারি)
- P(n): n = 3a + 5b কোনো a, b ≥ 0-এর জন্য। Basis তিনটি: 8 = 3 + 5, 9 = 3 · 3, 10 = 5 · 2. — সরাসরি
- Hypothesis (strong): কোনো k ≥ 10-এর জন্য 8 ≤ j ≤ k সব j-তে P(j) সত্য। — সব আগের মান
- Step: k + 1 ≥ 11, তাই k − 2 = (k + 1) − 3 ≥ 8, আর hypothesis-এ P(k − 2): k − 2 = 3a + 5b. — পরিসরের ভেতরে আছে কি না যাচাই
- k + 1 = 3(a + 1) + 5b, অর্থাৎ P(k + 1). ∎ — একটি ৩ টাকার টিকিট যোগ
কেন তিনটি basis: step তিন ধাপ পেছনে যায়; শুধু 8 প্রমাণ করলে 9 আর 10 কোনো আগের মান থেকে আসে না। 7 = 3a + 5b অসম্ভব, তাই শুরু 8-এ। নম্বর-ভাগ: তিন basis (৩), strong hypothesis সঠিক পরিসরে (২), k − 2 ≥ 8 যাচাই (২), নির্মাণ (২), উপসংহার (১)।
| n | |
| কোথা থেকে | |
| (a, b) | |
| 3a + 5b |
- Basis ১। 8 = একটি ৩ আর একটি ৫.
- Basis ২। 9 = তিনটি ৩. এটি 8 থেকে আসে না, তাই আলাদা basis.
- Basis ৩। 10 = দুটি ৫. এখন পরপর তিনটি মান হাতে।
- Step, n = 11. 11 − 3 = 8, যার উত্তর (1, 1); a এক বাড়িয়ে (2, 1).
- n = 12. 9-এর (3, 0) থেকে (4, 0). Step শুধু “তিন ধাপ পেছনে” তাকায়।
- n = 13. 10-এর (0, 2) থেকে (1, 2): 3 + 10 = 13.
- n = 14. 11-এর (2, 1) থেকে (3, 1). এখানে hypothesis-এ লাগল আগের step-এর ফল।
- n = 15. 12-এর (4, 0) থেকে (5, 0). তিনটি basis-এর তিনটি “সারি” এভাবে চিরকাল চলে; সব মান scratch script-এ মেলানো।
গ-০৫Full binary tree-এর recursive সংজ্ঞা: একটি একক node একটি full binary tree; T₁ আর T₂ full binary tree হলে একটি নতুন root, যার বাঁ subtree T₁ আর ডান subtree T₂, তাও full binary tree. Structural induction দিয়ে প্রমাণ করুন: leaf-এর সংখ্যা l(T) = i(T) + 1, যেখানে i(T) internal node-এর সংখ্যা। — ১০ নম্বর (কঠিন)
- Basis (একক node): node-টি leaf, তাই l = 1, i = 0, আর 1 = 0 + 1. — সংজ্ঞার basis নিয়ম
- Recursive step: ধরি T₁, T₂-এর জন্য l(T₁) = i(T₁) + 1 আর l(T₂) = i(T₂) + 1. — structural hypothesis: প্রতিটি অংশে দাবি সত্য
- নতুন tree T-এর leaf ঠিক T₁ আর T₂-এর leaf (নতুন root-এর দুটি সন্তান, তাই সে leaf নয়): l(T) = l(T₁) + l(T₂). — সংজ্ঞা
- internal node: T₁ আর T₂-এর সব, আর নতুন root: i(T) = i(T₁) + i(T₂) + 1. — সংজ্ঞা
- l(T) = i(T₁) + 1 + i(T₂) + 1 = (i(T₁) + i(T₂) + 1) + 1 = i(T) + 1. ∎ — hypothesis বসিয়ে
নম্বর-ভাগ: basis (২), hypothesis দুটি অংশে (২), l আর i-এর recursive হিসাব (৪), উপসংহার (২)। যেখানে নম্বর কাটে: node-সংখ্যার ওপর সাধারণ induction করে “একটি leaf যোগ করি” — full binary tree-এ একটি node যোগ করলে tree আর full থাকে না; structural induction এই ফাঁদ এড়ায়।
নিচের ব্লক অংশ গ-এর পাঁচটি দাবি ছোট পরিসরে মেলায়, আর কোথায় দাবি ভাঙে তাও দেখায়।
from itertools import product
N = 60
print("1+3+...+(2n-1) == n^2 :", all(sum(range(1, 2 * n, 2)) == n * n for n in range(1, N)))
print("6 | n^3 - n :", all((n**3 - n) % 6 == 0 for n in range(0, N)))
print("2^n > n^2 fails at n :", [n for n in range(0, N) if not 2**n > n * n])
# 3a + 5b with a, b >= 0: which n cannot be paid?
payable = {3 * a + 5 * b for a in range(40) for b in range(25)}
print("not payable (n < 60) :", [n for n in range(1, N) if n not in payable])
# full binary trees: every node has 0 or 2 children; count leaves and internal nodes
def full_trees(size): # all full binary trees with `size` nodes
if size == 1:
yield "L"
for left in range(1, size - 1):
for a, b in product(full_trees(left), full_trees(size - 1 - left)):
yield (a, b)
def leaves(t): return 1 if t == "L" else leaves(t[0]) + leaves(t[1])
def internal(t): return 0 if t == "L" else 1 + internal(t[0]) + internal(t[1])
total = ok = 0
for size in range(1, 16, 2):
for t in full_trees(size):
total += 1
ok += leaves(t) == internal(t) + 1
print(f"full binary trees up to 15 nodes: {total}, with l = i + 1: {ok}")আসল আউটপুট (ব্রাউজারের Python):
1+3+...+(2n-1) == n^2 : True
6 | n^3 - n : True
2^n > n^2 fails at n : [2, 3, 4]
not payable (n < 60) : [1, 2, 4, 7]
full binary trees up to 15 nodes: 626, with l = i + 1: 626গ-০১ আর গ-০২ n < 60-এ মিলেছে। 2ⁿ > n² ঠিক n = 2, 3, 4-এ ভাঙে, তাই basis ৫ (গ-০৩)। ৩ আর ৫ দিয়ে যা দেওয়া যায় না: 1, 2, 4, 7; 7-এর পরে সব যায়, গ-০৪-এর সঙ্গে হুবহু মেলে। ১৫টি node পর্যন্ত সব ৬২৬টি full binary tree-এ l = i + 1 (গ-০৫)।
৫ · অংশ ঘ — গণনার প্রমাণ, bijection আর pigeonhole
রিভিশন: পর্ব ৩২ “Pigeonhole principle”, পর্ব ৩৪ “Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity”, পর্ব ৩৭ “গণনার কৌশল”, পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”. Combinatorial proof-এ একটি গল্প বলুন: “একটি সেট দুইভাবে গুনি।” দুটি গণনাই যে একই সেট গোনে, সেটি স্পষ্ট না হলে নম্বর থাকে না।
ঘ-০১Combinatorial যুক্তিতে প্রমাণ করুন: C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ. — ৫ নম্বর (সহজ)
- প্রশ্ন: n জনের দল থেকে কয়টি উপদল (খালি সহ) বাছা যায়? — একটি সেট: {1, …, n}-এর সব subset
- গণনা ১: প্রতিটি মানুষ “আছে” বা “নেই”, দুটি বিকল্প, n বার: 2ⁿ. — গুণের নিয়ম
- গণনা ২: আকার k-এর উপদল C(n, k)টি; k = 0, …, n যোগ করলে বাঁ দিক। আকারগুলো আলাদা, তাই কোনো উপদল দুবার গোনা হয়নি। — যোগের নিয়ম, ভাগগুলো disjoint
- একই সেট দুইভাবে গোনা, তাই দুই রাশি সমান। ∎
নম্বর-ভাগ: সেটের বর্ণনা (১), দুটি গণনা (১ + ২), disjoint কথাটি আর উপসংহার (১)। বিকল্প: binomial theorem-এ x = y = 1.
ঘ-০২Double counting দিয়ে প্রমাণ করুন: 1 ≤ k ≤ n হলে k · C(n, k) = n · C(n − 1, k − 1). — ১০ নম্বর (মাঝারি)
- গোনা হবে: n জন থেকে k জনের একটি কমিটি আর তার একজন অধিনায়ক — এমন (কমিটি, অধিনায়ক) জোড়া। — সেট নির্দিষ্ট করা
- গণনা ১: আগে কমিটি, C(n, k) ভাবে; তারপর তার k জনের একজন অধিনায়ক: k · C(n, k). — গুণের নিয়ম
- গণনা ২: আগে অধিনায়ক, n ভাবে; তারপর বাকি n − 1 জন থেকে কমিটির বাকি k − 1 জন: n · C(n − 1, k − 1). — গুণের নিয়ম
- প্রতিটি জোড়া দুই গণনাতেই ঠিক একবার আসে, তাই দুই রাশি সমান। ∎ — double counting
নম্বর-ভাগ: সেট (২), দুটি গণনা (৩ + ৩), “ঠিক একবার” (২)। বীজগণিতেও হয়: k · n!/(k!(n − k)!) = n!/((k − 1)!(n − k)!) = n · C(n − 1, k − 1); প্রশ্ন combinatorial চাইলে শুধু এটি আধা নম্বর পেতে পারে।
ঘ-০৩G = (V, E) একটি সসীম undirected graph (loop নেই)। প্রমাণ করুন: সব vertex-এর degree-র যোগফল = 2|E|; আর বিজোড় degree-র vertex-এর সংখ্যা জোড়। — ১০ নম্বর (সহজ থেকে মাঝারি)
- (vertex, তার সঙ্গে লাগা edge) জোড়াগুলো গুনি। vertex ধরে গুনলে যোগফল ∑ deg(v). — degree-র সংজ্ঞা
- edge ধরে গুনলে প্রতিটি edge-এর ঠিক দুটি প্রান্ত, তাই 2|E|. সুতরাং ∑ deg(v) = 2|E|. — double counting; handshake
- V-কে দুই ভাগে ভাগ করি: V₁ (বিজোড় degree), V₂ (জোড় degree). ∑V₂ deg(v) জোড়। — জোড়ের যোগফল জোড়
- তাই ∑V₁ deg(v) = 2|E| − ∑V₂ deg(v) জোড়। — জোড় − জোড়
- বিজোড় সংখ্যার যোগফল জোড় হয় কেবল তখন, যখন পদসংখ্যা জোড়; তাই |V₁| জোড়। ∎
নম্বর-ভাগ: double counting-এর সেট (২), দুই গণনা (৩), ভাগ আর parity-র যুক্তি (৪), উপসংহার (১)। যেখানে নম্বর কাটে: “প্রতিটি edge দুটি vertex-এ যায়” লিখে ২ দিয়ে গুণ, কিন্তু কোন সেট গোনা হচ্ছে তা না বলা।
ঘ-০৪n ≥ 1. Bijection দিয়ে প্রমাণ করুন: {1, …, n}-এর জোড় আকারের subset আর বিজোড় আকারের subset সমান সংখ্যক। — ৫ নম্বর (মাঝারি)
- f(S) = S △ {1} সংজ্ঞায়িত করুন: 1 ∈ S হলে 1 বাদ, না থাকলে 1 যোগ। — n ≥ 1 বলে 1 আছে
- |f(S)| = |S| ± 1, তাই f জোড় আকারকে বিজোড় আকারে নেয়, আর উল্টোটাও। — আকারের parity বদলায়
- f(f(S)) = S, তাই f নিজেই নিজের inverse; f একটি bijection. — inverse থাকলে bijection
- সসীম দুটি সেটের মধ্যে bijection থাকলে তারা সমান আকারের। ∎
নম্বর-ভাগ: f-এর সংজ্ঞা (১), parity বদল (১), bijection-এর প্রমাণ (২), উপসংহার (১)। n = 0-এ দাবি মিথ্যা (জোড় ১টি: ∅, বিজোড় ০টি) — শর্ত n ≥ 1 কেন, তা এখান থেকেই বোঝা যায়।
ঘ-০৫{1, 2, …, 2n} থেকে যেকোনো n + 1টি আলাদা সংখ্যা নিলে, প্রমাণ করুন একটি অন্যটিকে ভাগ করে। দেখান যে n টি সংখ্যায় এটি নিশ্চিত নয়। — ১০ নম্বর (কঠিন)
- প্রতিটি সংখ্যা x = 2e · m আকারে অনন্যভাবে লেখা যায়, m বিজোড় (x-এর “বিজোড় অংশ”)। — ২-এর ঘাত আলাদা করা
- 1 থেকে 2n-এর মধ্যে বিজোড় সংখ্যা n টি: 1, 3, …, 2n − 1. তাই বিজোড় অংশের সম্ভাব্য মান n টি। — খোপ
- n + 1টি সংখ্যা, n টি খোপ: দুটি সংখ্যা x = 2em, y = 2fm-এর বিজোড় অংশ একই। — pigeonhole
- x ≠ y বলে e ≠ f; ধরি e < f. তাহলে y = 2f−e · x, তাই x ∣ y. — সাধারণতা না হারিয়ে
- তীক্ষ্ণতা: {n + 1, …, 2n}-এর n টি সংখ্যায় কেউ কাউকে ভাগ করে না, কারণ x ∣ y আর x < y হলে y ≥ 2x ≥ 2n + 2. ∎
নম্বর-ভাগ: বিজোড় অংশের ধারণা (২), খোপ গোনা (২), pigeonhole প্রয়োগ (২), ভাগ দেখানো (২), তীক্ষ্ণতার উদাহরণ (২)। যেখানে নম্বর কাটে: খোপ আর কবুতর কী, নাম ধরে না বলা।
from itertools import combinations
from math import comb
print("sum C(n,k) == 2^n, n<=20 :", all(sum(comb(n, k) for k in range(n + 1)) == 2**n for n in range(21)))
print("k C(n,k) == n C(n-1,k-1) :", all(k * comb(n, k) == n * comb(n - 1, k - 1)
for n in range(1, 21) for k in range(1, n + 1)))
even = [sum(comb(n, k) for k in range(0, n + 1, 2)) for n in range(1, 8)]
odd = [sum(comb(n, k) for k in range(1, n + 1, 2)) for n in range(1, 8)]
print("even-size subsets, n=1..7 :", even)
print("odd-size subsets, n=1..7 :", odd)
# n+1 numbers from {1..2n}: is one always a divisor of another?
def has_divisor_pair(s):
return any(b % a == 0 for a, b in combinations(sorted(s), 2))
for n in range(1, 8):
sets = list(combinations(range(1, 2 * n + 1), n + 1))
good = sum(has_divisor_pair(s) for s in sets)
tight = has_divisor_pair(range(n + 1, 2 * n + 1)) # only n numbers
print(f"n={n}: {good}/{len(sets)} subsets have a pair; "
f"{{n+1..2n}} has a pair: {tight}")আসল আউটপুট (ব্রাউজারের Python):
sum C(n,k) == 2^n, n<=20 : True
k C(n,k) == n C(n-1,k-1) : True
even-size subsets, n=1..7 : [1, 2, 4, 8, 16, 32, 64]
odd-size subsets, n=1..7 : [1, 2, 4, 8, 16, 32, 64]
n=1: 1/1 subsets have a pair; {n+1..2n} has a pair: False
n=2: 4/4 subsets have a pair; {n+1..2n} has a pair: False
n=3: 15/15 subsets have a pair; {n+1..2n} has a pair: False
n=4: 56/56 subsets have a pair; {n+1..2n} has a pair: False
n=5: 210/210 subsets have a pair; {n+1..2n} has a pair: False
n=6: 792/792 subsets have a pair; {n+1..2n} has a pair: False
n=7: 3003/3003 subsets have a pair; {n+1..2n} has a pair: Falseঘ-০১ আর ঘ-০২ n ≤ 20-এ মিলেছে। জোড় আর বিজোড় আকারের subset প্রতিটি n-এ সমান, 2n−1টি করে (ঘ-০৪)। ঘ-০৫: n = 7-এ ৩০০৩টি (C(14, 8)) বাছাইয়ের প্রতিটিতে ভাগ করার জোড়া আছে, অথচ {n + 1, …, 2n}-এর n টি সংখ্যায় একটিও নেই — দাবি আর তার তীক্ষ্ণতা দুটোই।
৬ · অংশ ঙ — সংখ্যাতত্ত্ব, relation, graph, tree আর group
রিভিশন: পর্ব ২১ “GCD আর Euclid-এর algorithm”, পর্ব ৫৫ “Equivalence relation আর partition”, পর্ব ৬২ “Planar graph”, পর্ব ৬৫ “Tree”, পর্ব ৭০ “Group”. এই দলে প্রমাণ সাধারণত সংজ্ঞা আর একটি আগের উপপাদ্যের ওপর দাঁড়ায়; কোন উপপাদ্য, তা নাম ধরে আর শর্তসহ লিখুন।
ঙ-০১a, b পূর্ণসংখ্যা, b > 0, আর r = a mod b. প্রমাণ করুন: gcd(a, b) = gcd(b, r). — ১০ নম্বর (মাঝারি)
- Division algorithm: a = qb + r, 0 ≤ r < b. — পর্ব ২০
- d ∣ a আর d ∣ b হলে d ∣ a − qb = r. তাই (a, b)-এর প্রতিটি common divisor (b, r)-এরও common divisor. — রৈখিক সমাহারকে ভাগ করে
- d ∣ b আর d ∣ r হলে d ∣ qb + r = a. তাই উল্টোটাও সত্য। — একই নিয়ম
- দুই জোড়ার common divisor-এর সেট হুবহু এক, তাই তাদের সবচেয়ে বড়টিও এক। ∎ — সেটের সমতা ⇒ সর্বোচ্চের সমতা
নম্বর-ভাগ: division algorithm (১), দুই দিকের অন্তর্ভুক্তি (৩ + ৩), সেট এক বলে gcd এক (৩)। এই lemma-ই Euclid-এর algorithm-এর সঠিকতা; থামার প্রমাণ আলাদা (r < b, ভাগশেষ কড়াভাবে কমে)।
ঙ-০২R একটি সেট A-এর ওপর equivalence relation. প্রমাণ করুন: দুটি equivalence class [a] আর [b] হয় সমান, নয়তো disjoint. — ১০ নম্বর (মাঝারি)
- ধরি [a] ∩ [b] ≠ ∅; কোনো c-এর জন্য aRc আর bRc. দেখাব [a] = [b]. — disjoint না হলে সমান, এই রূপে
- cRb (symmetric), তাই aRc আর cRb থেকে aRb (transitive). — equivalence relation-এর ধর্ম
- x ∈ [b] নিন: bRx. aRb আর bRx থেকে aRx, তাই x ∈ [a]. সুতরাং [b] ⊆ [a]. — transitive
- aRb থেকে bRa (symmetric); একই যুক্তিতে [a] ⊆ [b]. তাই [a] = [b]. ∎ — double inclusion
নম্বর-ভাগ: রূপটি ঠিকভাবে বসানো (২), aRb (২), দুই দিকের ⊆ (৩ + ২), উপসংহার (১)। এ থেকেই class-গুলো A-এর একটি partition (reflexive বলে প্রতিটি a ∈ [a], তাই কোনো class খালি নয় আর সবাই কোথাও আছে)।
ঙ-০৩প্রমাণ করুন: n ≥ 2 vertex-এর প্রতিটি tree-তে অন্তত দুটি leaf আছে; এ থেকে induction-এ দেখান যে n vertex-এর tree-তে ঠিক n − 1টি edge. — ১০ নম্বর (মাঝারি)
প্রথম অংশ extremal যুক্তি: “সবচেয়ে লম্বা path” নিন।
- Tree-টি connected আর n ≥ 2, তাই অন্তত একটি edge আছে; সসীম graph-এ সবচেয়ে লম্বা simple path P = v₀v₁…vm আছে, m ≥ 1. — সসীম সেটে সর্বোচ্চ থাকে
- v₀-এর v₁ ছাড়া আর কোনো প্রতিবেশী w থাকলে: w P-তে থাকলে একটি cycle হয় (tree-তে অসম্ভব); না থাকলে wv₀…vm আরও লম্বা path (P-এর সর্বোচ্চতার বিরোধী)। তাই deg(v₀) = 1; একই যুক্তিতে deg(vm) = 1. — দুটি ক্ষেত্র, দুটিই বিরোধ
- Induction: n = 1-এ 0টি edge. n ≥ 2-তে একটি leaf v মুছলে T − v এখনো connected আর acyclic, অর্থাৎ n − 1 vertex-এর tree; hypothesis-এ তার n − 2টি edge. — leaf মুছলে কোনো path ভাঙে না
- v-এর একটিই edge ছিল, তাই T-এর edge (n − 2) + 1 = n − 1. ∎
নম্বর-ভাগ: সবচেয়ে লম্বা path-এর অস্তিত্ব (২), দুই ক্ষেত্রে বিরোধ (৩), leaf মুছেও tree কেন (৩), গণনা (২)। যেখানে নম্বর কাটে: “n − 1 vertex-এর tree-তে একটি vertex যোগ করি” — এটি build-up ভুল (অংশ ৮, ত-০৬); সঠিক পথ: বড় tree থেকে মুছে ছোটতে নামা।
ঙ-০৪প্রমাণ করুন: V ≥ 3 vertex-এর একটি connected simple planar graph-এ E ≤ 3V − 6. এ থেকে দেখান K₅ planar নয়। — ১০ নম্বর (মাঝারি থেকে কঠিন)
- Euler-এর সূত্র (connected planar graph, একটি plane আঁকায়): V − E + F = 2. — পর্ব ৬২-এর উপপাদ্য, শর্তসহ
- প্রতিটি face-এর সীমানায় অন্তত ৩টি edge (simple, V ≥ 3), আর প্রতিটি edge সর্বোচ্চ দুটি face-এর সীমানায়; face ধরে গুনলে 3F ≤ ∑ deg(face) = 2E. — face-এর handshake, double counting
- F ≤ 2E/3 বসালে 2 = V − E + F ≤ V − E + 2E/3, অর্থাৎ E ≤ 3V − 6. — বীজগণিত
- K₅: V = 5, E = 10, কিন্তু 3V − 6 = 9 < 10. K₅ connected আর simple, তাই planar হতে পারে না। ∎ — contrapositive প্রয়োগ
নম্বর-ভাগ: Euler-এর সূত্র শর্তসহ (২), 3F ≤ 2E কারণসহ (৪), বীজগণিত (২), K₅ (২)। যেখানে নম্বর কাটে: K₃,₃-এ একই সূত্র লাগানো: 9 ≤ 12, তাই সূত্রটি কিছুই প্রমাণ করে না। K₃,₃ bipartite, তাতে triangle নেই, প্রতিটি face-এ অন্তত ৪টি edge: E ≤ 2V − 4 = 8 < 9.
ঙ-০৫(G, ·) একটি group. প্রমাণ করুন: প্রতিটি উপাদানের inverse অনন্য। — ৫ নম্বর (সহজ)
- ধরি b আর c দুটিই a-এর inverse: ab = ba = e আর ac = ca = e. — অনন্যতার প্রমাণে “দুটি ধরে সমান দেখানো”
- b = be = b(ac) = (ba)c = ec = c. ∎ — identity, c inverse, associativity, b inverse, identity
নম্বর-ভাগ: দুটি inverse ধরা (১), সমতার শিকল (৩), প্রতিটি সমান-চিহ্নের কারণ (১)। যেখানে নম্বর কাটে: commutativity ব্যবহার — group সাধারণত commutative নয়; associativity-ই এখানে যথেষ্ট। অস্তিত্ব আলাদা কথা: তা group-এর axiom থেকেই আসে।
import random
from math import gcd, comb
random.seed(82)
# gcd(a, b) == gcd(b, a mod b) on random pairs
pairs = [(random.randint(1, 10**9), random.randint(1, 10**6)) for _ in range(10000)]
print("gcd(a,b) == gcd(b, a mod b):", all(gcd(a, b) == gcd(b, a % b) for a, b in pairs))
# random labelled trees: attach vertex v to a random earlier vertex
def random_tree(n):
return [(v, random.randrange(v)) for v in range(1, n)]
leaf_ok = edge_ok = 0
for _ in range(2000):
n = random.randint(2, 30)
E = random_tree(n)
deg = [0] * n
for u, v in E:
deg[u] += 1; deg[v] += 1
edge_ok += len(E) == n - 1
leaf_ok += sum(d == 1 for d in deg) >= 2
print("2000 random trees: n-1 edges", edge_ok, "| at least 2 leaves", leaf_ok)
# planar edge bounds: K5 and K3,3
V, E = 5, comb(5, 2)
print(f"K5 : E = {E}, 3V-6 = {3 * V - 6}, E <= 3V-6? {E <= 3 * V - 6}")
V, E = 6, 9
print(f"K3,3: E = {E}, 3V-6 = {3 * V - 6}, 2V-4 = {2 * V - 4}, "
f"E <= 2V-4? {E <= 2 * V - 4}")আসল আউটপুট (ব্রাউজারের Python):
gcd(a,b) == gcd(b, a mod b): True
2000 random trees: n-1 edges 2000 | at least 2 leaves 2000
K5 : E = 10, 3V-6 = 9, E <= 3V-6? False
K3,3: E = 9, 3V-6 = 12, 2V-4 = 8, E <= 2V-4? Falseদশ হাজার এলোমেলো জোড়ায় ঙ-০১-এর lemma মিলেছে। প্রতিটি নতুন vertex-কে আগের কোনো একটির সঙ্গে জুড়ে বানানো ২০০০টি tree-র সবগুলোতে n − 1টি edge আর অন্তত দুটি leaf (ঙ-০৩)। K₅-এ 10 > 9, তাই E ≤ 3V − 6 ভাঙে; K₃,₃-এ 9 ≤ 12 বলে সেই সূত্র চুপ, কিন্তু ত্রিভুজহীন সীমা 2V − 4 = 8 ভাঙে।
৭ · অংশ চ — Invariant, diagonal আর অসম্ভবতার প্রমাণ
“কখনো সম্ভব নয়” ধরনের দাবিতে খুঁজুন এমন একটি রাশি, যা প্রতিটি চালে বদলায় না: এটাই invariant. শুরুর আর লক্ষ্যের মান আলাদা হলে লক্ষ্যে পৌঁছানো অসম্ভব। Loop invariant (পর্ব ১৩ “Program-এর সঠিকতা”) একই ধারণা, কোডের লুপে। রিভিশন: পর্ব ১৮ “Cardinality”, পর্ব ৭৪ “Finite automaton আর regular expression-এর পরিচয়”।
চ-০১৮ × ৮ দাবার বোর্ড থেকে দুটি বিপরীত কোণের ঘর কেটে ফেলা হলো (৬২টি ঘর)। প্রমাণ করুন: পাশাপাশি দুটি ঘর ঢাকে এমন ৩১টি domino দিয়ে বোর্ডটি ঢাকা যায় না। — ১০ নম্বর (মাঝারি)
- ঘর (r, c)-কে রং দিন: r + c জোড় হলে সাদা, বিজোড় হলে কালো। পূর্ণ বোর্ডে ৩২ সাদা, ৩২ কালো। — রঙের invariant বেছে নেওয়া
- বিপরীত কোণ (0, 0) আর (7, 7): দুটিতেই r + c জোড়, অর্থাৎ দুটিই সাদা। কাটার পরে ৩০ সাদা, ৩২ কালো। — হিসাব
- পাশাপাশি দুটি ঘরে r + c-এর parity আলাদা, তাই প্রতিটি domino ঠিক একটি সাদা আর একটি কালো ঢাকে। — invariant: প্রতি domino-তে (১, ১)
- ৩১টি domino ঢাকবে ৩১ সাদা আর ৩১ কালো; অথচ আছে ৩০ সাদা। বিরোধ, তাই ঢাকা অসম্ভব। ∎
নম্বর-ভাগ: রঙের নিয়ম (২), কাটার পরের গণনা (২), প্রতি domino-র রং কারণসহ (৪), বিরোধ (২)। যেখানে নম্বর কাটে: কয়েকটি সাজানোর চেষ্টা ব্যর্থ দেখিয়ে “অসম্ভব” বলা — সব সাজানো দেখা হয়নি।
চ-০২বোর্ডে 1, 2, …, 10 লেখা। প্রতি চালে যেকোনো দুটি সংখ্যা a, b মুছে |a − b| লেখা হয়, যতক্ষণ না একটি সংখ্যা থাকে। প্রমাণ করুন: শেষ সংখ্যাটি সবসময় বিজোড়। — ৫ নম্বর (মাঝারি)
- Invariant: বোর্ডের সব সংখ্যার যোগফলের parity. শুরুতে 1 + … + 10 = 55, বিজোড়। — যোগফলের সূত্র
- এক চালে যোগফল বদলায় −a − b + |a − b|. |a − b| আর a + b-এর parity এক (a − b আর a + b-এর পার্থক্য 2b), তাই বদলটি জোড়। — parity অপরিবর্তিত
- প্রতিটি চালে সংখ্যা একটি কমে, তাই ৯ চালে খেলা থামে; শেষ সংখ্যাই তখন যোগফল, যা বিজোড়। ∎ — invariant + থামা
নম্বর-ভাগ: invariant চেনা (১), বদল জোড় কারণসহ (২), থামা আর উপসংহার (২)। শেষ মান কোন বিজোড় সংখ্যা হবে, তা চালের ওপর নির্ভর করে; ব্লকে ১, ৩, ৫, ৭, ৯ সবই এসেছে।
চ-০৩যেকোনো সেট S-এর জন্য প্রমাণ করুন: S থেকে তার power set P(S)-এ কোনো onto ফাংশন নেই (Cantor-এর উপপাদ্য)। — ১০ নম্বর (কঠিন)
- বিপরীতে ধরি f: S → P(S) onto. — contradiction
- D = {x ∈ S : x ∉ f(x)} নিন; D ⊆ S, তাই D ∈ P(S). — diagonal সেট
- f onto, তাই কোনো d ∈ S-এর জন্য f(d) = D. — onto-র সংজ্ঞা
- d ∈ D হলে D-এর সংজ্ঞায় d ∉ f(d) = D; d ∉ D হলে d ∉ f(d), তাই সংজ্ঞায় d ∈ D. দুটিই বিরোধ। ∎ — দুটি ক্ষেত্র
নম্বর-ভাগ: অনুমান (১), D-এর সংজ্ঞা (৩), d-এর অস্তিত্ব (২), দুই ক্ষেত্রের বিরোধ (৪)। S অসীম হলেও প্রমাণ একই, তাই |S| < |P(S)| সব সেটে; S = ℕ নিলে P(ℕ) uncountable.
চ-০৪Pumping lemma দিয়ে প্রমাণ করুন: L = {0ⁿ1ⁿ : n ≥ 0} regular language নয়। — ১০ নম্বর (কঠিন)
- বিপরীতে ধরি L regular; তাহলে কোনো pumping length p আছে। — pumping lemma, পর্ব ৭৪
- s = 0p1p ∈ L নিন, |s| = 2p ≥ p. Lemma বলে s = xyz, যেখানে |xy| ≤ p, |y| ≥ 1, আর সব i ≥ 0-এর জন্য xyiz ∈ L. — s আমরা বাছি; বিভাজন বাছে lemma
- |xy| ≤ p, তাই x আর y দুটিই প্রথম p টি 0-এর ভেতরে: y = 0t, t ≥ 1. — যেকোনো বৈধ বিভাজনের জন্য
- i = 2: xy²z = 0p+t1p, যেখানে 0 বেশি, তাই ∉ L. বিরোধ; L regular নয়। ∎
নম্বর-ভাগ: অনুমান আর p (১), s-এর বাছাই (২), সব বিভাজনের জন্য যুক্তি (৪), pump করে বিরোধ (৩)। যেখানে নম্বর কাটে: একটি নির্দিষ্ট বিভাজন বেছে নেওয়া (“y = 01 ধরি”); বিভাজন lemma দেয়, আপনাকে সবগুলো সামলাতে হয়। Automata-র পূর্ণ তত্ত্ব পরিকল্পিত Theory of Computation কোর্সের বিষয়।
import random
from itertools import product
random.seed(82)
# board game: replace two numbers a, b by |a - b| until one number is left
finals = set()
for _ in range(2000):
nums = list(range(1, 11))
while len(nums) > 1:
a = nums.pop(random.randrange(len(nums)))
b = nums.pop(random.randrange(len(nums)))
nums.append(abs(a - b))
finals.add(nums[0])
print("last numbers seen:", sorted(finals))
# 8x8 board without two opposite corners: count the two colours
cells = [(r, c) for r in range(8) for c in range(8) if (r, c) not in {(0, 0), (7, 7)}]
dark = sum((r + c) % 2 == 0 for r, c in cells)
print("cells:", len(cells), "| colour A:", dark, "| colour B:", len(cells) - dark)
# Cantor: no f: S -> P(S) is onto, for S = {0, 1, 2}
S = range(3)
subsets = [frozenset(x for x in S if m >> x & 1) for m in range(8)]
onto = hit_D = 0
for f in product(subsets, repeat=3): # f[x] is the image of x
onto += len(set(f)) == 8
D = frozenset(x for x in S if x not in f[x]) # the diagonal set
hit_D += D in f
print("functions:", 8**3, "| onto:", onto, "| D in image:", hit_D)আসল আউটপুট (ব্রাউজারের Python):
last numbers seen: [1, 3, 5, 7, 9]
cells: 62 | colour A: 30 | colour B: 32
functions: 512 | onto: 0 | D in image: 0দুই হাজার এলোমেলো খেলায় শেষ সংখ্যা শুধু বিজোড়: 1, 3, 5, 7, 9 (চ-০২)। কাটা বোর্ডে ৬২টি ঘর, এক রঙের ৩০, অন্যটির ৩২ (চ-০১)। S = {0, 1, 2}-এ সব ৫১২টি ফাংশনের একটিও onto নয়, আর diagonal সেট D কোনো ফাংশনের image-এ আসেনি — চ-০৩-এর যুক্তি হুবহু (তবে প্রমাণ সব S-এর, ব্লক শুধু একটির)।
৮ · ভুল প্রমাণ ধরুন — ছয়টি ফাঁদ আর সংশোধন
প্রতিটি “প্রমাণ” পড়ে আগে নিজে ভুলের লাইনটি খুঁজুন, তারপর খুলুন। ভালো উত্তরে তিনটি জিনিস থাকে: কোন লাইন ভুল, কেন ভুল (সম্ভব হলে একটি counterexample), আর সংশোধিত প্রমাণ বা সঠিক দাবি।
ত-০১দাবি: “n² জোড় হলে n জোড়।” প্রমাণ: “ধরি n = 2k. তাহলে n² = 4k² = 2(2k²), জোড়। ∎” ভুল কোথায়? — ৫ নম্বর (সহজ)
ভুল: প্রমাণটি দাবির converse (“n জোড় ⇒ n² জোড়”) দেখায়। Converse সত্য হলেও মূল দাবি মিথ্যা হতে পারে: “4 ∣ n ⇒ 4 ∣ n²” সত্য, অথচ “4 ∣ n² ⇒ 4 ∣ n” মিথ্যা (n = 2). সংশোধন: ক-০২-এর contrapositive প্রমাণ।
ত-০২দাবি: 1 + 2 + … + n = n(n + 1)/2. “Step: P(k + 1) সত্য ধরি: 1 + … + (k + 1) = (k + 1)(k + 2)/2. দুই দিক থেকে (k + 1) বাদ দিলে 1 + … + k = k(k + 1)/2, যা P(k), সত্য। তাই P(k + 1) সত্য। ∎” ভুল কোথায়? — ৫ নম্বর (মাঝারি)
ভুল: যা প্রমাণ করার কথা (P(k + 1)), তা ধরে নিয়ে একটি সত্য কথায় পৌঁছানো হয়েছে: চক্রাকার যুক্তি। সত্য সিদ্ধান্ত থেকে অনুমান সত্য হয় না (0 = 1 ধরে দুই দিককে 0 দিয়ে গুণ করলে 0 = 0). সংশোধন: P(k) থেকে শুরু: 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2. এখানে প্রতিটি ধাপ উল্টানো যায় বলে খসড়ার চিন্তাটি কাজে লাগে, কিন্তু খাতায় দিক ঠিক রাখতে হয়।
ত-০৩“ধরি a = b. তাহলে a² = ab, a² − b² = ab − b², (a + b)(a − b) = b(a − b), a + b = b, 2b = b, তাই 2 = 1. ∎” ভুল কোথায়? — ৫ নম্বর (সহজ)
ভুল: (a + b)(a − b) = b(a − b) থেকে a + b = b লিখতে দুই দিককে (a − b) দিয়ে ভাগ করা হয়েছে; a = b বলে a − b = 0, আর শূন্য দিয়ে ভাগ অবৈধ। শেষ ধাপে b দিয়ে ভাগও b ≠ 0 না জেনে করা। সংশোধন: xy = xz থেকে y = z শুধু x ≠ 0 হলে; সাধারণভাবে x(y − z) = 0 থেকে x = 0 বা y = z. প্রতিটি ভাগের আগে “ভাজক শূন্য নয়, কারণ …” লিখুন।
ত-০৪“দাবি: যেকোনো n ≥ 1 টি ঘোড়ার দলে সবার রং এক। Basis n = 1 স্পষ্ট। Step: k + 1টি ঘোড়ার দলে প্রথম k টি এক রঙের, শেষ k টিও এক রঙের (hypothesis), আর মাঝের ঘোড়াগুলো দুই দলেই আছে, তাই সবাই এক রঙের। ∎” ভুল কোথায়? — ১০ নম্বর (মাঝারি)
ভুল: step সব k ≥ 1-এর জন্য দাবি করা হয়েছে, কিন্তু k = 1-এ (দুটি ঘোড়া) দুই দলের মিল খালি; নিচের stepper ধাপে ধাপে দেখায়। P(1) ⇒ P(2) প্রমাণ হয়নি, তাই শিকল প্রথম কড়াতেই ছেঁড়া। দাবিটি মিথ্যা: একটি সাদা আর একটি কালো ঘোড়া। শিক্ষা: step-এর প্রতিটি যুক্তি সবচেয়ে ছোট k-তেও খাটে কি না দেখুন (পর্ব ১০-এর §৮)।
| k + 1 | |
| A (প্রথম k) | |
| B (শেষ k) | |
| A ∩ B | |
| রায় |
- k + 1 = 4. A আর B-এর মিল {h₂, h₃}: A-র রং = h₂-এর রং = B-র রং। এখানে যুক্তি ঠিক।
- k + 1 = 3. মিল শুধু h₂, তবু একটি “সেতু” আছে। যুক্তি এখনো ঠিক।
- k + 1 = 2. A = {h₁}, B = {h₂}, মিল খালি। দুই দলের রং যুক্ত করার কোনো ঘোড়া নেই।
- ফাঁকের নাম। P(1) সত্য, কিন্তু P(1) ⇒ P(2) প্রমাণ হয়নি। P(2) মিথ্যা হলে বড় সব k-এর step সত্য হলেও কাজে লাগে না।
- শিক্ষা। Induction-এর শিকলে প্রতিটি কড়া লাগে; সবচেয়ে ছোট step-টি আলাদা করে পরীক্ষা করুন।
ত-০৫“৪ জন (A, B, C, D) থেকে ২ জনের কমিটি: প্রথম সদস্য ৪ ভাবে, দ্বিতীয় ৩ ভাবে, তাই 4 × 3 = 12টি কমিটি।” ভুল কোথায়? — ৫ নম্বর (সহজ)
ভুল: গুণের নিয়ম ক্রমসহ জোড়া গোনে; কমিটিতে ক্রম নেই, তাই {A, B} একবার (A, B) আর একবার (B, A) হিসেবে, দুবার গোনা হয়েছে (overcounting). প্রতিটি কমিটি ঠিক ২ বার এসেছে, তাই ভাগের নিয়ম: 12/2 = 6 = C(4, 2). শিক্ষা: “প্রতিটি বস্তু কতবার গোনা হলো?” প্রশ্নটি করুন (পর্ব ৩১ “গণনার মূল নিয়ম”)।
ত-০৬“দাবি: যে graph-এর প্রতিটি vertex-এর degree ≥ 1, তা connected. Induction on n: n = 2-এ একটি edge, connected. Step: n vertex-এর এমন একটি connected graph নিন, একটি নতুন vertex যোগ করে একটি edge দিয়ে জুড়ুন; ফলও connected. ∎” ভুল কোথায়? — ১০ নম্বর (কঠিন)
ভুল: Step-টি শুধু সেই n + 1 vertex-এর graph-গুলো বানায়, যা একটি ছোট connected graph-এ vertex জুড়ে পাওয়া যায়; “degree ≥ 1”-এর সব graph এভাবে আসে না। এই “build-up” ভুলে প্রমাণ সব ক্ষেত্র ঢাকে না। দাবি মিথ্যা: দুটি আলাদা edge 0–1 আর 2–3, সবার degree 1, কিন্তু দুটি component (ব্লকে মেলানো)। সঠিক কাঠামো: step-এ যেকোনো n + 1 vertex-এর graph নিয়ে শুরু করুন, তা থেকে একটি vertex মুছে hypothesis লাগান, আর মোছার পরও শর্ত টিকে আছে কি না দেখান (ঙ-০৩ এভাবে লেখা)। এখানে মোছার পরে শর্তই ভাঙতে পারে, আর তাতেই ফাঁক ধরা পড়ে।
from itertools import combinations, permutations
# T-01: proving the converse. "4 | n -> 4 | n^2" is true,
# but the claim "4 | n^2 -> 4 | n" is false:
print("4 | n^2 but not 4 | n:", [n for n in range(1, 30) if n * n % 4 == 0 and n % 4][:5])
# T-04: "2^n > n^2" -- where do the basis and the step hold?
print("2k^2 >= (k+1)^2 fails at k:", [k for k in range(1, 20) if 2 * k * k < (k + 1) ** 2])
print("2^n > n^2 fails at n :", [n for n in range(1, 20) if not 2**n > n * n])
# T-05: "2-person committees from 4 people = 4 * 3 = 12"
people = "ABCD"
ordered = list(permutations(people, 2))
print("ordered pairs:", len(ordered),
"| distinct committees:", len(set(map(frozenset, ordered))),
"| C(4,2):", len(list(combinations(people, 2))))
# T-06: build-up error. "every graph whose degrees are all >= 1 is connected"
E = [(0, 1), (2, 3)] # two separate edges
deg = {v: sum(v in e for e in E) for v in range(4)}
reach, todo = {0}, [0] # search from vertex 0
while todo:
u = todo.pop()
for a, b in E:
for x, y in ((a, b), (b, a)):
if x == u and y not in reach:
reach.add(y); todo.append(y)
print("degrees:", deg, "| reachable from 0:", sorted(reach))আসল আউটপুট (ব্রাউজারের Python):
4 | n^2 but not 4 | n: [2, 6, 10, 14, 18]
2k^2 >= (k+1)^2 fails at k: [1, 2]
2^n > n^2 fails at n : [2, 3, 4]
ordered pairs: 12 | distinct committees: 6 | C(4,2): 6
degrees: {0: 1, 1: 1, 2: 1, 3: 1} | reachable from 0: [0, 1]প্রথম লাইন ত-০১-এর counterexample: n = 2, 6, 10, …-এ 4 ∣ n², অথচ 4 ∤ n. দ্বিতীয় আর তৃতীয় লাইন গ-০৩-এর ছক: 2k² ≥ (k + 1)² ভাঙে k = 1, 2-এ, আর দাবি ভাঙে n = 2, 3, 4-এ; তাই step আর basis দুটোই দেখতে হয়। ক্রমসহ জোড়া ১২টি, আলাদা কমিটি ৬টি (ত-০৫)। শেষ লাইনে প্রতিটি degree 1, অথচ 0 থেকে শুধু 0 আর 1-এ পৌঁছানো যায়: graph connected নয় (ত-০৬)।
৯ · সাধারণ ভুলের ছক আর পরীক্ষার হলের কৌশল
| ভুল | কেমন দেখায় | ঠিক কাজ |
|---|---|---|
| উদাহরণকে প্রমাণ বলা | “n = 1, 2, 3-এ মেলে, তাই সত্য” | উদাহরণ খসড়ায়; খাতায় সাধারণ n |
| Converse প্রমাণ | p → q-এর বদলে q → p | প্রথম লাইনে অনুমান আর সিদ্ধান্ত আলাদা লেখা |
| চক্রাকার যুক্তি | সিদ্ধান্ত ধরে সত্য কথায় পৌঁছানো | অনুমান থেকে শুরু, সিদ্ধান্তে শেষ |
| একই অক্ষর দুই বস্তুর জন্য | m = 2k + 1, n = 2k + 1 | প্রতিটি নতুন বস্তুর নতুন অক্ষর |
| শূন্যে ভাগ বা ঋণাত্মকে অসমতা | শর্ত ছাড়া ভাগ | ভাগের আগে “≠ 0, কারণ …” |
| Induction-এ basis বা ছোট step বাদ | ঘোড়ার রং, 2ⁿ > n² n = 1 থেকে | সবচেয়ে ছোট step আলাদা করে যাচাই |
| অপূর্ণ ক্ষেত্র | শুধু ধনাত্মক n, বা শুধু জোড় | “ক্ষেত্রগুলো সব সম্ভাবনা ঢাকে” লেখা |
| শর্ত ছাড়া উপপাদ্য | K₃,₃-এ E ≤ 3V − 6, ভুল সিদ্ধান্ত | উপপাদ্যের নাম আর শর্ত মিলিয়ে লেখা |
| দুবার গোনা | কমিটিতে 4 × 3 | প্রতিটি বস্তু কতবার গোনা হলো, যাচাই |
| Build-up induction | ছোট থেকে বড় বানানো | বড় যেকোনো বস্তু থেকে ছোটতে নামা |
হলে সময়: মোট মিনিট ÷ মোট নম্বর দিয়ে প্রতিটি প্রশ্নের সময় ঠিক করুন। আটকে গেলে পদ্ধতির ঘোষণা, অনুমান, আর induction হলে basis ও hypothesis লিখে এগিয়ে যান; এগুলোতেই সাধারণত আংশিক নম্বর থাকে। যে ধাপ পারেননি, সেখানে “এখানে দেখাতে হবে যে …” লিখে বাকিটা শেষ করুন — সৎভাবে ফাঁক দেখানো ভুল দাবির চেয়ে ভালো। “স্পষ্টতই” শব্দটি তখনই লিখুন, যখন এক লাইনে কারণটিও দিতে পারেন।
আরও গভীরে: Lean-এর মতো proof assistant প্রতিটি ধাপকে axiom আর নিয়মে ভাঙিয়ে পরীক্ষা করে; খাতার প্রমাণ সেই অর্থে “informal”, পাঠকের বোঝার ওপর নির্ভর করে। এই পাতার প্রতিটি ধাপের পাশে কারণ লেখার অভ্যাস সেই আনুষ্ঠানিক যাচাইয়ের দিকেই প্রথম পা। Formal proof আর informal proof-এর পার্থক্য পর্ব ০৬ “অনুমানের নিয়ম”-এ দেখেছেন।
১০ · AI-এর যুগে — AI-এর লেখা প্রমাণ যাচাই
AI সহকারী প্রমাণের খসড়া দ্রুত লেখে, আর প্রায়ই সুন্দর ভাষায় ভুল লেখে: আত্মবিশ্বাসী কিন্তু চক্রাকার যুক্তি, দাবির বদলে converse প্রমাণ, induction-এ basis বাদ বা ছোট step-এ ভাঙা যুক্তি (ঘোড়ার রং), শূন্য হতে পারে এমন রাশিতে ভাগ, গণনায় off-by-one বা ক্রম গুলিয়ে দুবার গোনা, শর্ত ছাড়া উপপাদ্য (Euler-এর সূত্র connected না বলে, Fermat p ∤ a না বলে), বড় সংখ্যায় modular হিসাবে ভুল, আর এমন বই বা পাতার নাম যা নেই। তাই AI-কে লেখক নয়, কড়া পরীক্ষক বানান, আর প্রতিটি দাবি নিজে মেলান।
নিজের লেখা প্রমাণ AI-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি induction প্রমাণ খাতায় লেখার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- P(n) কী, আর কোন n থেকে, স্পষ্ট লেখা
- Basis: সবচেয়ে ছোট মান (বা মানগুলো) সরাসরি যাচাই
- Inductive hypothesis: P(k) (strong হলে সব আগের মান) ধরে নেওয়া
- Step: P(k + 1)-এর ভেতরে hypothesis খুঁজে বের করে প্রমাণ
- উপসংহার: induction-এর নীতি অনুযায়ী সব n-এ P(n), তারপর ∎
(সহজ) n একটি পূর্ণসংখ্যা। “n² জোড় হলে n জোড়” — এর contrapositive কোনটি?
- n জোড় হলে n² জোড়
- n বিজোড় হলে n² বিজোড়
- n² বিজোড় হলে n বিজোড়
- n বিজোড় হলে n² জোড়
(মাঝারি) “সব n ≥ n₀-এর জন্য 2ⁿ > n²” induction-এ প্রমাণ করতে চান। দাবিটি সত্য এমন ক্ষুদ্রতম n₀ কোনটি, যেখান থেকে এটি আর কখনো ভাঙে না?
- 1
- 3
- 4
- 5
(মাঝারি) “প্রতিটি n ≥ 8-কে 3a + 5b (a, b ≥ 0) রূপে লেখা যায়” — step-এ P(k + 1) আনতে P(k − 2) ব্যবহার করা হলো (একটি ৩ যোগ করে)। কয়টি basis লাগবে?
- ১টি (n = 8)
- ২টি (n = 8, 9)
- ৩টি (n = 8, 9, 10)
- ৫টি (n = 8 থেকে 12)
(সহজ) “বাজারঘরের যেকোনো ৩৬৭ জন গ্রাহকের মধ্যে অন্তত দুজনের জন্মদিন (মাস আর তারিখ) একই” — কোন পদ্ধতি সবচেয়ে সরাসরি?
- Pigeonhole principle
- Constructive: দুজনকে নাম ধরে দেখানো
- গ্রাহক-সংখ্যার ওপর induction
- Counterexample
(মাঝারি) একটি connected simple planar graph-এ 10টি vertex. সর্বোচ্চ কয়টি edge থাকতে পারে?
- 45
- 24
- 30
- 16
(কঠিন) “যেকোনো n ≥ 1 টি ঘোড়া এক রঙের” — induction-এর “প্রমাণে” ঠিক কোথায় ফাঁক?
- Basis n = 1 মিথ্যা
- Hypothesis ধরে নেওয়া অবৈধ
- Step k = 1 থেকে k + 1 = 2-এ ব্যর্থ
- Step শুধু বড় k-তে ব্যর্থ
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- আগে পড়া: অনুমান, সিদ্ধান্ত আর quantifier আলাদা করুন; সংকেত দেখে পদ্ধতি বাছুন, আর প্রথম লাইনেই পদ্ধতির নাম লিখুন।
- প্রতিটি ধাপে কারণ: সংজ্ঞা, উপপাদ্য (শর্তসহ), বীজগণিত বা hypothesis; প্রতিটি নতুন বস্তুর নতুন অক্ষর; ভাগের আগে ভাজক ≠ 0.
- Induction: P(n), basis, hypothesis, step আলাদা; step যত ধাপ পেছনে যায়, তত basis; recursive বস্তুতে structural induction, আর বড় থেকে ছোটতে নামা।
- গণনা আর অসম্ভবতা: double counting-এ সেটের নাম বলুন; pigeonhole-এ খোপ আর কবুতর; invariant-এ শুরু আর লক্ষ্যের মান তুলনা; extremal-এ সবচেয়ে লম্বা বা ছোটটি নিন।
- যাচাই আর সততা: খসড়ায় ছোট মানে মেলান, কিন্তু উদাহরণকে প্রমাণ বলবেন না; না পারলে ফাঁকটি সৎভাবে চিহ্নিত করুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৮৩ · ইন্টারভিউ আর contest-এর গণিত — puzzle, counting আর graphপরবর্তী পর্বধাঁধা, গণনা, সম্ভাবনা আর graph-এর ইন্টারভিউ প্রশ্ন, যুক্তিসহ সমাধান।
- পর্ব ০৮ · প্রমাণের পদ্ধতি — direct, contrapositive আর contradictionরিভিশনঅংশ ক আর খ-এর পদ্ধতিগুলোর মূল আলোচনা।
- পর্ব ১০ · Mathematical inductionরিভিশনযোগফল, অসমতা, বিভাজ্যতা আর ঘোড়ার রঙের ফাঁদ।
- পর্ব ৩৭ · গণনার কৌশলরিভিশনBijection আর double counting-এর আরও উদাহরণ।
- ডিসক্রিট ম্যাথমেটিক্স · কোর্স হোম৮৩টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- DSA · পর্ব ০৩ · অ্যালগরিদম ঠিক কি না — loop invariant আর inductionকোডে প্রয়োগএকই প্রমাণের কৌশল অ্যালগরিদমের সঠিকতায়।