Discrete Mathematics MCQ — প্রশ্নব্যাংক ব্যাখ্যাসহ | পর্ব ৮০

এক নজরে · এই পাতা কীভাবে ব্যবহার করবেন

৭৪টি প্রশ্ন, কোর্সের ক্রমে: প্রথমে অনুশীলনের কৌশল, তারপর সাতটি ভাগে মডিউল ১ থেকে ১৩-এর ৬৪টি প্রশ্ন, আর শেষে ১০টি প্রশ্নের মিশ্র মহড়া। প্রতিটি ভাগের শুরুতে কোন পর্ব ঝালিয়ে নেবেন, তার লিংক।
আগে খাতায় উত্তর, তারপর চাপুন: যে অপশনই চাপুন, ব্যাখ্যা খুলবে: কেন সঠিক বা ভুল, আর কোন পর্বে বিষয়টি আছে।
চার ধরনের প্রশ্ন: মনে রাখার, যুক্তির, প্রমাণ পড়ে ভুল ধরার আর ছোট হিসাবের। কঠিনতা লেখা থাকে প্রশ্নের শুরুতে: (সহজ), (মাঝারি) বা (কঠিন)।
প্রতিটি সংখ্যা যাচাই করা: প্রতিটি ভাগের শেষে একটি Python block সেই ভাগের সব হিসাব brute force বা সূত্রে মিলিয়ে দেখায়; প্রশ্ন শেষ করে তবেই চালান।
অন্য অনুশীলন পাতা: পূর্ণ সমাধানের হিসাব পর্ব ৭৯-এ, লিখিত ও ভাইভার প্রশ্ন পর্ব ৮১-এ, প্রমাণ লেখা পর্ব ৮২-এ, আর ইন্টারভিউর ধাঁধা পর্ব ৮৩-এ।

এই পর্বে যা করবেন

বাদ দেওয়ার পদ্ধতিতে উত্তর বের করা, আর প্রতিটি distractor-এর পেছনের ভুল ধারণা চেনা
Implication, quantifier আর প্রমাণের কাঠামো নিয়ে যুক্তির প্রশ্নে কারণসহ উত্তর দেওয়া
gcd, modular inverse, CRT, RSA আর Diffie–Hellman-এর ছোট হিসাব খাতায় দ্রুত করা
গণনা, সম্ভাবনা আর recurrence-এর প্রশ্নে ক্রম, পুনরাবৃত্তি আর শর্ত ঠিকমতো ধরা
Relation, graph, tree, group আর automaton-এর উপপাদ্যের শর্ত চিনে ঠিক অপশন বাছা
ঘড়ি ধরে মিশ্র মহড়া দিয়ে নিজের প্রস্তুতি মাপা আর দুর্বল মডিউলে ফেরা

১ · কীভাবে অনুশীলন করবেন — প্রশ্নের ধরন, বাদ দেওয়া আর সময়

এই পাতা বিশ্ববিদ্যালয়ের Discrete Mathematics বা Discrete Structures কোর্সের পরীক্ষা, IT ও প্রোগ্রামার পদের লিখিত পরীক্ষা, aptitude ও reasoning test, আর software ইন্টারভিউর আগের ঝালাইয়ের জন্য। নিজের পরীক্ষার ধরন আলাদা হতে পারে, তবে discrete math-এর MCQ-তে নম্বর বেশি হারায় একটি শর্ত এড়িয়ে যাওয়ায়: “যদি” না “যদি এবং কেবল যদি”, “অন্তত একটি” না “ঠিক একটি”, ক্রম গোনা হবে কি না, উপপাদ্যের শর্ত পূরণ হয়েছে কি না।

প্রশ্নের চার ছাঁচ

ধরন	উদাহরণ	কৌশল
মনে রাখা	Euler circuit-এর শর্ত, R(3, 3), Chomsky-র শ্রেণি	সংজ্ঞার চাবি-শব্দ আর শর্তসহ বলুন
যুক্তি	Quantifier-এর negation, contrapositive, Hall-এর শর্ত	ছোট উদাহরণে প্রতিটি অপশন যাচাই
প্রমাণ পড়া	ভুল induction, loop invariant, recursive সেট	প্রতিটি ধাপের কারণ খুঁজুন; কোথায় ফাঁক
ছোট হিসাব	3¹⁰⁰ mod 7, BANANA, D₅, Huffman	আগে সূত্র, তারপর সংখ্যা; শেষে ছোট ক্ষেত্রে মিলিয়ে দেখা

কোন মডিউলে কতটি প্রশ্ন

Questions per module, roughly in proportion to the number of lessons; 10 more in the mixed mock

কৌশল ১ · বাদ দেওয়ার পদ্ধতি — একটি quantifier-এর প্রশ্ন ধাপে ধাপে

সঠিক উত্তর সরাসরি খোঁজার চেয়ে ভুল অপশন কাটা প্রায়ই সহজ। নিচের প্রশ্নে প্রতিটি অপশন একটি নিয়ম দিয়ে যাচাই করুন। Quantifier-এর negation-এর পুরো আলোচনা পর্ব ০৪-এ।

প্রশ্ন¬∀x(P→Q)চারটি অপশন
Quantifierক, ঘ বাদ∀ হয় ∃
ভেতরের ¬খ বাদ¬(P→Q) ≡ P∧¬Q
উত্তরগ∃x(P∧¬Q)
যাচাই৬৪ ক্ষেত্রbrute force

প্রশ্ন (মাঝারি)চার অপশন

“সব অর্ডার P হলে Q” মিথ্যা।
¬∀x (P(x) → Q(x)) ≡ ?

ক) ∀x (¬P(x) → ¬Q(x))
খ) ∃x (P(x) → ¬Q(x))
গ) ∃x (P(x) ∧ ¬Q(x))
ঘ) ∀x (P(x) ∧ ¬Q(x))

ধাপ ২ক আর ঘ কাটুন

¬∀x φ ≡ ∃x ¬φ
“সবার জন্য নয়” মানে
“অন্তত একটির জন্য নয়”
→ ∀ দিয়ে শুরু ক, ঘ বাদ

ধাপ ৩খ কাটুন

¬(P → Q) ≡ P ∧ ¬Q
খ-এর P → ¬Q আলাদা:
যে x-এ P মিথ্যা, সেখানে
P → ¬Q এমনিই সত্য
→ খ বাদ

ধাপ ৪উত্তর গ

∃x (P(x) ∧ ¬Q(x))
অন্তত একটি অর্ডার আছে
যা P, অথচ Q নয়:
একটি counterexample

ধাপ ৫কোডে যাচাই

domain {0, 1, 2}
P, Q-এর 8 × 8 = 64 মান
গ: সব ক্ষেত্রে মেলে
খ: P সব মিথ্যা হলে
   মেলে না

আগে প্রশ্নটি নিজের ভাষায় বলুন। “সব P-ই Q” দাবিটি মিথ্যা; অর্থাৎ অন্তত একটি ব্যতিক্রম আছে। এই এক বাক্যই উত্তরের আকার বলে দেয়।
Quantifier উল্টায়। ¬∀x φ ≡ ∃x ¬φ. “সবার জন্য সত্য নয়” মানে “অন্তত একটির জন্য মিথ্যা”, তাই ∀ দিয়ে শুরু হওয়া ক আর ঘ বাদ।
ভেতরের negation ঠিক করুন। ¬(P → Q) ≡ P ∧ ¬Q, অথচ খ বলছে P → ¬Q. যে x-এ P মিথ্যা, সেখানে P → ¬Q এমনিই সত্য (vacuous truth), তাই খ মূল দাবির সমতুল্য নয়।
উত্তর গ। ∃x (P(x) ∧ ¬Q(x)): এমন একটি অর্ডার আছে যা P মানে অথচ Q মানে না। Universal দাবি খণ্ডনের জন্য ঠিক এই একটি counterexample-ই লাগে।
সন্দেহ থাকলে ছোট domain-এ যাচাই। তিন উপাদানের domain-এ P আর Q-এর ৬৪ রকম মানে চারটি অপশন মিলিয়ে দেখা যায়; নিচের Python block ঠিক এটিই করে।

প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে; এই পাতার সব block শুধু Python-এর standard library ব্যবহার করে।

from itertools import product
from fractions import Fraction as F

imp = lambda a, b: (not a) or b
# স্টেপারের প্রশ্ন: ¬∀x(P(x) → Q(x))-এর সঙ্গে কোন অপশন সব ক্ষেত্রে মেলে?
# domain = {0, 1, 2}; P আর Q-এর সব 2^3 × 2^3 = 64 রকম মান
opts = {
    "ক ∀x(¬P→¬Q)": lambda P, Q: all(imp(not p, not q) for p, q in zip(P, Q)),
    "খ ∃x(P→¬Q)":  lambda P, Q: any(imp(p, not q) for p, q in zip(P, Q)),
    "গ ∃x(P∧¬Q)":  lambda P, Q: any(p and not q for p, q in zip(P, Q)),
    "ঘ ∀x(P∧¬Q)":  lambda P, Q: all(p and not q for p, q in zip(P, Q)),
}
for name, f in opts.items():
    bad = [(P, Q) for P in product([0, 1], repeat=3) for Q in product([0, 1], repeat=3)
           if f(P, Q) != (not all(imp(p, q) for p, q in zip(P, Q)))]
    print(name, "মেলে" if not bad else f"মেলে না, প্রথম counterexample P={bad[0][0]} Q={bad[0][1]}")

# negative marking: ঠিক +1, ভুল −1/4, চারটি অপশন
for cut in range(3):
    k = 4 - cut                       # বাকি অপশন
    ev = F(1, k) - F(k - 1, k) * F(1, 4)
    print(f"{cut}টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর {ev} ≈ {float(ev):.3f}")

আসল আউটপুট:

ক ∀x(¬P→¬Q) মেলে না, প্রথম counterexample P=(0, 0, 0) Q=(0, 0, 0)
খ ∃x(P→¬Q) মেলে না, প্রথম counterexample P=(0, 0, 0) Q=(0, 0, 0)
গ ∃x(P∧¬Q) মেলে
ঘ ∀x(P∧¬Q) মেলে না, প্রথম counterexample P=(0, 0, 1) Q=(0, 0, 0)
0টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/16 ≈ 0.062
1টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/6 ≈ 0.167
2টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 3/8 ≈ 0.375

গ সব ৬৪ ক্ষেত্রে মূল দাবির negation-এর সঙ্গে মেলে; খ ভাঙে ঠিক সেখানে, যেখানে P সব জায়গায় মিথ্যা (তখন মূল ∀ দাবি সত্য, অথচ খ সত্য বলে)। দ্বিতীয় অংশ negative marking-এর হিসাব: ঠিক হলে +১ আর ভুলে −০.২৫ ধরলে অন্ধ আন্দাজের প্রত্যাশিত লাভ মাত্র ১/১৬, একটি অপশন নিশ্চিতভাবে কাটলে ১/৬, দুটি কাটলে ৩/৮. কত কাটে বা আদৌ কাটে কি না, তা পরীক্ষাভেদে আলাদা; নিজের পরীক্ষার নিয়ম দেখে নিন।

কৌশল ২ · ছোট ক্ষেত্রে মিলিয়ে দেখা

গণনা বা recurrence-এর সূত্র মনে না পড়লে n = 1, 2, 3 বসিয়ে অপশন কাটুন। যেমন “a_n = 2·3ⁿ − 2ⁿ” অপশনটি a₀ = 1 আর a₁ = 4 মেলায় কি না, দশ সেকেন্ডে দেখা যায়। একটি ছোট ক্ষেত্রে না মিললে অপশনটি নিশ্চিত ভুল; মিললে শুধু সম্ভাব্য।

কৌশল ৩ · সময় ভাগ

প্রথম দফায় সংজ্ঞা আর যুক্তির প্রশ্ন, দ্বিতীয় দফায় হিসাব, খাতায় প্রতিটি ধাপ লিখে। হিসাবের প্রশ্নে distractor প্রায়ই একটি ধাপ বাদ দিয়ে বানানো: ceiling-এর বদলে floor, mod φ(n)-এর বদলে mod n, বা দুবার গোনা অংশ বিয়োগ না করা।

বারোটি বড় ফাঁদ

ফাঁদ	ভুল ধারণা	সঠিক কথা
Converse	“p → q সত্য, তাই q → p-ও”	সমতুল্য শুধু contrapositive ¬q → ¬p (পর্ব ০২)
Vacuous truth	“p মিথ্যা, তাই p → q মিথ্যা”	p মিথ্যা হলে p → q সত্য (পর্ব ০২)
Quantifier-এর ক্রম	“∀x∃y আর ∃y∀x একই”	ক্রম বদলালে অর্থ বদলায় (পর্ব ০৫)
Induction	“Base ঠিক, তাই প্রমাণ ঠিক”	ধাপটি সব k-তে খাটতে হয়, ছোট k-সহ (পর্ব ১০)
অসীমের আকার	“ℚ ঘন, তাই ℝ-এর মতো uncountable”	ℚ countable; ℝ আর P(ℕ) নয় (পর্ব ১৮)
ঋণাত্মক ভাগশেষ	“−17 mod 5 = −2”	Division algorithm-এ 0 ≤ r < d, তাই 3 (পর্ব ২০)
Fermat-এর converse	“aⁿ⁻¹ ≡ 1, তাই n মৌলিক”	Carmichael সংখ্যা যেমন 561 ফাঁকি দেয় (পর্ব ২৫)
ক্রম আর পুনরাবৃত্তি	“সবখানে C(n, k)”	আগে প্রশ্ন: ক্রম গোনা হবে? পুনরাবৃত্তি চলবে? (পর্ব ৩৩, ৩৫)
উল্টো শর্ত	“P(সতর্কতা \| জালিয়াতি) = P(জালিয়াতি \| সতর্কতা)”	Bayes দিয়ে উল্টাতে হয়, base rate-সহ (পর্ব ৩৯)
Planar সীমা	“e ≤ 3v − 6 সব graph-এ”	শুধু simple, connected planar graph-এ, v ≥ 3 (পর্ব ৬২)
Dijkstra	“যেকোনো weight-এ চলে”	প্রমাণ ধরে নেয় weight ≥ 0 (পর্ব ৬১)
Undecidable	“কোনো program-এর থামা প্রমাণ করা যায় না”	অসম্ভব শুধু সব program-এর জন্য একটি algorithm (পর্ব ৭৫)

এই পাতার প্রশ্নগুলো সম্পর্কে: প্রশ্নগুলো এই কোর্সের জন্য নতুন করে লেখা, এ ধরনের প্রশ্ন প্রায়ই আসে এমন ধারণা থেকে। কোনোটিই কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠানের আসল প্রশ্ন নয়। “বাজারঘর” একটি কাল্পনিক অনলাইন দোকান, আর সব সংখ্যা ধরে নেওয়া। খেলনা RSA আর Diffie–Hellman-এর ছোট সংখ্যা শুধু বোঝার জন্য।

২ · মডিউল ১ ও ২ — যুক্তি আর প্রমাণ (১০টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ০১–১৩

পর্ব ০২, ০৩, ০৪, ০৫, ০৬, ০৭ — implication, tautology, nested quantifier, resolution
পর্ব ০৮, ০৯, ১০, ১১, ১২, ১৩ — contrapositive প্রমাণ, strong induction, structural induction, loop invariant

মডিউল ১ — যুক্তি (৫টি প্রশ্ন)

(সহজ) p: “অর্ডার ৫০০ টাকার বেশি”, q: “ডেলিভারি ফ্রি”. p → q কখন মিথ্যা?

p মিথ্যা, q সত্য
p মিথ্যা, q মিথ্যা
p সত্য, q মিথ্যা
p সত্য, q সত্য

(সহজ) “অর্ডার ৫০০ টাকার বেশি হলে ডেলিভারি ফ্রি”-এর সঙ্গে logically equivalent কোনটি?

ডেলিভারি ফ্রি হলে অর্ডার ৫০০ টাকার বেশি
ডেলিভারি ফ্রি না হলে অর্ডার ৫০০ টাকার বেশি নয়
অর্ডার ৫০০ টাকার বেশি না হলে ডেলিভারি ফ্রি নয়
অর্ডার ৫০০ টাকার বেশি, অথচ ডেলিভারি ফ্রি নয়

(মাঝারি) নিচের কোনটি tautology?

(p ∧ (p → q)) → q
(p → q) → (q → p)
((p → q) ∧ ¬q) → p
(p ∨ q) → (p ∧ q)

(মাঝারি) Domain পূর্ণসংখ্যা ℤ. নিচের কোনটি সত্য?

∃y ∀x (x + y = 0)
∀x ∀y (x + y = 0)
∀x ∃y (x < y < x + 1)
∀x ∃y (x + y = 0)

(মাঝারি) ¬∀x ∃y P(x, y)-এর সমতুল্য কোনটি?

∀x ∃y ¬P(x, y)
∃x ∀y ¬P(x, y)
∃x ∃y ¬P(x, y)
∀y ∃x ¬P(x, y)

মডিউল ২ — প্রমাণ (৫টি প্রশ্ন)

(সহজ) “n পূর্ণসংখ্যা; n² জোড় হলে n জোড়।” প্রমাণের সবচেয়ে সুবিধাজনক পদ্ধতি কোনটি?

Direct proof: n² = 2k থেকে শুরু
n-এর ওপর induction
Contrapositive: n বিজোড় ধরে n² বিজোড় দেখানো
একটি counterexample খোঁজা

(মাঝারি) ভুয়া প্রমাণ: “যেকোনো n টি ঘোড়া এক রঙের। Base: n = 1 সত্য। ধাপ: n + 1 টি ঘোড়ার প্রথম n টি এক রঙের, শেষ n টিও; দুই দল মাঝখানে মিলে যায়, তাই সব এক রঙের।” ভুল কোথায়?

n = 1 থেকে n = 2-এ দুই দলের মিল (overlap) ফাঁকা
Base case ভুল
Strong induction লাগত
Induction অসীম সেটে চলে না

(মাঝারি) শুধু ৪ আর ৫ টাকার স্ট্যাম্প (যত খুশি) দিয়ে কোন সবচেয়ে ছোট n থেকে শুরু করে প্রতিটি n টাকা ঠিক ঠিক বানানো যায়?

৮
১০
১১
১২

(মাঝারি) কোড: s = 0; i = 0; while i < n: s = s + a[i]; i = i + 1. প্রতিবার i < n পরীক্ষার মুহূর্তে কোনটি loop invariant?

s = a[0] + … + a[i]
s = a[0] + … + a[i − 1] (i = 0 হলে ফাঁকা যোগ 0)
i < n
s ≥ 0

(কঠিন) সেট S-এর recursive সংজ্ঞা: 3 ∈ S; x ∈ S আর y ∈ S হলে x + y ∈ S. S ঠিক কোন সেট?

সব ধনাত্মক বিজোড় সংখ্যা
৩ বা তার বড় সব পূর্ণসংখ্যা
৩-এর সব ধনাত্মক গুণিতক
শুধু {3, 6}

সব প্রশ্ন শেষ হলে নিচের block-এ ওপরের হিসাবগুলো মিলিয়ে নিন।

from itertools import product

imp = lambda a, b: (not a) or b
rows = list(product([False, True], repeat=2))
forms = {
    "(p ∧ (p → q)) → q": lambda p, q: imp(p and imp(p, q), q),
    "(p → q) → (q → p)": lambda p, q: imp(imp(p, q), imp(q, p)),
    "((p → q) ∧ ¬q) → p": lambda p, q: imp(imp(p, q) and not q, p),
    "(p ∨ q) → (p ∧ q)": lambda p, q: imp(p or q, p and q),
}
for s, f in forms.items():
    print(s, "tautology" if all(f(p, q) for p, q in rows) else "নয়")

# ℤ-এর একটি ছোট টুকরো [-20, 20]-এ quantifier-এর ক্রম
Z = range(-20, 21)
print("∀x∃y x+y=0:", all(any(x + y == 0 for y in Z) for x in Z))
print("∃y∀x x+y=0:", any(all(x + y == 0 for x in Z) for y in Z))

# ৪ আর ৫ টাকার স্ট্যাম্পে কোন মান বানানো যায় না?
ok = {4 * a + 5 * b for a in range(10) for b in range(10)}
print("অসম্ভব মান:", [n for n in range(1, 30) if n not in ok])

# 3 ∈ S; x, y ∈ S ⇒ x + y ∈ S — 40 পর্যন্ত S তৈরি
S = {3}
for _ in range(15):
    S |= {x + y for x in S for y in S if x + y <= 40}
print("S ∩ [1, 40]:", sorted(S))

আসল আউটপুট:

(p ∧ (p → q)) → q tautology
(p → q) → (q → p) নয়
((p → q) ∧ ¬q) → p নয়
(p ∨ q) → (p ∧ q) নয়
∀x∃y x+y=0: True
∃y∀x x+y=0: False
অসম্ভব মান: [1, 2, 3, 6, 7, 11]
S ∩ [1, 40]: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39]

চারটি সূত্রের মধ্যে শুধু modus ponens-এর রূপটি tautology. ℤ-এর একটি টুকরোয় ∀x∃y সত্য আর ∃y∀x মিথ্যা: ক্রমই পার্থক্য গড়ে। স্ট্যাম্পের তালিকার শেষ অসম্ভব মান ১১, তাই ১২ থেকে সব হয়; আর S-এর তালিকায় শুধু ৩-এর গুণিতক। তবে মনে রাখুন, সসীম পরিসরে মিলে যাওয়া প্রমাণ নয়; প্রমাণ আসে induction থেকে, কোড শুধু ভুল ধরতে সাহায্য করে।

৩ · মডিউল ৩ ও ৪ — সেট, ফাংশন আর সংখ্যাতত্ত্ব (১১টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ১৪–২৬

পর্ব ১৪, ১৫, ১৬, ১৭, ১৮, ১৯ — power set, one-to-one, De Morgan, uncountable, Boolean product
পর্ব ২০, ২১, ২২, ২৩, ২৪, ২৫, ২৬ — division algorithm, lcm, modular inverse, CRT, Fermat-এর ছোট উপপাদ্য, Carmichael সংখ্যা

মডিউল ৩ — সেট, ফাংশন আর ক্রম (৫টি প্রশ্ন)

(সহজ) |P(P(∅))| কত? (P মানে power set.)

(সহজ) তিন উপাদানের সেট A থেকে চার উপাদানের সেট B-তে কতগুলো one-to-one ফাংশন আছে?

২৪
৬৪
৮১
৪

(মাঝারি) A − (B ∪ C)-এর সমান কোনটি?

(A − B) ∪ (A − C)
(A − B) ∪ C
A − (B ∩ C)
(A − B) ∩ (A − C)

(মাঝারি) নিচের কোন সেটটি uncountable?

ℚ, সব মূলদ সংখ্যা
P(ℕ), ℕ-এর সব subset
ℤ × ℤ
{0, 1}-এর ওপর সব সসীম string

(কঠিন) Directed graph 1 → 2 → 3 → 1-এর 0-1 adjacency matrix A-এর সারি: (0 1 0), (0 0 1), (1 0 0). Boolean power A^[3] কী?

A নিজে
সব উপাদান ১
Identity matrix I
সারি (0 0 1), (1 0 0), (0 1 0)

মডিউল ৪ — সংখ্যাতত্ত্ব (৬টি প্রশ্ন)

(সহজ) Division algorithm-এ −17 = 5q + r, যেখানে 0 ≤ r < 5. q আর r কত?

q = −3, r = −2
q = −4, r = 3
q = −3, r = 2
q = 3, r = −2

(সহজ) gcd(252, 198) = 18. lcm(252, 198) কত?

১৮
৪৯,৮৯৬
১,৩৮৬
২,৭৭২

(মাঝারি) 7-এর গুণের inverse mod 26 কত?

১৫
৪
১৯
inverse নেই

(মাঝারি) 3¹⁰⁰ mod 7 কত?

(মাঝারি) x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7), আর 0 ≤ x < 105. x কত?

৮
২৩
৩৮
১২৮

(কঠিন) 561 = 3 · 11 · 17, আর gcd(a, 561) = 1 এমন প্রতিটি a-তে a⁵⁶⁰ ≡ 1 (mod 561). কোন সিদ্ধান্ত সঠিক?

561 মৌলিক, কারণ Fermat-এর পরীক্ষায় সব base পাস
Fermat-এর ছোট উপপাদ্য ভুল প্রমাণিত
Miller–Rabin-ও 561-কে সবসময় মৌলিক বলবে
561 একটি Carmichael সংখ্যা; Fermat-এর পরীক্ষা ফাঁকি খায়, Miller–Rabin নয়

from itertools import product, chain, combinations
from math import gcd

def power_set(s):
    s = list(s)
    return [frozenset(c) for c in chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))]
print("|P(P(∅))| =", len(power_set(power_set(set()))))
f_all = list(product(range(4), repeat=3))          # {a,b,c} → {0,1,2,3}
print("সব function:", len(f_all), "| one-to-one:", sum(len(set(f)) == 3 for f in f_all))

A = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]
bp = lambda X, Y: [[int(any(X[i][k] and Y[k][j] for k in range(3))) for j in range(3)] for i in range(3)]
print("A^[3] =", bp(bp(A, A), A))

print("-17 = 5q + r:", divmod(-17, 5))            # Python-এ 0 ≤ r < 5
g = gcd(252, 198); print("gcd, lcm:", g, 252 * 198 // g)
print("7⁻¹ mod 26 =", pow(7, -1, 26))
print("3^100 mod 7 =", pow(3, 100, 7))
print("CRT:", [x for x in range(105) if (x % 3, x % 5, x % 7) == (2, 3, 2)])
ok = all(pow(a, 560, 561) == 1 for a in range(1, 561) if gcd(a, 561) == 1)
print("561-এ সব coprime a-তে a^560 ≡ 1:", ok, "| 3·11·17 =", 3 * 11 * 17)
# Miller–Rabin, base 2: 560 = 2^4 · 35
x = pow(2, 35, 561); seq = [x]
for _ in range(4):
    x = x * x % 561; seq.append(x)
print("base 2-এর ক্রম:", seq)

আসল আউটপুট:

|P(P(∅))| = 2
সব function: 64 | one-to-one: 24
A^[3] = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
-17 = 5q + r: (-4, 3)
gcd, lcm: 18 2772
7⁻¹ mod 26 = 15
3^100 mod 7 = 4
CRT: [23]
561-এ সব coprime a-তে a^560 ≡ 1: True | 3·11·17 = 561
base 2-এর ক্রম: [263, 166, 67, 1, 1]

Python-এর divmod floored division ব্যবহার করে, তাই r সবসময় 0 ≤ r < 5, ঠিক division algorithm-এর মতো; pow(7, -1, 26) সরাসরি inverse দেয়। শেষ লাইনটি 561-এর Miller–Rabin: 560 = 2⁴ · 35, আর ক্রম 263, 166, 67, 1. 67-এর বর্গ 1 অথচ 67 নিজে ±1 নয়, তাই 561 যৌগিক প্রমাণিত, যদিও Fermat-এর পরীক্ষা সব coprime base-এ পাস করে।

৪ · মডিউল ৫ ও ৬ — Cryptography-র গণিত আর গণনা (৯টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ২৭–৩৭

পর্ব ২৭, ২৮, ২৯, ৩০ — affine cipher, φ(n), textbook RSA, Diffie–Hellman, padding. বাস্তব ব্যবহারের নিয়ম সাইবার সিকিউরিটি কোর্সের পর্ব ১০-এ।
পর্ব ৩১, ৩২, ৩৩, ৩৪, ৩৫, ৩৬, ৩৭ — inclusion–exclusion, generalized pigeonhole, multinomial, stars and bars, binomial theorem

মডিউল ৫ — সংখ্যাতত্ত্ব থেকে cryptography (৪টি প্রশ্ন)

(সহজ) Affine cipher E(x) = (ax + b) mod 26, যেখানে a, b ∈ {0, 1, …, 25}. কতগুলো (a, b) জোড়া বৈধ key, অর্থাৎ decrypt করা যায়?

৬৭৬
২৬
৩১২
৩০০

(মাঝারি) খেলনা RSA: p = 5, q = 11, e = 3. গোপন exponent d কত?

২৭
৩৭
৩
৪০

(মাঝারি) খেলনা Diffie–Hellman: p = 23, g = 5. একজনের গোপন a = 6, অন্যজনের b = 15. দুজনের ভাগ করা গোপন key কত?

৮
২
১৯
১৪

(মাঝারি) বাজারঘর বড় n দিয়ে padding ছাড়া textbook RSA-য় শুধু “হ্যাঁ” বা “না” encrypt করে পাঠায়। প্রধান দুর্বলতা কী?

বড় n factor করা সহজ
e গোপন রাখা যায় না
Decryption ভুল ফল দেয়
একই বার্তা সবসময় একই ciphertext দেয়, তাই অনুমান করে মেলানো যায়

মডিউল ৬ — গণনা (৫টি প্রশ্ন)

(সহজ) দৈর্ঘ্য ৮-এর কতগুলো bit string হয় 1 দিয়ে শুরু, নয়তো 00 দিয়ে শেষ (বা দুটিই)?

১৯২
১৬০
৩২
২৫৬

(সহজ) বাজারঘরের ১০০টি অর্ডার বছরের ১২ মাসে ছড়ানো। নিশ্চিতভাবে কোনো এক মাসে অন্তত কতটি অর্ডার?

৮
১২
৯
১৩

(মাঝারি) “BANANA” শব্দের অক্ষরগুলো কতভাবে সাজানো যায়?

৬০
৭২০
১২০
৩৬০

(মাঝারি) x₁ + x₂ + x₃ = 10-এর কতগুলো পূর্ণসংখ্যা সমাধান আছে, যেখানে প্রতিটি x_i ≥ 1?

৬৬
১২০
৪৫
৩৬

(কঠিন) (2x − y)⁵-এর বিস্তারে x³y²-এর সহগ কত?

১০
৮০
−৮০
৪০

from itertools import product, permutations
from math import gcd, comb

valid_a = [a for a in range(26) if gcd(a, 26) == 1]
print("affine: বৈধ a", len(valid_a), "টি, মোট key", len(valid_a) * 26)

p, q, e = 5, 11, 3                     # খেলনা RSA, শুধু বোঝার জন্য
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi); c = pow(9, e, n)
print("n, φ, d:", n, phi, d, "| 9 → c =", c, "→ ফেরত", pow(c, d, n))
print("ভুল পথ e⁻¹ mod n =", pow(e, -1, n))
P, g, a, b = 23, 5, 6, 15              # খেলনা Diffie–Hellman
A, B = pow(g, a, P), pow(g, b, P)
print("A, B:", A, B, "| গোপন:", pow(B, a, P), pow(A, b, P), "| A·B mod p:", A * B % P)

bits = ["".join(s) for s in product("01", repeat=8)]
print("1 দিয়ে শুরু বা 00-তে শেষ:", sum(s[0] == "1" or s.endswith("00") for s in bits))
print("BANANA:", len(set(permutations("BANANA"))))
sol = [(x, y, 10 - x - y) for x in range(1, 9) for y in range(1, 9) if 10 - x - y >= 1]
print("x1+x2+x3=10, xi ≥ 1:", len(sol), "| সূত্র C(9,2) =", comb(9, 2))

poly = {(0, 0): 1}                     # (2x − y)^5 গুণ করে বিস্তার
for _ in range(5):
    new = {}
    for (i, j), cf in poly.items():
        new[(i + 1, j)] = new.get((i + 1, j), 0) + 2 * cf
        new[(i, j + 1)] = new.get((i, j + 1), 0) - cf
    poly = new
print("x^3 y^2-এর সহগ:", poly[(3, 2)])

আসল আউটপুট:

affine: বৈধ a 12 টি, মোট key 312
n, φ, d: 55 40 27 | 9 → c = 14 → ফেরত 9
ভুল পথ e⁻¹ mod n = 37
A, B: 8 19 | গোপন: 2 2 | A·B mod p: 14
1 দিয়ে শুরু বা 00-তে শেষ: 160
BANANA: 60
x1+x2+x3=10, xi ≥ 1: 36 | সূত্র C(9,2) = 36
x^3 y^2-এর সহগ: 80

RSA-র লাইনে 9 encrypt হয়ে 14, আর d = 27 দিয়ে আবার 9: key ঠিক। “ভুল পথ” লাইনটি দেখায়, mod n-এ inverse নিলে 37 আসে, যা distractor-টির উৎস। Diffie–Hellman-এ দুই দিক থেকে একই 2 মেলে, অথচ A · B mod p = 14 আলাদা। শেষ লাইনে বিস্তারটি গুণ করে বের করা, সূত্র ছাড়াই: সহগ 80. মনে রাখুন, এই ছোট সংখ্যার RSA আর DH শুধু গণিত বোঝার জন্য; বাস্তবে বড় key, padding আর পরীক্ষিত লাইব্রেরি লাগে।

৫ · মডিউল ৭ ও ৮ — সম্ভাবনা আর উন্নত গণনা (১১টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৩৮–৫১

পর্ব ৩৮, ৩৯, ৪০, ৪১, ৪২, ৪৩ — Bayes, prosecutor’s fallacy, linearity of expectation, Chebyshev, birthday paradox
পর্ব ৪৪, ৪৫, ৪৬, ৪৭, ৪৮, ৪৯, ৫০, ৫১ — characteristic equation, master theorem, generating function, derangement, Burnside

মডিউল ৭ — বিচ্ছিন্ন সম্ভাবনা (৫টি প্রশ্ন)

(সহজ) দুটি ন্যায্য ছক্কা একসঙ্গে ছোড়া হলো। যোগফল 7 হওয়ার সম্ভাবনা কত?

১/১১
১/৩৬
১/৬
১/১২

(মাঝারি) বাজারঘরের ২% অর্ডার জালিয়াতি। একটি detector জালিয়াতির ৯৫%-এ আর সৎ অর্ডারের ৫%-এ সতর্কতা দেয়। সতর্কতা পাওয়া একটি অর্ডার আসলে জালিয়াতি হওয়ার সম্ভাবনা মোটামুটি কত?

প্রায় ০.২৮
০.৯৫
০.০২
০.০৬৮

(মাঝারি) ১০টি চিঠি এলোমেলোভাবে ১০টি খামে ভরা হলো, প্রতিটি permutation সমান সম্ভাব্য। ঠিক খামে পড়া চিঠির প্রত্যাশিত সংখ্যা কত?

০.১
১
প্রায় ০.৩৬৮
৫

(মাঝারি) একটি random variable X-এর গড় 50 আর standard deviation 5; বণ্টন অজানা। Chebyshev অনুযায়ী P(|X − 50| ≥ 15)-এর সর্বোচ্চ সীমা কত?

১/৩
প্রায় ০.০০৩
১/২২৫
১/৯

(মাঝারি) বছরের ৩৬৫ দিন সমান সম্ভাব্য ধরে কমপক্ষে কতজন হলে কোনো দুজনের একই জন্মদিনের সম্ভাবনা ০.৫ ছাড়ায়?

২৩
১৮৩
৩৬৬
৫৭

মডিউল ৮ — উন্নত গণনা (৬টি প্রশ্ন)

(সহজ) দৈর্ঘ্য n-এর যে bit string-এ পরপর দুটি 0 নেই, তার সংখ্যা a_n; a₁ = 2, a₂ = 3. a₅ কত?

৮
৩২
১৩
১৬

(মাঝারি) a_n = 5a_n−1 − 6a_n−2, a₀ = 1, a₁ = 4. Closed form কোনটি?

a_n = 2ⁿ + 3ⁿ
a_n = 2 · 3ⁿ − 2ⁿ
a_n = 3ⁿ + n · 2ⁿ
a_n = 5ⁿ − 6ⁿ

(মাঝারি) T(n) = 4T(n/2) + n-এর সমাধান master theorem অনুযায়ী কী?

Θ(n)
Θ(n log n)
Θ(n² log n)
Θ(n²)

(মাঝারি) ৫ জন ক্রেতার প্যাকেট এমনভাবে বিলি করতে হবে যেন কেউ নিজের প্যাকেট না পায়। কত উপায়ে?

৪৪
১২০
৭৬
৯

(মাঝারি) 1/(1 − x)³-এর ঘাত-ধারায় x⁵-এর সহগ কত?

১
১০
২১
৩৫

(কঠিন) ৪টি পুঁতির মালা, প্রতিটি পুঁতি লাল বা নীল; শুধু ঘোরালে একই হলে মালা একই ধরা হয় (উল্টানো চলবে না)। আলাদা মালা কতগুলো?

১৬
৬
৪
৫

from itertools import product, permutations
from fractions import Fraction as F
from math import comb

print("দুই ছক্কায় যোগফল 7:", F(sum(a + b == 7 for a in range(1, 7) for b in range(1, 7)), 36))
tp, fp = F(2, 100) * F(95, 100), F(98, 100) * F(5, 100)
print("P(জালিয়াতি | সতর্কতা) =", tp / (tp + fp), "≈", round(float(tp / (tp + fp)), 3))
perms = list(permutations(range(6)))
fixed = F(sum(sum(p[i] == i for i in range(6)) for p in perms), len(perms))
print("n = 6-এ ঠিক খামের প্রত্যাশা:", fixed)
q = 1.0
for k in range(1, 24):
    q *= (365 - k + 1) / 365
    if k in (22, 23): print(k, "জনে মিলের সম্ভাবনা", round(1 - q, 4))

a = {1: 2, 2: 3}
for n in range(3, 6): a[n] = a[n - 1] + a[n - 2]
brute = sum("00" not in "".join(s) for s in product("01", repeat=5))
print("a_5 =", a[5], "| brute force:", brute)
r = [1, 4]
for n in range(2, 6): r.append(5 * r[-1] - 6 * r[-2])
print("recurrence:", r, "| 2·3^n − 2^n:", [2 * 3**n - 2**n for n in range(6)])
D5 = sum(all(p[i] != i for i in range(5)) for p in permutations(range(5)))
print("D_5 =", D5, "| x^5-এর সহগ 1/(1−x)^3-এ:", comb(7, 2))
fix = []
for s in range(4):                    # ঘূর্ণন 0°, 90°, 180°, 270°
    fix.append(sum(c == c[s:] + c[:s] for c in product("RB", repeat=4)))
print("Burnside: fix =", fix, "→ necklace", sum(fix) // 4)

আসল আউটপুট:

দুই ছক্কায় যোগফল 7: 1/6
P(জালিয়াতি | সতর্কতা) = 19/68 ≈ 0.279
n = 6-এ ঠিক খামের প্রত্যাশা: 1
22 জনে মিলের সম্ভাবনা 0.4757
23 জনে মিলের সম্ভাবনা 0.5073
a_5 = 13 | brute force: 13
recurrence: [1, 4, 14, 46, 146, 454] | 2·3^n − 2^n: [1, 4, 14, 46, 146, 454]
D_5 = 44 | x^5-এর সহগ 1/(1−x)^3-এ: 21
Burnside: fix = [16, 2, 4, 2] → necklace 6

Bayes-এর উত্তর ভগ্নাংশে ঠিক 19/68: সতর্কতার প্রায় তিন ভাগের দুই ভাগই সৎ অর্ডার, কারণ সৎ অর্ডার সংখ্যায় অনেক বেশি। খামের প্রত্যাশা n = 6-এ সব 720টি permutation গুনে ঠিক 1, যে কোনো n-এ একই। Recurrence-এর তালিকা আর closed form প্রথম ছয়টি পদে মেলে, আর Burnside-এর fix তালিকা 16, 2, 4, 2. Brute force ছোট n-এ সূত্রকে যাচাই করে, প্রমাণ করে না।

৬ · মডিউল ৯ ও ১০ — Relation আর graph (১০টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৫২–৬৪

পর্ব ৫২, ৫৩, ৫৪, ৫৫, ৫৬ — equivalence relation, Bell সংখ্যা, transitive closure, Warshall, lub
পর্ব ৫৭, ৫৮, ৫৯, ৬০, ৬১, ৬২, ৬৩, ৬৪ — handshake, Euler path, Euler-এর সূত্র, chromatic number, Hall-এর উপপাদ্য. Algorithm-এর কোড DSA কোর্সে।

মডিউল ৯ — Relation (৪টি প্রশ্ন)

(সহজ) {1, 2, 3}-এর ওপর R = {(1,1), (2,2), (3,3), (1,2), (2,1)}. R সম্পর্কে কোনটি সঠিক?

Reflexive আর symmetric, কিন্তু transitive নয়
এটি একটি partial order
শুধু symmetric
Equivalence relation; class {1, 2} আর {3}

(মাঝারি) ৪টি পণ্যের একটি সেটে কতগুলো আলাদা equivalence relation সম্ভব?

১৫
৭
৬৫,৫৩৬
২৪

(মাঝারি) R = {(1,2), (2,3), (3,4)}-এর transitive closure-এ কোন নতুন জোড়াগুলো যোগ হয়?

শুধু (1, 3)
(1, 3) আর (2, 4)
(1, 3), (2, 4) আর (1, 4)
ওপরের তিনটি, সঙ্গে (1,1) থেকে (4,4)

(মাঝারি) {1, 2, 3, 4, 6, 12}-এ বিভাজ্যতার partial order. 4 আর 6-এর lub আর glb কত?

lub ২৪, glb ২
lub ১২, glb ২
lub ১২, glb ১
নেই, কারণ 4 আর 6 তুলনীয় নয়

মডিউল ১০ — গ্রাফ (৬টি প্রশ্ন)

(সহজ) ৭টি vertex-এর এমন কোনো simple graph কি আছে, যার প্রতিটি vertex-এর degree 3?

হ্যাঁ, যেকোনো n-এ 3-regular graph হয়
হ্যাঁ, তবে connected নয়
না: degree-যোগ 21 বিজোড়
না, কারণ 7 মৌলিক

(মাঝারি) K₅ planar নয়, এর সবচেয়ে সরাসরি যুক্তি কোনটি?

Planar হলে e ≤ 3v − 6 হতো, অথচ 10 > 9
K₅-এ ত্রিভুজ আছে
e ≤ 2v − 4 ভাঙে
K₅-এ Euler circuit আছে

(মাঝারি) একটি connected graph-এ vertex A, B, C, D, E-এর degree যথাক্রমে 3, 4, 2, 3, 2. কোনটি সঠিক?

Euler circuit আছে
Euler path আছে, A থেকে D (বা উল্টো)
Euler path বা circuit কোনোটিই নেই
Euler path আছে, B থেকে শুরু

(মাঝারি) একটি connected planar graph-এর সমতলে আঁকায় v = 8 আর e = 12. Face কতগুলো (বাইরের অসীম face-সহ)?

৪
৮
২২
৬

(মাঝারি) ৭ জন রাইডারের শিফট-দ্বন্দ্বের graph একটি cycle C₇ (পাশাপাশি দুজন একই শিফটে নয়)। কমপক্ষে কয়টি শিফট লাগে?

(কঠিন) রাইডার a শুধু অর্ডার ১, b শুধু অর্ডার ১, আর c অর্ডার ১, ২ বা ৩ নিতে পারে; প্রত্যেকে আলাদা একটি অর্ডার। সর্বোচ্চ কতজনকে মেলানো যায়, আর কেন?

২জন; {a, b}-এর প্রতিবেশী মাত্র একটি অর্ডার
৩জন, কারণ অর্ডার ৩টি আর রাইডার ৩জন
১জন
৩জন, যদি c-কে আগে অর্ডার ১ দেওয়া হয়

from itertools import product, combinations

def partitions(s):                     # একটি সেটের সব partition
    if not s: yield []; return
    for p in partitions(s[1:]):
        for i in range(len(p)): yield p[:i] + [[s[0]] + p[i]] + p[i + 1:]
        yield [[s[0]]] + p
print("৪ উপাদানে equivalence relation (Bell):", sum(1 for _ in partitions([1, 2, 3, 4])))

R = {(1, 2), (2, 3), (3, 4)}
M = [[int((i, j) in R) for j in range(1, 5)] for i in range(1, 5)]
for k in range(4):                     # Warshall
    M = [[M[i][j] or (M[i][k] and M[k][j]) for j in range(4)] for i in range(4)]
T = {(i + 1, j + 1) for i in range(4) for j in range(4) if M[i][j]}
print("closure-এ নতুন:", sorted(T - R))
D = [1, 2, 3, 4, 6, 12]
ub = [u for u in D if u % 4 == 0 and u % 6 == 0]
lb = [x for x in D if 4 % x == 0 and 6 % x == 0]
print("4, 6-এর lub:", min(ub), "| glb:", max(lb))

print("degree-যোগ 7 × 3 =", 7 * 3, "| K5: e = 10, 3v − 6 =", 3 * 5 - 6, "| f =", 2 - 8 + 12)
deg = {"A": 3, "B": 4, "C": 2, "D": 3, "E": 2}
print("বিজোড় degree:", [v for v, k in deg.items() if k % 2])
C7 = [(i, (i + 1) % 7) for i in range(7)]
chi = next(k for k in range(1, 8)
           if any(all(c[u] != c[v] for u, v in C7) for c in product(range(k), repeat=7)))
can = {"a": {1}, "b": {1}, "c": {1, 2, 3}}
best = max(len(S) for r in range(4) for S in combinations("abc", r)
           if any(len(set(o)) == r for o in product(*[can[x] for x in S])))
print("χ(C7) =", chi, "| সর্বোচ্চ matching:", best)

আসল আউটপুট:

৪ উপাদানে equivalence relation (Bell): 15
closure-এ নতুন: [(1, 3), (1, 4), (2, 4)]
4, 6-এর lub: 12 | glb: 2
degree-যোগ 7 × 3 = 21 | K5: e = 10, 3v − 6 = 9 | f = 6
বিজোড় degree: ['A', 'D']
χ(C7) = 3 | সর্বোচ্চ matching: 2

৪ উপাদানের সব partition তালিকা করে ১৫টি পাওয়া গেছে, যা Bell সংখ্যা। Warshall-এর তিন ধাপের পর নতুন জোড়া ঠিক তিনটি। χ(C₇)-এর জন্য কোড ১, ২, ৩ রঙে সব বিন্যাস চেষ্টা করে প্রথম সফল k ছাপে; আর matching-এর brute force সব subset দেখে ২-এর বেশি পায় না, যা Hall-এর শর্ত ভাঙার সঙ্গে মেলে।

৭ · মডিউল ১১ ও ১২ — Tree আর বীজগাণিতিক কাঠামো (৮টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৬৫–৭২

পর্ব ৬৫, ৬৬, ৬৭, ৬৮ — full m-ary tree, postfix, Cayley-র সূত্র, Huffman coding
পর্ব ৬৯, ৭০, ৭১, ৭২ — element-এর order, Lagrange, field, zero divisor, minimum distance

মডিউল ১১ — Tree (৪টি প্রশ্ন)

(সহজ) একটি full 3-ary tree-এ internal vertex ১০টি। Leaf কতগুলো?

৩০
২১
৩১
১১

(মাঝারি) (a + b) * (c − d)-এর expression tree-র postorder traversal, অর্থাৎ postfix রূপ কোনটি?

* + a b − c d
a + b * c − d
a b + c d − *
a b c d + − *

(মাঝারি) K₄-এর (৪টি লেবেলযুক্ত vertex-এর complete graph) কতগুলো আলাদা spanning tree আছে?

৪
৬
১২
১৬

(কঠিন) প্রতি ১০০টি প্রতীকে A ৪০ বার, B ২৫, C ২০, D ১০ আর E ৫ বার আসে। Huffman code-এ প্রতীকপ্রতি গড় দৈর্ঘ্য কত bit?

২.১০
৩
প্রায় ২.৩২
প্রায় ২.০৪

মডিউল ১২ — বীজগাণিতিক কাঠামো আর Boolean algebra (৪টি প্রশ্ন)

(সহজ) Boolean algebra-য় xy + xy′ + x′y-এর সরলতম রূপ কোনটি?

x
x + y
xy
1

(মাঝারি) যোগের group (ℤ₁₂, + mod 12)-এ উপাদান 8-এর order কত?

৮
১২
৪
৩

(মাঝারি) নিচের কোনটি field?

ℤ₇ (mod 7 যোগ আর গুণ)
ℤ₈
ℤ, সব পূর্ণসংখ্যা
ℤ₆

(মাঝারি) একটি code-এর minimum distance d = 5. এটি নিশ্চিতভাবে কতগুলো bit-error ধরতে আর কতগুলো শোধরাতে পারে?

৫টি ধরা, ২টি শোধরানো
৪টি ধরা, ৪টি শোধরানো
৪টি ধরা, ২টি শোধরানো
২টি ধরা, ১টি শোধরানো

from itertools import combinations, product
from math import log2
import heapq

print("full 3-ary, i = 10: n =", 3 * 10 + 1, "| leaf =", (3 - 1) * 10 + 1)
def postfix(t):                        # t = (op, বাম, ডান) বা একটি অক্ষর
    return t if isinstance(t, str) else postfix(t[1]) + " " + postfix(t[2]) + " " + t[0]
print("postfix:", postfix(("*", ("+", "a", "b"), ("-", "c", "d"))))
E = list(combinations(range(4), 2))   # K4-এর ৬টি edge
# ৪ vertex-এ ৩টি edge: চারটি vertex ছুঁলে ত্রিভুজ নেই, তাই tree
print("K4-এর spanning tree:", sum(len({v for e in es for v in e}) == 4 for es in combinations(E, 3)))

fr = {"A": 40, "B": 25, "C": 20, "D": 10, "E": 5}
h = [(w, k, {k: 0}) for k, w in fr.items()]; heapq.heapify(h)
while len(h) > 1:
    w1, k1, d1 = heapq.heappop(h); w2, k2, d2 = heapq.heappop(h)
    heapq.heappush(h, (w1 + w2, k1 + k2, {s: L + 1 for s, L in (d1 | d2).items()}))
L = h[0][2]
print("Huffman দৈর্ঘ্য:", dict(sorted(L.items())), "| গড়:", sum(fr[s] * L[s] for s in fr) / 100)
print("entropy ≈", round(-sum(w / 100 * log2(w / 100) for w in fr.values()), 3))

ok = all(((x and y) or (x and not y) or (not x and y)) == (x or y) for x, y in product([0, 1], repeat=2))
print("xy + xy' + x'y = x + y:", ok)
print("ℤ12-এ 8-এর order:", next(k for k in range(1, 13) if 8 * k % 12 == 0))
for m in (6, 7, 8):
    print(f"ℤ{m} field?", all(any(a * b % m == 1 for b in range(m)) for a in range(1, m)))
d = 5; print("d = 5: ধরা", d - 1, "| শোধরানো", (d - 1) // 2)

আসল আউটপুট:

full 3-ary, i = 10: n = 31 | leaf = 21
postfix: a b + c d - *
K4-এর spanning tree: 16
Huffman দৈর্ঘ্য: {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 4} | গড়: 2.1
entropy ≈ 2.041
xy + xy' + x'y = x + y: True
ℤ12-এ 8-এর order: 3
ℤ6 field? False
ℤ7 field? True
ℤ8 field? False
d = 5: ধরা 4 | শোধরানো 2

K₄-এর ৬টি edge থেকে ৩টি নেওয়ার ২০টি উপায়ের মধ্যে ৪টি ত্রিভুজ বাদ গেলে ১৬টি tree থাকে, Cayley-র সূত্রের সঙ্গে মেলে। Huffman-এর গড় 2.1 bit আর entropy প্রায় 2.041: Huffman নিম্নসীমার খুব কাছে, তবে সমান নয়। কোডে postfix-এ বিয়োগ চিহ্ন ASCII-র -, পাতার লেখায় “−”.

৮ · মডিউল ১৩ — গণনার মডেল আর উন্নত বিষয় (৫টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৭৩–৭৭

পর্ব ৭৩, ৭৪, ৭৫, ৭৬, ৭৭ — context-free language, DFA minimization, halting problem, Ramsey সংখ্যা, 2-SAT. Automaton আর computability-র গভীর আলোচনা একটি ভবিষ্যৎ Theory of Computation কোর্সে।

(সহজ) Language L = {aⁿbⁿ : n ≥ 0} সম্পর্কে কোনটি সঠিক?

Regular
Context-free, কিন্তু regular নয়
Context-free নয়
সসীম language

(মাঝারি) {0, 1}-এর ওপর যে string-গুলো “01”-এ শেষ হয়, সেগুলো চেনার minimal DFA-তে কতগুলো state?

(মাঝারি) “Halting problem undecidable”-এর সঠিক অর্থ কোনটি?

এমন কোনো algorithm নেই যা প্রতিটি (program, input) জোড়ার জন্য সঠিকভাবে বলবে থামবে কি না
কোনো নির্দিষ্ট program থামবে কি না কখনো প্রমাণ করা যায় না
যথেষ্ট দ্রুত কম্পিউটার হলে সমাধান হবে
Halting problem NP-complete

(মাঝারি) একটি দলে যেকোনো দুজন হয় পরিচিত, নয় অপরিচিত। কমপক্ষে কতজন হলে নিশ্চিতভাবে তিনজন পরস্পর পরিচিত বা তিনজন পরস্পর অপরিচিত থাকবে?

(মাঝারি) প্রতিটি clause-এ বড়জোর দুটি literal (2-CNF). এর satisfiability সম্পর্কে কোনটি সঠিক?

3-SAT-এর মতো NP-complete
Implication graph-এর SCC দেখে polynomial সময়ে নির্ণয় করা যায়
2-CNF সবসময় satisfiable
যেকোনো 3-CNF-কে 2-CNF-এ ভাঙা যায়, তাই P = NP

from itertools import product, combinations

# “01”-এ শেষ হওয়া binary string-এর তিন-state DFA
# state 0: কিছু মেলেনি, 1: শেষে 0, 2: শেষে 01 (accept)
delta = {(0, "0"): 1, (0, "1"): 0, (1, "0"): 1, (1, "1"): 2, (2, "0"): 1, (2, "1"): 0}
def run(w):
    s = 0
    for ch in w: s = delta[(s, ch)]
    return s == 2
words = ["".join(t) for L in range(9) for t in product("01", repeat=L)]
print("DFA আর endswith('01') সব", len(words), "টি string-এ মেলে:",
      all(run(w) == w.endswith("01") for w in words))

def ramsey_free(n):                    # K_n-এর কতগুলো ২-রঙা colouring-এ একরঙা ত্রিভুজ নেই
    E = list(combinations(range(n), 2)); idx = {e: i for i, e in enumerate(E)}
    tri = [sum(1 << idx[e] for e in combinations(t, 2)) for t in combinations(range(n), 3)]
    full = (1 << len(E)) - 1
    return sum(all(m & t not in (0, t) for t in tri) for m in range(full + 1))
print("K5-এ একরঙা ত্রিভুজহীন colouring:", ramsey_free(5))
print("K6-এ একরঙা ত্রিভুজহীন colouring:", ramsey_free(6))

# (x ∨ x) ∧ (¬x ∨ ¬x): দুই literal-এর clause, তবু UNSAT
print("(x∨x)∧(¬x∨¬x) satisfiable?", any((x or x) and (not x or not x) for x in (False, True)))

আসল আউটপুট:

DFA আর endswith('01') সব 511 টি string-এ মেলে: True
K5-এ একরঙা ত্রিভুজহীন colouring: 12
K6-এ একরঙা ত্রিভুজহীন colouring: 0
(x∨x)∧(¬x∨¬x) satisfiable? False

তিন-state DFA দৈর্ঘ্য ০ থেকে ৮-এর সব ৫১১টি string-এ endswith("01")-এর সঙ্গে মেলে। Ramsey-র অংশ K₅-এর সব 2¹⁰ আর K₆-এর সব 2¹⁵ = 32,768 রং-বিন্যাস পরীক্ষা করে: K₅-এ ১২টি বিন্যাসে একরঙা ত্রিভুজ নেই (পঞ্চভুজ আর তার রূপভেদ), K₆-এ একটিও নয়, অর্থাৎ R(3, 3) = 6. শেষ লাইন দেখায়, দুই-literal clause হলেই satisfiable নয়।

৯ · মিশ্র মহড়া — ঘড়ি ধরে ১০টি প্রশ্ন, সব মডিউল থেকে

সব ভাগ শেষ হলে এই অংশটি একটি ছোট মহড়া পরীক্ষা হিসেবে করুন। প্রশ্নগুলো ইচ্ছা করে এলোমেলো, কারণ আসল পরীক্ষায় resolution-এর পরেই Dijkstra, তারপর Catalan আসতে পারে। ওপরের প্রশ্ন থেকে এগুলো আলাদা।

মহড়ার নিয়ম · ১০টি প্রশ্ন, ১২ মিনিট

ঘড়ি ধরুন: ১২ মিনিটের টাইমার চালু করুন; প্রতি প্রশ্নে গড়ে এক মিনিটের একটু বেশি।
আগে খাতায়: ১ থেকে ১০ নম্বরের পাশে অপশন আর এক লাইনের কারণ লিখুন; সময় শেষ হলে তবেই অপশন চাপুন।
ফল পড়ুন এভাবে: ৮ বা বেশি ঠিক হলে প্রস্তুতি ভালো; ৫ থেকে ৭ হলে ভুল প্রশ্নের পর্বগুলো ঝালিয়ে নিন; ৪ বা কম হলে আগে মডিউলের ভাগগুলো আবার করুন। এই সীমা শুধু অনুশীলনের সুবিধার জন্য ধরা, কোনো পরীক্ষার মান নয়।

(সহজ) Premise (p ∨ q) আর (¬p ∨ r) থেকে resolution দিয়ে কী পাওয়া যায়?

p ∨ r
q ∧ r
q ∨ r
¬p

(সহজ) 1 + 2 + 4 + … + 2⁹ (অর্থাৎ ∑_k=0⁹ 2^k) কত?

১০২৩
১০২৪
৫১২
২০৪৭

(মাঝারি) কোন ধরনের graph-এ Dijkstra-র algorithm ভুল দূরত্ব দিতে পারে?

যেখানে একাধিক shortest path সমান দৈর্ঘ্যের
যেখানে কোনো edge-এর weight ঋণাত্মক
যেকোনো directed graph-এ
যে graph-এ cycle আছে

(মাঝারি) ৪ জোড়া বন্ধনী দিয়ে কতগুলো সঠিকভাবে মেলানো (balanced) বিন্যাস হয়, যেমন (()())()?

১৪
৭০
৪২
৫

(মাঝারি) দাবি: “প্রতিটি অঋণাত্মক পূর্ণসংখ্যা n-এ n² + n + 41 মৌলিক।” কোনটি সঠিক?

0 থেকে 39 পর্যন্ত মৌলিক, তাই সব n-এ প্রমাণিত
প্রথম counterexample n = 41
এটি একটি খোলা সমস্যা
n = 40-এ মান 1681 = 41², তাই দাবি মিথ্যা

(মাঝারি) P(A) = 0.5, P(B) = 0.4, P(A ∪ B) = 0.7. A আর B সম্পর্কে কোনটি সঠিক?

Mutually exclusive
Independent
Dependent, কারণ P(A ∩ B) ≠ 0
তথ্য যথেষ্ট নয়

(সহজ) ১০টি vertex আর ৩টি connected component-এর একটি forest-এ কতগুলো edge?

৯
১০
৭
৮

(মাঝারি) 1, 2, 3, 4-এর permutation-গুলো lexicographic ক্রমে সাজালে 1342-এর ঠিক পরেরটি কোনটি?

1423
1432
1324
2134

(সহজ) তিনটি Boolean variable-এর কতগুলো আলাদা Boolean function আছে?

৮
৯
১৬
২৫৬

(মাঝারি) তিন উপাদানের সেট {1, 2, 3}-এ কতগুলো reflexive relation আছে?

৫১২
৬৪
৮
৯

মহড়া শেষ করে, নম্বর লিখে তবেই নিচের block চালান।

from itertools import product, permutations
from fractions import Fraction as F
from math import comb

imp = lambda a, b: (not a) or b
ok = all(imp((p or q) and (not p or r), q or r) for p, q, r in product([0, 1], repeat=3))
print("(p∨q), (¬p∨r) ⊨ q∨r:", ok)
print("Σ 2^k, k = 0..9:", sum(2**k for k in range(10)))
print("Catalan C_4:", comb(8, 4) // 5, "| C(8,4) =", comb(8, 4))
n = next(n for n in range(100) if any((n * n + n + 41) % d == 0 for d in range(2, n * n + n + 41)))
print("n² + n + 41-এর প্রথম যৌগিক মান: n =", n, "→", n * n + n + 41, "=", 41, "×", 41)
pa, pb, pu = F(5, 10), F(4, 10), F(7, 10)
print("P(A∩B) =", pa + pb - pu, "| P(A)P(B) =", pa * pb)
print("১০ vertex, ৩ component-এর forest-এ edge:", 10 - 3)
ps = sorted("".join(p) for p in permutations("1234"))
i = ps.index("1342"); print("1342-এর আগে আর পরে:", ps[i - 1], ps[i + 1])
print("৩ variable-এর Boolean function:", 2 ** 2 ** 3)
print("৩ উপাদানে reflexive relation:", 2 ** (3 * 3 - 3), "| মোট relation:", 2 ** 9)

আসল আউটপুট:

(p∨q), (¬p∨r) ⊨ q∨r: True
Σ 2^k, k = 0..9: 1023
Catalan C_4: 14 | C(8,4) = 70
n² + n + 41-এর প্রথম যৌগিক মান: n = 40 → 1681 = 41 × 41
P(A∩B) = 1/5 | P(A)P(B) = 1/5
১০ vertex, ৩ component-এর forest-এ edge: 7
1342-এর আগে আর পরে: 1324 1423
৩ variable-এর Boolean function: 256
৩ উপাদানে reflexive relation: 64 | মোট relation: 512

প্রথম লাইন resolution-এর নিয়মটিকেই truth table-এ যাচাই করে: (p ∨ q) আর (¬p ∨ r) সত্য হলে q ∨ r সত্য। n² + n + 41-এর লাইন দেখায় 0 থেকে 39-এ সব মৌলিক, আর প্রথম ব্যতিক্রম n = 40-এ 41². Permutation-এর লাইনে 1342-এর আগে-পরে দুটিই ছাপা হয়েছে, দুটি distractor-এর উৎস মেলাতে।

AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর নিজে যাচাই করুন

AI assistant মুহূর্তে শত শত discrete math প্রশ্ন বানাতে পারে, কিন্তু সে প্রায়ই নিশ্চিত সুরে ভুল প্রমাণ দেয় (circular যুক্তি, converse প্রমাণ, base case বাদ), গণনায় off-by-one বা দুবার গোনা করে, উপপাদ্য তার শর্ত ছাড়া বলে, বড় সংখ্যার modular হিসাবে ভুল করে, আর একই প্রশ্নে দুটি সঠিক অপশন রাখে। তাই AI-এর বানানো প্রশ্ন অনুশীলনের ভালো কাঁচামাল, উত্তরপত্র নয়।

AI-এর প্রচলিত ভুল	উদাহরণ	কীভাবে ধরবেন
শর্তহীন উপপাদ্য	Fermat-এ p ∤ a বাদ, Euler-এর সূত্র disconnected graph-এ, Hall সাধারণ graph-এ	প্রতিটি উপপাদ্যের শর্ত জিজ্ঞেস করুন, তারপর প্রশ্নে মিলিয়ে নিন
ভুল গণনা	ক্রম গোনা না গোনা গুলিয়ে ফেলা, “অন্তত একটি”-তে দুবার গোনা	ছোট n-এ brute force দিয়ে সংখ্যা মেলান
Modular হিসাব	বড় ঘাতে ভুল অবশিষ্ট, inverse mod n বনাম mod φ(n)	Python-এর `pow(a, b, m)` আর `pow(a, -1, m)`
ভুল প্রমাণ	যা প্রমাণ করতে হবে তা ধরে নেওয়া, শূন্য হতে পারে এমন রাশি দিয়ে ভাগ	প্রতিটি ধাপের কারণ লিখুন; একটি counterexample খুঁজুন
বানানো উৎস	“অমুক পরীক্ষায় এসেছিল”, অস্তিত্বহীন বই বা প্রবন্ধ	উৎস দেখাতে না পারলে দাবি বাদ

নিচের প্রম্পটটি AI-কে প্রশ্ন বানাতে বলে, আর যাচাইয়ের উপায়ও চায়। উত্তর পেলে প্রতিটি সংখ্যা এই পাতার Python block-এর মতো একটি ছোট কোডে মিলিয়ে নিন।

আমি Discrete Mathematics-এর MCQ পরীক্ষার প্রস্তুতি নিচ্ছি। বিষয়: [যেমন: nested quantifier / CRT / stars and bars / Bayes / planar graph / group-এর order] কঠিনতা: [সহজ / মাঝারি / কঠিন] ৮টি MCQ বানাও। প্রতিটির জন্য: ১. ঠিক ৪টি অপশন, শুধু একটি সঠিক। দরকারি সব সংখ্যা প্রশ্নেই থাকবে। ২. হিসাবের প্রশ্নে সূত্র আর প্রতিটি ধাপ দেখাও, আর একটি ছোট Python কোড দাও যা brute force দিয়ে উত্তর মেলায়। ৩. কোনো উপপাদ্য ব্যবহার করলে তার সব শর্ত লেখো, আর প্রশ্নে শর্তগুলো পূরণ হয়েছে কি না বলো। ৪. প্রতিটি ভুল অপশন কোন ভুল ধারণা থেকে এসেছে, এক লাইনে লেখো। ৫. নিশ্চিত না হলে “নিশ্চিত নই” লেখো। কোনো প্রশ্নকে কোনো নির্দিষ্ট পরীক্ষার আসল প্রশ্ন বলে দাবি করবে না।

যাচাইয়ের চেকলিস্ট

চারটি অপশনের মধ্যে ঠিক একটি সত্য, মিলিয়ে দেখেছি
হিসাবের উত্তর ছোট ক্ষেত্রে brute force দিয়ে মিলিয়েছি
ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত প্রশ্নে পূরণ হয়েছে, দেখেছি
প্রমাণের প্রতিটি ধাপের কারণ আছে; converse বা circular যুক্তি নেই
সন্দেহজনক দাবির একটি counterexample খুঁজেছি, বা না পাওয়ার কারণ বুঝেছি
নামকরা উপপাদ্য বা ইতিহাস একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

কেন এই উত্তর ভুল? — রিভিশনের কৌশল আর বড় ধারণা

আগে নিজে ভাবুন, তারপর খুলে দেখুন।

প্র ০১Converse, inverse আর উল্টো শর্ত এত বেশি MCQ-তে ফাঁদ হয় কেন?

কারণ দৈনন্দিন ভাষা “যদি” আর “যদি এবং কেবল যদি” আলাদা করে না। “ভালো পড়লে পাস করবে” শুনে আমরা প্রায়ই ধরে নিই “পাস করেছে, তাই ভালো পড়েছে”, যা converse. George Boole ১৮৪৭ আর ১৮৫৪ সালের লেখায় যুক্তিকে বীজগণিতের রূপ দেন (পর্ব ০২); সেই বীজগণিতে p → q আর q → p-এর truth table আলাদা, আর সমতুল্য শুধু contrapositive ¬q → ¬p.

যুক্তিতে: “p → q আর q, তাই p” হলো affirming the consequent, একটি চেনা fallacy (পর্ব ০৬)।
প্রমাণে: “n² জোড় হলে n জোড়” প্রমাণ করতে গিয়ে “n জোড় হলে n² জোড়” দেখানো converse-এর প্রমাণ, মূলের নয় (পর্ব ০৮)।
সম্ভাবনায়: P(সতর্কতা | জালিয়াতি) = ০.৯৫ থেকে P(জালিয়াতি | সতর্কতা) = ০.৯৫ ধরে নেওয়া একই ভুলের সম্ভাবনার রূপ; base rate কম হলে আসল উত্তর মাত্র ০.২৮ (পর্ব ৩৯)।

রিভিশনে প্রতিটি “যদি” বাক্যের পাশে চারটি রূপ লিখুন: মূল, converse, inverse, contrapositive, আর কোন দুটি জোড়ায় সমতুল্য তা দাগান। শর্তসাপেক্ষ সম্ভাবনায় প্রতিবার লিখুন “কোনটি দেওয়া আছে, কোনটি চাওয়া হচ্ছে”।

মূল উপলব্ধি: শর্ত আর ফল অদলবদল করলে সাধারণত নতুন, আলাদা দাবি তৈরি হয়।

প্র ০২উপপাদ্যের শর্ত বাদ পড়লে কোথায় কোথায় ভুল উত্তর “সঠিক” দেখায়?

Discrete math-এর বহু MCQ-তে distractor হলো একটি উপপাদ্য, যার একটি শর্ত পূরণ হয়নি। চারটি চেনা উদাহরণ:

Fermat: a^p−1 ≡ 1 (mod p) শুধু p মৌলিক আর p ∤ a হলে। উল্টো দিক সত্য নয়: Robert Carmichael ১৯১০ সালে 561-এর কথা প্রকাশ করেন (Václav Šimerka ১৮৮৫ সালেই এমন সংখ্যার তালিকা দিয়েছিলেন বলে জানা যায়); 561 যৌগিক, অথচ সব coprime base-এ পরীক্ষা পাস করে (পর্ব ২৫)।
Euler-এর সূত্র: v − e + f = 2 connected planar graph-এর জন্য। Königsberg-এর সাত সেতুর প্রবন্ধটি সাধারণত ১৭৩৬ সালের বলে উল্লেখ করা হয়; graph theory-র শুরু সেখান থেকে ধরা হয় (পর্ব ৬০)। e ≤ 3v − 6-ও শুধু simple connected planar graph-এ, v ≥ 3 হলে।
Hall: ১৯৩৫ সালের এই উপপাদ্য bipartite graph-এর matching নিয়ে; সাধারণ graph-এর perfect matching-এর শর্ত আলাদা (পর্ব ৬৪)।
Dijkstra: ১৯৫৯ সালে প্রকাশিত algorithm-এর সঠিকতার প্রমাণ অঋণাত্মক weight ধরে নেয় (পর্ব ৬১)।

তাই কোনো অপশন একটি উপপাদ্যের নাম নিলে, প্রথমে প্রশ্নের তথ্য দিয়ে শর্তগুলো একে একে পরীক্ষা করুন: মৌলিক? connected? simple? bipartite? weight অঋণাত্মক? যেখানে একটি শর্ত ভাঙে, অপশনটি সাধারণত ফাঁদ।

মূল উপলব্ধি: উপপাদ্য = শর্ত + সিদ্ধান্ত; শর্ত ছাড়া সিদ্ধান্তের কোনো দাম নেই।

প্র ০৩গণনার MCQ-তে কোন চারটি প্রশ্ন নিজেকে আগে করবেন?

গণনার distractor প্রায় সবসময় চারটি সিদ্ধান্তের একটিতে ভুল থেকে আসে। হিসাব শুরুর আগে লিখে নিন:

ক্রম গোনা হবে? দল বাছাই হলে C(n, k), সারি বা পদ বণ্টন হলে P(n, k) (পর্ব ৩৩)।
পুনরাবৃত্তি চলবে? একই জিনিস একাধিকবার নেওয়া গেলে stars and bars: C(n + k − 1, k − 1) (পর্ব ৩৫)।
“অন্তত”, “ঠিক” না “বড়জোর”? “অন্তত একটি” প্রায়ই complement বা inclusion–exclusion চায় (পর্ব ৩১, ৪৯)।
জিনিস বা বাক্স আলাদা চেনা যায়? লেবেলহীন বাক্সে partition, তখন Stirling আর Bell সংখ্যা (পর্ব ৫০, ৫৫); symmetry থাকলে Burnside (পর্ব ৫১)।

ইতিহাসও এই সতর্কতার পক্ষে। Blaise Pascal ১৬৫৪ সালে তাঁর ত্রিভুজ নিয়ে লেখেন, যদিও একই ত্রিভুজ আগে চীন, ভারত আর পারস্যের গণিতবিদদের কাছেও পরিচিত ছিল (পর্ব ৩৪)। তবু চার শতাব্দী পরেও ছাত্রছাত্রীদের সবচেয়ে চেনা ভুল একই: একই বিন্যাস দুবার গোনা। সবচেয়ে নির্ভরযোগ্য পাহারা হলো ছোট সংখ্যায় brute force: n = 3 বা 4-এ সব বিন্যাস তালিকা করে সূত্রের সঙ্গে মেলানো, যা এই পাতার প্রতিটি Python block করে।

মূল উপলব্ধি: সূত্র বাছার আগে ক্রম, পুনরাবৃত্তি, সীমা আর চেনা যাওয়া, এই চারটি ঠিক করুন।

প্র ০৪সম্ভাবনার প্রশ্নে অন্তর্জ্ঞান কেন এত সহজে ঠকে?

কারণ আমরা সাধারণত একটি ঘটনার কথা ভাবি, অথচ প্রশ্ন প্রায়ই সব জোড়া বা সব সম্ভাবনার কথা বলে। জন্মদিনের সমস্যায় ২৩ জনে মিলের সম্ভাবনা প্রায় ০.৫০৭৩ (পর্ব ৪২), যা অবাক করে, কারণ মাথায় আসে “আমার জন্মদিনের সঙ্গে কারও মিল”। অথচ ২৩ জনে জোড়া ২৫৩টি। এই একই হিসাব hash collision-এর ঝুঁকি বোঝায়: ছোট id-তে collision আশার চেয়ে অনেক আগে আসে।

Monty Hall-এর ধাঁধাও চেনা উদাহরণ: পরিসংখ্যানবিদ Steve Selvin ১৯৭৫ সালে এটি প্রকাশ করেন (পর্ব ৩৮), আর পরে অনেক শিক্ষিত পাঠকও প্রথমে ভুল উত্তর দেন। সমাধানের চাবি একটাই: sample space আর প্রতিটি ফলের সম্ভাবনা স্পষ্ট লেখা।

তৃতীয় ফাঁদ হলো ধরে নেওয়া যে প্রত্যাশা হিসাবের জন্য independence লাগে। খামের প্রশ্নে চিঠিগুলোর ঘটনা স্বাধীন নয়, তবু linearity of expectation বলে প্রত্যাশা ঠিক ১ (পর্ব ৪০)। উল্টো দিকে, P(A ∩ B) ≠ 0 দেখে “dependent” বলা ভুল; independence-এর শর্ত P(A ∩ B) = P(A)P(B).

রিভিশনে প্রতিটি সম্ভাবনার প্রশ্নে লিখুন: sample space কী, ফলগুলো সমান সম্ভাব্য কি না, কোন শর্ত দেওয়া, আর উত্তর ০ থেকে ১-এর মধ্যে বাস্তবসম্মত কি না।

মূল উপলব্ধি: অন্তর্জ্ঞান একটি ঘটনা দেখে; গণিত সব ঘটনা গোনে।

প্র ০৫“অসম্ভব”, “কঠিন” আর “অজানা”: এই তিনটি গুলিয়ে গেলে কী হয়?

Discrete math-এ তিন ধরনের সীমা আছে, আর MCQ-তে এদের অদলবদল একটি প্রিয় distractor.

অসম্ভব (প্রমাণিত): Georg Cantor ১৮৯১ সালে diagonal যুক্তিতে দেখান কিছু অসীম সেট countable নয় (পর্ব ১৮)। Alan Turing ১৯৩৬ সালে দেখান halting problem undecidable: কোনো algorithm সব program-এর জন্য উত্তর দিতে পারে না (পর্ব ৭৫)। এগুলো সময় বা যন্ত্রের সীমা নয়, যুক্তির।
কঠিন বলে বিশ্বাস করা: Stephen Cook ১৯৭১ সালে SAT-কে NP-complete দেখান (পর্ব ৭৭)। NP-complete মানে “কোনো দ্রুত algorithm জানা নেই, আর একটি পেলে সব NP সমস্যায় পাওয়া যাবে”, “অসম্ভব” নয়। RSA-র নিরাপত্তাও এমন বিশ্বাসের ওপর: বড় n factor করা কঠিন বলে ধারণা (পর্ব ২৮)।
অজানা: P বনাম NP আজও খোলা প্রশ্ন; R(5, 5)-এর সঠিক মানও অজানা (পর্ব ৭৬)।

আরেকটি সূক্ষ্মতা: চার রঙের উপপাদ্য Kenneth Appel আর Wolfgang Haken ১৯৭৬ সালে প্রমাণ করেন কম্পিউটারের সাহায্যে (পর্ব ৬৩)। “কম্পিউটার-সহায়িত” মানে “অপ্রমাণিত” নয়; পরে proof assistant-এও সম্পূর্ণ প্রমাণ যাচাই হয়েছে (পর্ব ০১)।

মূল উপলব্ধি: “প্রমাণিত অসম্ভব”, “কঠিন বলে বিশ্বাস” আর “অজানা” তিনটি আলাদা দাবি; অপশনের শব্দ সাবধানে পড়ুন।

শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন

উপরের সব MCQ শেষ করলে নিচে আপনার মোট স্কোর দেখাবে।

ক্রমখেলনা RSA-র key তৈরির ছয় ধাপ। আগে থেকে পরে সাজান (▲▼ চেপে সরান)

দুটি আলাদা মৌলিক p আর q বাছাই
n = pq হিসাব
φ(n) = (p − 1)(q − 1) হিসাব
gcd(e, φ(n)) = 1 এমন e বাছাই
Extended Euclid দিয়ে d = e⁻¹ mod φ(n)
(n, e) প্রকাশ; d, p আর q গোপন

শব্দকোষ

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

মনে রাখুন

কারণসহ উত্তর: চাপার আগে খাতায় অপশন আর এক লাইনের কারণ; ভুলের খাতায় প্রশ্ন নয়, নিয়ম লিখুন।
যুক্তির রূপ: p → q-এর সমতুল্য শুধু contrapositive; quantifier-এর negation-এ প্রতিটি quantifier উল্টায়, আর ক্রম বদলালে অর্থ বদলায়।
শর্ত আগে: Fermat, Euler-এর সূত্র, e ≤ 3v − 6, Hall, Dijkstra, প্রতিটির শর্ত মিলিয়ে তবেই সিদ্ধান্ত।
গণনার চার প্রশ্ন: ক্রম, পুনরাবৃত্তি, “অন্তত/ঠিক/বড়জোর”, আর জিনিস বা বাক্স চেনা যায় কি না; ছোট n-এ brute force দিয়ে মেলান।
Modular হিসাব: ঘাত কমান mod φ(n) বা mod p − 1-এ, inverse নিন সঠিক modulus-এ; খেলনা RSA শুধু বোঝার জন্য।

পরের পর্বে: পর্ব ৮১ “লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — Discrete Mathematics”: MCQ চেনায় কোনটি সঠিক, লিখিত পরীক্ষা আর ভাইভা চায় কেন সঠিক; সেখানে তুলনা আর ব্যাখ্যার আদর্শ উত্তর।

MCQ প্রশ্নব্যাংক — Discrete Mathematics

এই পর্বে যা করবেন

১ · কীভাবে অনুশীলন করবেন — প্রশ্নের ধরন, বাদ দেওয়া আর সময়

প্রশ্নের চার ছাঁচ

কৌশল ১ · বাদ দেওয়ার পদ্ধতি — একটি quantifier-এর প্রশ্ন ধাপে ধাপে

কৌশল ২ · ছোট ক্ষেত্রে মিলিয়ে দেখা

কৌশল ৩ · সময় ভাগ

বারোটি বড় ফাঁদ

২ · মডিউল ১ ও ২ — যুক্তি আর প্রমাণ (১০টি প্রশ্ন)

মডিউল ১ — যুক্তি (৫টি প্রশ্ন)

মডিউল ২ — প্রমাণ (৫টি প্রশ্ন)

৩ · মডিউল ৩ ও ৪ — সেট, ফাংশন আর সংখ্যাতত্ত্ব (১১টি প্রশ্ন)

মডিউল ৩ — সেট, ফাংশন আর ক্রম (৫টি প্রশ্ন)

মডিউল ৪ — সংখ্যাতত্ত্ব (৬টি প্রশ্ন)

৪ · মডিউল ৫ ও ৬ — Cryptography-র গণিত আর গণনা (৯টি প্রশ্ন)

মডিউল ৫ — সংখ্যাতত্ত্ব থেকে cryptography (৪টি প্রশ্ন)

মডিউল ৬ — গণনা (৫টি প্রশ্ন)

৫ · মডিউল ৭ ও ৮ — সম্ভাবনা আর উন্নত গণনা (১১টি প্রশ্ন)

মডিউল ৭ — বিচ্ছিন্ন সম্ভাবনা (৫টি প্রশ্ন)

মডিউল ৮ — উন্নত গণনা (৬টি প্রশ্ন)

৬ · মডিউল ৯ ও ১০ — Relation আর graph (১০টি প্রশ্ন)

মডিউল ৯ — Relation (৪টি প্রশ্ন)

মডিউল ১০ — গ্রাফ (৬টি প্রশ্ন)

৭ · মডিউল ১১ ও ১২ — Tree আর বীজগাণিতিক কাঠামো (৮টি প্রশ্ন)

মডিউল ১১ — Tree (৪টি প্রশ্ন)

মডিউল ১২ — বীজগাণিতিক কাঠামো আর Boolean algebra (৪টি প্রশ্ন)

৮ · মডিউল ১৩ — গণনার মডেল আর উন্নত বিষয় (৫টি প্রশ্ন)

৯ · মিশ্র মহড়া — ঘড়ি ধরে ১০টি প্রশ্ন, সব মডিউল থেকে

AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর নিজে যাচাই করুন

যাচাইয়ের চেকলিস্ট

কেন এই উত্তর ভুল? — রিভিশনের কৌশল আর বড় ধারণা

শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন

শব্দকোষ

মনে রাখুন

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