লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — Discrete Mathematics

সংজ্ঞা: Direct proof-এ p ধরে সংজ্ঞা আর আগের উপপাদ্য দিয়ে q-তে পৌঁছাই। Contrapositive-এ ¬q → ¬p প্রমাণ করি, যা p → q-এর logically equivalent. Contradiction-এ p ∧ ¬q ধরে একটি বিরোধ r ∧ ¬r বের করি। Proof by cases-এ p-কে p₁ ∨ … ∨ p_k-এ ভাগ করে প্রতিটি ক্ষেত্র থেকে q দেখাই।

Counterexample: “সব x-এর জন্য P(x)” মিথ্যা দেখাতে একটি counterexample-ই যথেষ্ট। কিন্তু সত্য প্রমাণে হাজার উদাহরণও যথেষ্ট নয়: n² + n + 41 সংখ্যাটি n = 0 থেকে 39 পর্যন্ত মৌলিক, অথচ n = 40-এ 1681 = 41²। আর “কোনো x আছে” ধরনের দাবিতে একটি উদাহরণই প্রমাণ (constructive existence).

সীমা: অনেক “contradiction” প্রমাণ আসলে ছদ্মবেশী contrapositive: ¬q ধরে ¬p পেলে বিরোধ টানার দরকার নেই, contrapositive লিখলেই পরিষ্কার। Contradiction-এ ¬q-এর নেতিবাচক রূপ ঠিকভাবে লিখতে হয়: “সব n-এ” এর নেতি “কোনো n-এ নয়”।

পরীক্ষক যা খোঁজেন: চার কাঠামো প্রতীকে (৪); প্রতিটির একটি সঠিক উদাহরণ (৩); কখন কোনটি (২); counterexample-এর ভূমিকা (১)। পর্ব ০৮ · পর্ব ০৯

যেখানে নম্বর কাটে: converse (q → p) প্রমাণ করে ফেলা; contradiction-এ ¬q-এর বদলে ¬p ধরা; cases-এ কোনো ক্ষেত্র (যেমন n = 0 বা ঋণাত্মক) বাদ রাখা।

সংজ্ঞা: সাধারণ induction: P(b) সত্য, আর প্রতিটি k ≥ b-তে P(k) → P(k + 1) হলে সব n ≥ b-তে P(n) সত্য। Strong induction: basis P(b), …, P(b + j) সত্য, আর প্রতিটি k ≥ b + j-তে P(b) ∧ … ∧ P(k) → P(k + 1) হলে সব n ≥ b-তে P(n) সত্য।

সম্পর্ক: দুটি সমান শক্তিশালী। Q(n) = “P(b), …, P(n) সবই সত্য” নিলে strong induction-এর প্রমাণ Q-এর ওপর সাধারণ induction হয়ে যায়। আর দুটিই well-ordering principle-এর সমতুল্য: ℕ-এর প্রতিটি অশূন্য subset-এর একটি ক্ষুদ্রতম উপাদান আছে। তাই “minimal counterexample” যুক্তি (সবচেয়ে ছোট ব্যতিক্রম ধরে বিরোধ) আসলে induction-এরই আরেক রূপ।

উদাহরণ: ৩ আর ৫ টাকার টিকিট দিয়ে n ≥ 8 টাকা ঠিক মেটানো যায়। Strong induction-এর step: n − 3 মেটানো গেলে একটি ৩ টাকার টিকিট যোগ করলেই n. এই step তিন ধাপ পেছনে তাকায়, তাই basis 8, 9, 10 তিনটিই লাগে।

def payable(n):                      # n = 3x + 5y with x, y >= 0 ?
    return any((n - 5 * y) % 3 == 0 for y in range(n // 5 + 1))

print("not payable up to 30:", [n for n in range(1, 31) if not payable(n)])
print("every n in 8..2000 payable:", all(payable(n) for n in range(8, 2001)))

# strong induction uses P(n-3) -> P(n): it needs three bases
for n in (8, 9, 10):
    y = next(y for y in range(n // 5 + 1) if (n - 5 * y) % 3 == 0)
    print(f"base {n:2} = 3*{(n - 5 * y) // 3} + 5*{y}")

# what goes wrong with only one base (n = 8)?
reached = {8}
for n in range(9, 20):
    if n - 3 in reached:
        reached.add(n)
print("from base 8 alone, the step reaches:", sorted(reached))

not payable up to 30: [1, 2, 4, 7]
every n in 8..2000 payable: True
base  8 = 3*1 + 5*1
base  9 = 3*3 + 5*0
base 10 = 3*0 + 5*2
from base 8 alone, the step reaches: [8, 11, 14, 17]

সীমা: Recursive সংজ্ঞার সেটে (string, tree, সূত্র) একই ধারণার নাম structural induction: basis-এ মৌলিক উপাদান, step-এ প্রতিটি নির্মাণ-নিয়ম (পর্ব ১২)। “সব ঘোড়ার রং এক” ধরনের ভুল প্রমাণ step-এর একটি ছোট k-তে (১ থেকে ২) ভাঙে; step-কে প্রতিটি k-তে খাটতে হয়।

পরীক্ষক যা খোঁজেন: দুই নীতি প্রতীকে (২); সমতুল্যতা আর well-ordering (২); ছক (২); উদাহরণ আর basis-এর সংখ্যার কারণ (৩); structural induction বা ভুলের উদাহরণ (১)। পর্ব ১০ · পর্ব ১১

যেখানে নম্বর কাটে: “strong induction বেশি শক্তিশালী” লেখা; basis কম দেওয়া; hypothesis-এ যা প্রমাণ করতে হবে সেটিই ধরে নেওয়া (সব n-এ P(n)).

চার রূপ: p = “অর্ডার ১০০০ টাকার বেশি”, q = “ডেলিভারি ফ্রি”। মূল p → q; converse q → p (“ফ্রি হলে অর্ডার ১০০০-এর বেশি”); inverse ¬p → ¬q; contrapositive ¬q → ¬p (“ফ্রি না হলে অর্ডার ১০০০-এর বেশি নয়”)। Truth table-এর চার সারিতে (TT, TF, FT, FF) p → q আর contrapositive দুটিরই মান 1, 0, 1, 1; converse আর inverse দুটির 1, 1, 0, 1. সারি p = মিথ্যা, q = সত্য (ছোট অর্ডারেও ফ্রি, যেমন কোনো উৎসবের দিনে) মূল দাবি ভাঙে না, কিন্তু converse ভাঙে। তাই মূল ≡ contrapositive, আর converse ≡ inverse.

Quantifier-এর ক্রম: ডোমেইন {0, 1, 2}, আর P(x, y) মানে x + y ≡ 0 (mod 3). ∀x ∃y P সত্য (প্রতিটি x-এর জন্য y = (3 − x) mod 3), কিন্তু ∃y ∀x P মিথ্যা (কোনো একটি y সব x-এর জন্য খাটে না)। ভাষায়: “প্রতিটি রাইডারের একটি রুট আছে” বনাম “একটি রুট সব রাইডারের”। ∃y ∀x থেকে ∀x ∃y আসে, উল্টোটি নয় (পর্ব ০৫)।

পরীক্ষক যা খোঁজেন: চার রূপ (২); সমতুল্যতা সারি ধরে (১); quantifier-এর উদাহরণ আর কোন দিকে implication (২)। পর্ব ০২ · পর্ব ০৩

যেখানে নম্বর কাটে: inverse-কে contrapositive বলা; ¬(p → q)-কে ¬p → ¬q লেখা (ঠিক হলো p ∧ ¬q).

সংজ্ঞা: একটি সেট countable, যদি সসীম হয় অথবা ℕ-এর সঙ্গে একটি bijection থাকে (তখন countably infinite). অর্থাৎ উপাদানগুলোকে ১ম, ২য়, ৩য় … করে একটি তালিকায় সাজানো যায়, যাতে প্রত্যেকে কোনো সসীম অবস্থানে আসে। অসীম কিন্তু countable নয় এমন সেট uncountable.

Diagonal-এর ধারণা: ধরুন (0, 1)-এর সব সংখ্যার একটি তালিকা আছে। i-তম সংখ্যার i-তম অঙ্ক বদলে একটি নতুন সংখ্যা বানাই; এটি প্রতিটি সারি থেকে অন্তত এক অঙ্কে আলাদা, তাই তালিকায় নেই, বিরোধ। Cantor-এর উপপাদ্য-এ একই কৌশল: যেকোনো f: S → P(S)-এর জন্য D = {x ∈ S : x ∉ f(x)} কোনো f(x)-এর সমান হতে পারে না, তাই কোনো f onto নয়। (দশমিকের 0.0999… = 0.1000… সমস্যা এড়াতে অঙ্ক 9 বা 0 বেছে না নেওয়ার সতর্কতা পর্ব ১৮-এ।)

from itertools import combinations, product

S = [0, 1, 2]
P = [frozenset(c) for r in range(4) for c in combinations(S, r)]
print("|S| =", len(S), " |P(S)| =", len(P))

checked = 0
for f in product(P, repeat=len(S)):        # every function f: S -> P(S)
    D = frozenset(x for x in S if x not in f[x])
    assert D not in f                       # D differs from f(x) at x
    checked += 1
print("functions checked:", checked, "- none is onto")

rows = ["0110", "1010", "0001", "1111"]     # a 'complete' list?
new = "".join("1" if r[i] == "0" else "0" for i, r in enumerate(rows))
print("diagonal flip:", new, "| in the list?", new in rows)

|S| = 3  |P(S)| = 8
functions checked: 512 - none is onto
diagonal flip: 1110 | in the list? False

কম্পিউটার বিজ্ঞানে ফল: প্রোগ্রাম countable, কিন্তু {0, 1}-এর ওপর language-এর সেট P(Σ*) uncountable. তাই এমন language আছে, যা কোনো প্রোগ্রাম decide করে না (পর্ব ১৮, পর্ব ৭৫)। এটি অস্তিত্বের প্রমাণ; কোন সমস্যা, তা বলে না। নির্দিষ্ট উদাহরণ halting problem (চ-০৩)।

পরীক্ষক যা খোঁজেন: সংজ্ঞা (২); তিনটি countable উদাহরণ, তালিকার ধারণাসহ (২); diagonal-এর যুক্তি (৩); CS-এর ফল (২); সাধারণ ভুল (১)। পর্ব ১৮

যেখানে নম্বর কাটে: “সব অসীম সেট সমান আকারের” লেখা; “ℚ ঘন, তাই uncountable” বলা; diagonal-এ নতুন সংখ্যা কেন তালিকায় নেই, তা না বলা।

তুলনা: Fermat: p মৌলিক আর p ∤ a হলে a^p−1 ≡ 1 (mod p). Euler: gcd(a, n) = 1 হলে a^φ(n) ≡ 1 (mod n), যেকোনো n ≥ 1-এ। n = p মৌলিক হলে φ(p) = p − 1, তাই Fermat হলো Euler-এর বিশেষ রূপ। দুটির কাজ একই: বিশাল ঘাত ছোট করা।

Fermat test-এর ফাঁক: উপপাদ্যের converse সত্য নয়। Carmichael সংখ্যা (যেমন 561 = 3 · 11 · 17) যৌগিক, অথচ প্রতিটি সহমৌলিক a-তে a⁵⁶⁰ ≡ 1. Miller–Rabin আরেকটি সত্য ব্যবহার করে: মৌলিক p-এর mod-এ 1-এর বর্গমূল শুধু ±1. n − 1 = 2^sd লিখে a^d-কে বারবার বর্গ করি; ±1 ছাড়া অন্য কোনো বর্গমূল দেখা দিলে n যৌগিক।

from math import gcd

n = 561
print("561 = 3 * 11 * 17 ->", 3 * 11 * 17 == n)
coprime = [a for a in range(2, n) if gcd(a, n) == 1]
caught = [a for a in coprime if pow(a, n - 1, n) != 1]
print("coprime bases:", len(coprime), "| Fermat test catches:", len(caught))

d, s = n - 1, 0
while d % 2 == 0:
    d, s = d // 2, s + 1
print(f"n - 1 = 2^{s} * {d}")
x = pow(2, d, n)
seq = [x]
for _ in range(s - 1):
    x = x * x % n
    seq.append(x)
print("Miller-Rabin, base 2:", seq)
print("67^2 mod 561 =", 67 * 67 % n, "-> 67 is a square root of 1, not +-1")

561 = 3 * 11 * 17 -> True
coprime bases: 319 | Fermat test catches: 0
n - 1 = 2^4 * 35
Miller-Rabin, base 2: [263, 166, 67, 1]
67^2 mod 561 = 1 -> 67 is a square root of 1, not +-1

পরীক্ষক যা খোঁজেন: দুই উপপাদ্য শর্তসহ (২); বিশেষ রূপের সম্পর্ক (১); Carmichael আর Miller–Rabin-এর ধারণা (২)। পর্ব ২৪ · পর্ব ২৫

যেখানে নম্বর কাটে: p ∤ a বা gcd(a, n) = 1 শর্ত বাদ দেওয়া; “Fermat test পাস করলে মৌলিক” লেখা।

সংজ্ঞা: ভিন্ন মৌলিক p, q; n = pq; e এমন যে gcd(e, (p − 1)(q − 1)) = 1; d = e⁻¹ mod (p − 1)(q − 1). Public key (n, e), private key d. E(m) = m^e mod n, D(c) = c^d mod n, যেখানে 0 ≤ m < n.

সঠিকতার মূল যুক্তি: ed = 1 + k(p − 1)(q − 1). mod p-এ দুই ক্ষেত্র: p ∤ m হলে Fermat দিয়ে m^ed = m · (m^p−1)^k(q−1) ≡ m; p ∣ m হলে দুই পাশই 0. একইভাবে mod q. তাই p আর q দুটিই m^ed − m-কে ভাগ করে, আর p, q ভিন্ন মৌলিক বলে pq-ও ভাগ করে। খেয়াল করুন, gcd(m, n) = 1 লাগেনি; এই ক্ষেত্র-ভাগই পরীক্ষার সবচেয়ে প্রচলিত ফাঁক। (ধাপে ধাপে পূর্ণ প্রমাণ পর্ব ২৮-এর উপপাদ্য ৪.২-এ।)

কেন padding: Textbook RSA-এর তিন দুর্বলতা n বড় হলেও থাকে: (১) deterministic, তাই বার্তার সম্ভাব্য মান কম হলে (ঘণ্টা 0–23) যে কেউ public key দিয়ে সব মান encrypt করে মিলিয়ে নেন, অর্থাৎ semantic security নেই; (২) malleable: E(m₁)E(m₂) ≡ E(m₁m₂); (৩) ছোট e আর ছোট m-এ m^e < n হলে mod কাজই করে না, সাধারণ e-তম মূল নিলেই m. Padding (encryption-এ OAEP, সইয়ে PSS) এলোমেলোতা আর কাঠামো যোগ করে এগুলো বন্ধ করে।

p, q, e = 61, 53, 17                     # TOY numbers, never for real use
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi)
print("n =", n, " phi =", phi, " d =", d)

ok = all(pow(pow(m, e, n), d, n) == m for m in range(n))
share = sum(1 for m in range(n) if m % p == 0 or m % q == 0)
print("D(E(m)) == m for all", n, "messages:", ok)
print("messages sharing a factor with n:", share)

c = pow(9, e, n)                         # hour 9, sent twice
print("E(9) today and tomorrow:", c, pow(9, e, n))
guess = next(h for h in range(24) if pow(h, e, n) == c)
print("attacker tries 0..23 with public key, finds:", guess)
print("E(5)*E(7) mod n == E(35):", pow(5, e, n) * pow(7, e, n) % n == pow(35, e, n))

n = 3233  phi = 3120  d = 2753
D(E(m)) == m for all 3233 messages: True
messages sharing a factor with n: 113
E(9) today and tomorrow: 1972 1972
attacker tries 0..23 with public key, finds: 9
E(5)*E(7) mod n == E(35): True

সীমা: নিরাপত্তা দাঁড়িয়ে আছে বড় n factor করার কঠিনতার অনুমানের ওপর; φ(n) জানা আর factor জানা সমতুল্য (পর্ব ২৮)। এটি প্রমাণিত কঠিনতা নয়, একটি অনুমান।

পরীক্ষক যা খোঁজেন: key তৈরি আর দুই সূত্র (২); সঠিকতার দুই ক্ষেত্র আর pq-তে জোড়া দেওয়া (৪); তিন দুর্বলতা (৩); padding ও বাস্তবের সাবধানতা (১)। পর্ব ২৮ · পর্ব ২৩

যেখানে নম্বর কাটে: “gcd(m, n) = 1 না হলে কাজ করে না” লেখা; d-কে mod n-এ হিসাব করা; “n বড় হলেই নিরাপদ” বলা।

দুই প্রশ্ন: n রকম জিনিস থেকে r বার বাছাইয়ে জিজ্ঞেস করুন: (ক) ক্রম কি গুরুত্বপূর্ণ? (খ) একই জিনিস একাধিকবার নেওয়া যায়?

C(n, r) = P(n, r)/r!: প্রতিটি দল r! ভাবে সাজানো যায়, তাই ভাগের নিয়ম। Stars and bars: r টি তারা (বাছাই) আর n − 1টি দাগ (রকমের সীমানা) এক সারিতে; প্রতিটি সারি ঠিক একটি বাছাই, আর উল্টোটাও। r + n − 1টি ঘরের কোন n − 1টিতে দাগ, তা বাছলেই সারি ঠিক হয়, তাই C(n + r − 1, n − 1) = C(n + r − 1, r). একই bijection-এ x₁ + … + x_n = r-এর অঋণাত্মক সমাধান। উদাহরণ: বাজারঘরের ৫ রকম মিষ্টি থেকে ৩টি।

from itertools import product, permutations, combinations
from itertools import combinations_with_replacement as cwr
from math import comb, perm

items, r = "ABCDE", 3                    # 5 kinds of sweets, pick 3
n = len(items)
rows = [
    ("ordered, repeats allowed    n^r", len(list(product(items, repeat=r))), n ** r),
    ("ordered, no repeats      P(n,r)", len(list(permutations(items, r))), perm(n, r)),
    ("unordered, no repeats    C(n,r)", len(list(combinations(items, r))), comb(n, r)),
    ("unordered, repeats  C(n+r-1, r)", len(list(cwr(items, r))), comb(n + r - 1, r)),
]
for name, brute, formula in rows:
    print(f"{name}: brute {brute:3}  formula {formula:3}")

sols = sum(1 for a in range(8) for b in range(8 - a))   # c = 7 - a - b
print("x1 + x2 + x3 = 7, xi >= 0:", sols, "= C(9, 2) =", comb(9, 2))

ordered, repeats allowed    n^r: brute 125  formula 125
ordered, no repeats      P(n,r): brute  60  formula  60
unordered, no repeats    C(n,r): brute  10  formula  10
unordered, repeats  C(n+r-1, r): brute  35  formula  35
x1 + x2 + x3 = 7, xi >= 0: 36 = C(9, 2) = 36

সীমা: “অন্তত একটি” শর্ত থাকলে হয় নিম্নসীমা সরানো, নয় complement. ঊর্ধ্বসীমা (x_i ≤ 3) থাকলে stars and bars একা চলে না; inclusion–exclusion লাগে (ঘ-০২)। আর আলাদা জিনিস আলাদা বাক্সে দিলে উত্তর n^r, stars and bars নয়।

পরীক্ষক যা খোঁজেন: দুই প্রশ্ন আর ২ × ২ ছক (৩); C = P/r!-এর কারণ (১); stars and bars-এর bijection (৩); দুই সমাধান-গণনা (২); সীমা (১)। পর্ব ৩১ · পর্ব ৩৩ · পর্ব ৩৫

যেখানে নম্বর কাটে: একই রকম জিনিসকে আলাদা ধরে গোনা; C(n + r − 1, r)-এ r আর n − 1 গুলিয়ে ভুল সংখ্যা বসানো; একই দল দুবার গোনা (overcounting).

সংজ্ঞা: P(B) > 0 হলে P(A ∣ B) = P(A ∩ B)/P(B): B ঘটেছে জানলে sample space ছোট হয়ে B হয়ে যায়। Bayes: P(H ∣ E) = P(E ∣ H)P(H) / [P(E ∣ H)P(H) + P(E ∣ Hᶜ)P(Hᶜ)]।

ভুল ১ ও ২ (উল্টো শর্ত আর base rate): “filter ৯৫% জালিয়াতি ধরে” মানে P(সতর্কতা ∣ জালিয়াতি) = ০.৯৫; কিন্তু প্রশ্ন P(জালিয়াতি ∣ সতর্কতা)। ১০,০০০ অর্ডার ভাবুন: ১০০টি জালিয়াতি, তার ৯৫টিতে সতর্কতা; ৯৯০০টি সৎ, তার ৪৯৫টিতে ভুল সতর্কতা। মোট ৫৯০ সতর্কতার মাত্র ৯৫টি সত্যিকারের, ৯৫/৫৯০ = ১৯/১১৮ ≈ ১৬%. জালিয়াতি বিরল বলে ভুল সতর্কতাই বেশি।

ভুল ৩: Mutually exclusive মানে A ∩ B = ∅; independent মানে P(A ∩ B) = P(A)P(B). দুটির সম্ভাবনা ধনাত্মক হলে mutually exclusive ঘটনা কখনো independent নয়: একটি ঘটলে অন্যটি নিশ্চিতভাবে ঘটেনি, এটাই সবচেয়ে বড় নির্ভরতা।

from fractions import Fraction as F

prior, sens, fpr = F(1, 100), F(95, 100), F(5, 100)
alarm = sens * prior + fpr * (1 - prior)
post = sens * prior / alarm
print("P(alarm | fraud) =", sens)
print("P(fraud | alarm) =", post, "~", round(float(post), 4))

P = lambda E: F(len(E), 6)               # one fair die
A, B, C = {2, 4, 6}, {1, 2}, {1, 3, 5}
print("A,B independent?", P(A & B) == P(A) * P(B), "| disjoint?", not (A & B))
print("A,C independent?", P(A & C) == P(A) * P(C), "| disjoint?", not (A & C))

stay = switch = 0                        # Monty Hall, all 9 equally likely cases
for car in range(3):
    for pick in range(3):
        opened = min(x for x in range(3) if x not in (pick, car))
        other = 3 - pick - opened
        stay += pick == car
        switch += other == car
print("stay wins", F(stay, 9), "| switch wins", F(switch, 9))

P(alarm | fraud) = 19/20
P(fraud | alarm) = 19/118 ~ 0.161
A,B independent? True | disjoint? False
A,C independent? False | disjoint? True
stay wins 1/3 | switch wins 2/3

পরীক্ষক যা খোঁজেন: সংজ্ঞা আর P(B) > 0 শর্ত (২); Bayes-এর হিসাব, ভগ্নাংশে বা স্বাভাবিক সংখ্যায় (৩); দুই উল্টো শর্তের পার্থক্য (২); independent বনাম disjoint, উদাহরণসহ (৩)। পর্ব ৩৯

যেখানে নম্বর কাটে: উত্তর “৯৫%” লেখা; হর-এ শুধু P(E ∣ H)P(H) রাখা; pairwise independence থেকে mutual independence দাবি করা।

তুলনা: E[X + Y] = E[X] + E[Y] সবসময় সত্য: যোগফলটি প্রতিটি outcome-এ আলাদা করে ভাঙে, যৌথ বণ্টন লাগে না। কিন্তু Var(X + Y) = Var X + Var Y + 2Cov(X, Y); শেষ পদ শূন্য হয় কেবল X, Y uncorrelated হলে (independence যথেষ্ট)। দুটি স্বাধীন ছক্কা: E = 7/2 + 7/2 = 7, আর variance 35/12 + 35/12 = 35/6. কিন্তু Y = X নিলে E[2X] = 7 একই, অথচ Var(2X) = 4 · 35/12 = 35/3, দ্বিগুণ।

Indicator: n জনের এলোমেলো permutation-এ নিজের জায়গায় থাকা মানুষের প্রত্যাশিত সংখ্যা: I_i = 1 যদি i নিজের জায়গায়, E[I_i] = 1/n, তাই মোট n · (1/n) = 1, যেকোনো n-এ। I_i-গুলো independent নয়, তবু linearity খাটে (n = 5-এ ১২০টি permutation গুনে ঠিক 1 মিলেছে)।

পরীক্ষক যা খোঁজেন: দুই সূত্র আর Cov-এর পদ (২); ছক্কার দুই ক্ষেত্র (২); indicator (১)। পর্ব ৪০ · পর্ব ৪১

যেখানে নম্বর কাটে: linearity-র জন্য independence দাবি করা; E[XY] = E[X]E[Y] সব ক্ষেত্রে লেখা।

তিন সমাধান: (১) r² − 5r + 6 = 0, মূল 2 আর 3; a_n = α2ⁿ + β3ⁿ; α + β = 1, 2α + 3β = 4 থেকে β = 2, α = −1; a_n = 2 · 3ⁿ − 2ⁿ. (২) Hanoi h_n = 2h_n−1 + 1, h₀ = 0: ধ্রুবক particular solution c = 2c + 1 থেকে c = −1; h_n = 2ⁿ − 1. (৩) a = 2, b = 2, d = 1: d = log₂2, case 2, T(n) = Θ(n log n). তুলনার জন্য U(n) = 8U(n/2) + n²: log₂8 = 3 > 2, case 1, Θ(n³)।

a = [1, 4]                               # a_n = 5a_{n-1} - 6a_{n-2}
for n in range(2, 21):
    a.append(5 * a[-1] - 6 * a[-2])
print("characteristic roots 2, 3:", all(a[n] == 2 * 3**n - 2**n for n in range(21)))

h = [0]                                  # h_n = 2h_{n-1} + 1 (Hanoi)
for n in range(1, 21):
    h.append(2 * h[-1] + 1)
print("particular solution -1:", all(h[n] == 2**n - 1 for n in range(21)))

T = {1: 1}                               # T(n) = 2T(n/2) + n
for k in range(1, 21):
    T[2**k] = 2 * T[2**(k - 1)] + 2**k
print("master case 2, T(2^k) = 2^k (k+1):", all(T[2**k] == 2**k * (k + 1) for k in range(21)))

U = {1: 1}                               # U(n) = 8U(n/2) + n^2
for k in range(1, 11):
    U[2**k] = 8 * U[2**(k - 1)] + 4**k
print("U(n)/n^3 for n = 2^4, 2^7, 2^10:", [round(U[2**k] / 8**k, 4) for k in (4, 7, 10)])

characteristic roots 2, 3: True
particular solution -1: True
master case 2, T(2^k) = 2^k (k+1): True
U(n)/n^3 for n = 2^4, 2^7, 2^10: [1.9375, 1.9922, 1.999]

সীমা: Master theorem খাটে না যখন উপসমস্যা অসমান (T(n/3) + T(2n/3) + n), ভাগ নয় বিয়োগ (T(n − 1) + n), বা চালিকা-খরচ বহুপদী নয় (2T(n/2) + n log n; উত্তর Θ(n log² n), পর্ব ৪৭)। Particular solution-এর অনুমান নিজেই একটি মূল হলে n দিয়ে গুণ করতে হয় (resonance).

পরীক্ষক যা খোঁজেন: ছক (৩); তিন সমাধান, initial condition বসিয়ে (৪); master-এর case বাছাইয়ের কারণ (২); সীমা (১)। পর্ব ৪৫ · পর্ব ৪৬ · পর্ব ৪৭

যেখানে নম্বর কাটে: সাধারণ সমাধানে initial condition না বসানো; particular solution-কে একা উত্তর ধরা; master theorem-এ log_ba-এর বদলে a/b তুলনা।

Complement: “অন্তত একটি” প্রশ্নে সরাসরি গোনা জটিল, কিন্তু “একটিও না” সহজ হলে মোট থেকে বিয়োগ। PIN: 10⁴ − 10 · 9 · 8 · 7 = 10000 − 5040 = 4960.

Inclusion–exclusion: কয়েকটি শর্তের যেকোনোটি ভাঙে এমন জিনিস গুনতে, যখন শর্তগুলো একসঙ্গেও ভাঙতে পারে: |A₁ ∪ … ∪ A_n| = ∑|A_i| − ∑|A_i ∩ A_j| + … । Derangement-এ A_i = “i নিজের জায়গায়”; k টি নির্দিষ্ট জায়গা স্থির রাখার উপায় (n − k)!, তাই D_n = ∑_k=0ⁿ (−1)^kC(n, k)(n − k)! = n! ∑ (−1)^k/k!. D₄ = 9, D₅ = 44, আর D_n/n! দ্রুত 1/e ≈ 0.3679-এর দিকে যায় (n = 7 পর্যন্ত brute force দিয়ে মেলানো)।

কখন কোনটি: একটি “খারাপ” ঘটনা থাকলে complement যথেষ্ট; অনেকগুলো পরস্পর-ছেদী শর্তে inclusion–exclusion. দুটিই আসলে একই নীতি: complement হলো এক সেটের inclusion–exclusion.

পরীক্ষক যা খোঁজেন: দুই পদ্ধতির সংজ্ঞা (২); PIN (১); D_n-এর সূত্র আর একটি মান (২)। পর্ব ৩১ · পর্ব ৪৯

যেখানে নম্বর কাটে: চিহ্ন একান্তর না করা; ছেদগুলো বাদ দিয়ে শুধু যোগ করা।

সংজ্ঞা: সেট A-এর ওপর R একটি equivalence relation, যদি reflexive, symmetric আর transitive; একটি partial order, যদি reflexive, antisymmetric (aRb আর bRa হলে a = b) আর transitive.

from itertools import product

def props(A, R):
    return (all((a, a) in R for a in A),                      # reflexive
            all((b, a) in R for (a, b) in R),                 # symmetric
            all(a == b for (a, b) in R if (b, a) in R),       # antisymmetric
            all((a, d) in R for (a, b) in R for (c, d) in R if b == c))

A = range(1, 13)
div = {(a, b) for a in A for b in A if b % a == 0}
mod3 = {(a, b) for a in A for b in A if (a - b) % 3 == 0}
print("(refl, sym, antisym, trans)")
print("a | b on 1..12     :", props(A, div))
print("a = b (mod 3)      :", props(A, mod3))
print("classes mod 3:", sorted({tuple(b for b in A if (a - b) % 3 == 0) for a in A}))

X = range(3)
pairs = [(a, b) for a in X for b in X]
eq = po = both = 0
for bits in product([0, 1], repeat=9):   # all 512 relations on {0,1,2}
    r, s, an, t = props(X, {pr for pr, k in zip(pairs, bits) if k})
    eq += r and s and t
    po += r and an and t
    both += r and s and an and t
print("on 3 elements: equivalences", eq, "| partial orders", po, "| both", both)

(refl, sym, antisym, trans)
a | b on 1..12     : (True, False, True, True)
a = b (mod 3)      : (True, True, False, True)
classes mod 3: [(1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12)]
on 3 elements: equivalences 5 | partial orders 19 | both 1

সীমা: ঋণাত্মকসহ ℤ-এ বিভাজ্যতা antisymmetric নয় (2 ∣ −2 আর −2 ∣ 2), তাই সেখানে partial order নয়। “Antisymmetric মানে symmetric নয়” ভুল: খালি relation দুটিই।

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); ছক (৩); দুই উদাহরণের ধর্ম যাচাই (২); class আর Hasse-এর ছবি (২); “দুটিই কেবল সমতা” (১)। পর্ব ৫২ · পর্ব ৫৫ · পর্ব ৫৬

যেখানে নম্বর কাটে: transitivity যাচাইয়ে শুধু কয়েকটি জোড়া দেখা; antisymmetric আর asymmetric গুলিয়ে ফেলা।

সংজ্ঞা: Euler circuit প্রতিটি edge ঠিক একবার ব্যবহার করে শুরুতে ফেরে; Hamilton cycle প্রতিটি vertex ঠিক একবার ছুঁয়ে ফেরে।

def euler_kind(adj):
    odd = sum(len(v) % 2 for v in adj.values())   # graphs here are connected
    return {0: "Euler circuit", 2: "Euler trail only"}.get(odd, "neither")

def ham_cycle(adj):
    n, path = len(adj), [0]
    def go():
        if len(path) == n:
            return 0 in adj[path[-1]]
        for v in adj[path[-1]]:
            if v not in path:
                path.append(v)
                if go():
                    return True
                path.pop()
        return False
    return go()

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    return adj

K4 = graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
bowtie = graph([(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)])
outer = [(i, (i + 1) % 5) for i in range(5)]
petersen = graph(outer + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)])
for name, g in [("K4", K4), ("bowtie", bowtie), ("Petersen", petersen)]:
    print(f"{name:8} {euler_kind(g):17} Hamilton cycle: {ham_cycle(g)}")

K4       neither           Hamilton cycle: True
bowtie   Euler circuit     Hamilton cycle: False
Petersen neither           Hamilton cycle: False

ইতিহাস ও সীমা: Königsberg-এর সেতু নিয়ে Euler-এর প্রবন্ধ সাধারণত ১৭৩৬ সালের বলে উল্লেখ করা হয়। Dirac আর Ore কেবল যথেষ্ট শর্ত: শর্ত না মিললেও Hamilton cycle থাকতে পারে (যেমন যেকোনো cycle graph C_n, n ≥ 5).

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা, edge বনাম vertex (২); Euler-এর iff শর্ত (২); Hamilton-এর যথেষ্ট ও আবশ্যিক শর্ত (২); জটিলতার পার্থক্য (২); তিন উদাহরণ (২)। পর্ব ৬০

যেখানে নম্বর কাটে: connected শর্ত বাদ; Dirac-কে iff লেখা; “Hamilton কঠিন, তাই সব graph-এ কঠিন” বলা (বিশেষ শ্রেণিতে সহজ)।

তথ্যগুলো: (১) Euler-এর সূত্র: connected planar graph-এর যেকোনো plane drawing-এ v − e + f = 2 (পাঁচটি Platonic solid-এ মিলিয়ে দেখা যায়, যেমন cube: 8 − 12 + 6). (২) simple planar, v ≥ 3 হলে e ≤ 3v − 6, কারণ প্রতিটি face-এর degree ≥ 3, তাই 2e ≥ 3f. (৩) এর ওপর ত্রিভুজও না থাকলে face-এর degree ≥ 4, তাই e ≤ 2v − 4; সাধারণভাবে girth g হলে e ≤ g(v − 2)/(g − 2). (৪) প্রতিটি planar graph-এ degree ≤ 5-এর একটি vertex আছে। (৫) Kuratowski (১৯৩০): planar ⇔ কোনো subgraph K₅ বা K_3,3-এর subdivision নয়। (৬) চার রঙের উপপাদ্য: প্রতিটি planar graph-এর chromatic number ≤ 4; প্রমাণ Appel ও Haken, ১৯৭৬, কম্পিউটার-নির্ভর।

সীমা: e ≤ 3v − 6 কেবল আবশ্যিক শর্ত: K_3,3 এটি মানে (9 ≤ 12) তবু planar নয়। তাই অসমতা দিয়ে “planar নয়” প্রমাণ হয়, “planar” প্রমাণ হয় না; তার জন্য একটি plane drawing দেখাতে হয়। Euler-এর সূত্র disconnected graph-এ c টি component হলে v − e + f = 1 + c.

পরীক্ষক যা খোঁজেন: ছয় তথ্য শর্তসহ (৪); দুই অসমতার কারণ, face-এর degree দিয়ে (২); তিন graph (৩); আবশ্যিক বনাম যথেষ্ট (১)। পর্ব ৬২ · পর্ব ৬৩

যেখানে নম্বর কাটে: simple বা v ≥ 3 শর্ত বাদ; K_3,3-এ 3v − 6 খাটিয়ে “planar” সিদ্ধান্ত।

Algorithm: প্রতিটি চিহ্ন একটি leaf, ওজন = কতবার আসে। বারবার সবচেয়ে হালকা দুটি tree জোড়া দিই, নতুন root-এর ওজন দুটির যোগফল, যতক্ষণ না একটি tree থাকে। বাঁয়ে 0, ডানে 1.

কেন সর্বোত্তম: (১) Exchange: কোনো সর্বোত্তম tree-তে সবচেয়ে বিরল দুটি চিহ্নকে সবচেয়ে গভীরে ভাই করা যায়; গভীর leaf-এর সঙ্গে জায়গা বদলালে খরচ বাড়ে না। তাই greedy-র প্রথম পছন্দ নিরাপদ। (২) জোড়া দুটিকে একটি চিহ্ন z ধরলে নতুন সমস্যার খরচ ঠিক p_x + p_y কম; এই ছোট সমস্যায় induction খাটিয়ে পুরো দাবি।

import heapq

w = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}   # order counts
heap = [(c, i, {k: ""}) for i, (k, c) in enumerate(w.items())]
heapq.heapify(heap)
i, merges = len(heap), []
while len(heap) > 1:
    c1, _, t1 = heapq.heappop(heap)
    c2, _, t2 = heapq.heappop(heap)
    merges.append(c1 + c2)
    code = {k: "0" + v for k, v in t1.items()} | {k: "1" + v for k, v in t2.items()}
    heapq.heappush(heap, (c1 + c2, i, code)); i += 1
code = heap[0][2]
L = lambda cd: sum(w[k] * len(cd[k]) for k in w)
print("lengths:", {k: len(code[k]) for k in sorted(w)})
print("cost =", L(code), "| sum of merged weights =", sum(merges), merges)
print("fixed 3-bit code cost =", 3 * sum(w.values()))

bad = dict(code); bad["a"], bad["f"] = code["f"], code["a"]   # exchange
print("swap a (common) with f (rare): cost", L(bad), "> ", L(code))

lengths: {'a': 1, 'b': 3, 'c': 3, 'd': 3, 'e': 4, 'f': 4}
cost = 224 | sum of merged weights = 224 [14, 25, 30, 55, 100]
fixed 3-bit code cost = 300
swap a (common) with f (rare): cost 344 >  224

সীমা: Huffman সর্বোত্তম কেবল “প্রতিটি চিহ্নে আলাদা codeword”-এর prefix code-এর মধ্যে; গড় দৈর্ঘ্য L-এর জন্য H ≤ L < H + 1, যেখানে H entropy. সমান ওজনে একাধিক Huffman tree হয়, খরচ একই।

পরীক্ষক যা খোঁজেন: algorithm (১); exchange lemma (২); induction-এর ধাপ (১); সীমা বা entropy (১)। পর্ব ৬৮

যেখানে নম্বর কাটে: “greedy, তাই সর্বোত্তম” লিখে থামা; ওপর থেকে ভাগ করা (Shannon–Fano ধাঁচ) Huffman বলে চালানো।

সংজ্ঞা: Group (G, ∗): একটি associative binary operation, একক উপাদান, আর প্রতিটি উপাদানের inverse. Ring (R, +, ·): (R, +) abelian group, গুণ associative আর 1 গুণের একক, দুই দিকের বণ্টন বিধি; গুণের inverse চাওয়া হয় না (এই কোর্সে 1-সহ ring; কিছু বইয়ে 1 বাধ্যতামূলক নয়)। Field: commutative ring, 1 ≠ 0, আর প্রতিটি অশূন্য উপাদানের গুণের inverse আছে।

ℤ_n: ℤ_n field ⇔ n মৌলিক। n = ab (1 < a, b < n) হলে a · b ≡ 0, অর্থাৎ a একটি zero divisor, আর zero divisor-এর inverse থাকতে পারে না। উল্টো দিকে n মৌলিক হলে gcd(a, n) = 1, তাই Bézout থেকে inverse.

from math import gcd

for n in (5, 7, 12, 15):
    units = [a for a in range(1, n) if gcd(a, n) == 1]
    zd = [a for a in range(1, n) if any(a * b % n == 0 for b in range(1, n))]
    kind = "field" if len(units) == n - 1 else "ring, not a field"
    print(f"Z_{n:<2} units {len(units):2}  zero divisors {zd}  -> {kind}")

print("inverse of 3 in Z_7:", pow(3, -1, 7))
try:
    pow(3, -1, 12)
except ValueError as err:
    print("inverse of 3 in Z_12:", err)

Z_5  units  4  zero divisors []  -> field
Z_7  units  6  zero divisors []  -> field
Z_12 units  4  zero divisors [2, 3, 4, 6, 8, 9, 10]  -> ring, not a field
Z_15 units  8  zero divisors [3, 5, 6, 9, 10, 12]  -> ring, not a field
inverse of 3 in Z_7: 5
inverse of 3 in Z_12: base is not invertible for the given modulus

প্রয়োগ ও সম্পর্ক: Lagrange (subgroup-এর order group-এর order-কে ভাগ করে) থেকে এক লাইনে Fermat আর Euler আসে। GF(2⁸) AES-এ, GF(2)-এর ওপর polynomial CRC-তে, আর finite field Reed–Solomon code-এ। সসীম integral domain মানেই field.

পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (৩); ছকের উদাহরণ আর প্রতিউদাহরণ (৩); ℤ_n-এর শর্ত আর কারণ (৩); একটি প্রয়োগ (১)। পর্ব ৭০ · পর্ব ৭১

যেখানে নম্বর কাটে: “ring-এ গুণের inverse থাকে” লেখা; (ℤ, ·)-কে group বলা; GF(4)-কে ℤ₄ ভাবা (ℤ₄ field নয়)।

aⁿbⁿ: grammar S → aSb ∣ ab এটি তৈরি করে, তাই context-free. Regular নয়, তার ধারণা pigeonhole দিয়ে: ধরুন k-state-এর DFA এটি চেনে। a¹, a², …, a^k+1 এই k + 1টি prefix-এর দুটি, aⁱ আর a^j (i ≠ j), একই state-এ পৌঁছায়। তখন aⁱbⁱ গৃহীত হলে a^jbⁱ-ও গৃহীত, যা ভাষায় নেই: বিরোধ। একই যুক্তির আনুষ্ঠানিক রূপ pumping lemma (পর্ব ৭৪)।

সীমা: প্রতিটি ধাপ কড়াভাবে বড় (⊊)। aⁿbⁿcⁿ context-free নয়, তার প্রমাণে context-free-এর pumping lemma লাগে, যা এই কোর্সে নেই; context-free language যে decidable, সেটিও পরিকল্পিত Theory of Computation কোর্সের বিষয়। ছবিতে Chomsky-র type 1 (context-sensitive) শ্রেণি আলাদা দেখানো হয়নি; সেটি context-free আর decidable-এর মাঝে পড়ে।

পরীক্ষক যা খোঁজেন: ছক (৪); aⁿbⁿ-এর grammar (১); regular না হওয়ার যুক্তি (৩); closure-এর পার্থক্য (১); প্রয়োগ (১)। পর্ব ৭৩ · পর্ব ৭৪

যেখানে নম্বর কাটে: “regular-এর subset সবসময় regular” লেখা (aⁿbⁿ ⊆ a*b*, তবু regular নয়); NFA-কে DFA-র চেয়ে বেশি শক্তিশালী বলা।

সংজ্ঞা: L recognizable, যদি এমন Turing machine M থাকে যা L-এর প্রতিটি সদস্যে একসময় গ্রহণ করে, আর বাকিদের বর্জন করে বা চিরকাল চলে। L decidable, যদি এমন M থাকে যা প্রতিটি ইনপুটে থামে আর ঠিক L গ্রহণ করে। L decidable ⇔ L আর তার complement দুটিই recognizable.

Halting problem-এর যুক্তি (Turing, ১৯৩৬): ধরুন H আছে, যা প্রতিটি ⟨M, w⟩-এ বলে M, w-তে থামে কি না। নতুন যন্ত্র D বানাই: ইনপুট ⟨M⟩ পেলে H-কে ⟨M, ⟨M⟩⟩ জিজ্ঞেস করে, আর H “থামে” বললে D চিরকাল চলে, “থামে না” বললে থামে। এখন D-কে ⟨D⟩ দিলে D থামে ⇔ D থামে না: বিরোধ। এটি Cantor-এর diagonal-এরই রূপ। HALT নিজে recognizable (যন্ত্রটি চালিয়ে দেখি), তাই তার complement recognizable নয়।

Rice: যন্ত্রের language-এর যেকোনো অতুচ্ছ ধর্ম undecidable: “L(M) ফাঁকা কি না”, “M কোনো ইনপুটে hello ছাপে কি না”। কিন্তু কোডের চেহারার প্রশ্ন (“M-এ ১০টির বেশি state আছে কি?”) decidable. তাই বাস্তবের static analyzer অনুমান করে: কিছু bug ছাড়ে বা ভুয়া সতর্কতা দেয়।

সীমা: Church–Turing thesis একটি thesis, উপপাদ্য নয়: “কার্যকর হিসাব” অনানুষ্ঠানিক ধারণা, তাই প্রমাণ হয় না; পক্ষে প্রমাণ হলো বিভিন্ন মডেলের সমতুল্যতা।

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা আর complement-এর সম্পর্ক (৩); diagonal যুক্তি (৩); Rice আর তার শর্ত (২); NP-complete বনাম undecidable (২)। পর্ব ৭৫ · পর্ব ৭৭

যেখানে নম্বর কাটে: “halting problem কঠিন কিন্তু বেশি সময় দিলে মেলে” লেখা; Rice-কে কোডের চেহারার প্রশ্নে খাটানো; recognizable আর decidable এক ভাবা।

Tautology সব assignment-এ সত্য, contradiction কোনোটিতেই নয়, satisfiable অন্তত একটিতে সত্য। φ tautology ⇔ ¬φ unsatisfiable. পর্ব ০৩

পরের প্রশ্ন: satisfiability যাচাই কত কঠিন? — SAT NP-complete (Cook–Levin, ১৯৭১); কিন্তু 2-SAT polynomial সময়ে মেলে।

Implication একটি প্রতিশ্রুতি: শুধু p সত্য আর q মিথ্যা হলে তা ভাঙে। p মিথ্যা হলে প্রতিশ্রুতি পরীক্ষাই হয়নি; একে vacuous truth বলে। পর্ব ০২

পরের প্রশ্ন: “খালি সেটের সব উপাদান লাল” সত্য না মিথ্যা? — সত্য; মিথ্যা হতে হলে একটি অ-লাল উপাদান লাগত।

∃x ∀y ¬P(x, y): প্রতিটি quantifier উল্টে যায়, নেগেশন ভেতরে ঢোকে। পর্ব ০৫

পরের প্রশ্ন: limit-এর ε–δ সংজ্ঞার নেগেশনে এটি কোথায় লাগে? — “একটি ε আছে, যার জন্য কোনো δ খাটে না”, ঠিক এই নিয়মেই।

শুরুতে সত্য, প্রতিটি পুনরাবৃত্তিতে টিকে থাকে, আর loop শেষে invariant ∧ থামার শর্ত থেকে postcondition. এতে partial correctness; loop থামার প্রমাণ (variant) যোগ করলে total. পর্ব ১৩

পরের প্রশ্ন: থামা কীভাবে দেখাবেন? — একটি অঋণাত্মক পূর্ণসংখ্যার মান প্রতি পুনরাবৃত্তিতে কড়াভাবে কমে; well-ordering-এ অসীম কমা অসম্ভব।

ঠিক bijection-এর (one-to-one আর onto দুটিই)। পর্ব ১৬

পরের প্রশ্ন: সমান আকারের সসীম সেটে one-to-one হলেই কি onto? — হ্যাঁ, pigeonhole থেকে; অসীমে নয়, যেমন ℕ-এ n ↦ 2n.

প্রতি দুই ধাপে বড় সংখ্যাটি অর্ধেকের নিচে নামে, তাই ধাপ লগারিদমিক; Lamé-এর (১৮৪৪) সীমা: ধাপ ছোট সংখ্যার দশমিক অঙ্ক-সংখ্যার পাঁচগুণের বেশি নয়, সবচেয়ে খারাপ পরপর দুটি Fibonacci সংখ্যায়। পর্ব ২১

পরের প্রশ্ন: extended Euclid কী দেয়? — Bézout-এর x, y (ax + by = gcd); gcd = 1 হলে x-ই a-এর modular inverse.

Modulus-গুলো জোড়ায় জোড়ায় সহমৌলিক হলে, তাদের গুণফলের mod-এ ঠিক একটি সমাধান। পর্ব ২৩

পরের প্রশ্ন: সহমৌলিক না হলে? — সমাধান থাকতেও পারে, না-ও; x ≡ a (mod m), x ≡ b (mod n)-এ শর্ত gcd(m, n) ∣ a − b, আর তখন অনন্য lcm(m, n)-এর mod-এ।

Authentication: মাঝখানে বসা আক্রমণকারী (man-in-the-middle) দুই পক্ষের সঙ্গে আলাদা key বানাতে পারেন; তাই সই বা certificate লাগে। পর্ব ২৯

পরের প্রশ্ন: নিরাপত্তা কিসের ওপর? — discrete log আর computational Diffie–Hellman-এর কঠিনতার অনুমান, ঠিকমতো বাছা group-এ।

N টি জিনিস k টি বাক্সে রাখলে কোনো বাক্সে অন্তত ⌈N/k⌉টি। পর্ব ৩২

পরের প্রশ্ন: কত জন হলে দুজনের জন্মদিন নিশ্চিতভাবে এক? — ৩৬৭ জন (৩৬৬টি সম্ভাব্য তারিখ); ২৩ জনের কথাটি সম্ভাবনার, নিশ্চয়তার নয়।

৩৬৫টি সমসম্ভব দিনে ২৩ জনের মধ্যে অন্তত একটি মিলের সম্ভাবনা প্রায় ০.৫০৭. b বিটের hash-এ collision আশা করা যায় প্রায় 2^b/2টি ইনপুটে, 2^b-এ নয় (birthday bound). পর্ব ৪২

পরের প্রশ্ন: ছোট অর্ডার-ID-তে এর প্রভাব? — এলোমেলো ID-র দৈর্ঘ্য এমন রাখতে হয় যাতে প্রত্যাশিত অর্ডার-সংখ্যা 2^b/2-এর অনেক নিচে থাকে।

k জনকে বাছা মানেই বাকি n − k জনকে বাদ রাখা: দুই বাছাইয়ের মধ্যে bijection. পর্ব ৩৪

পরের প্রশ্ন: Pascal-এর অভেদ গণনায়? — একটি নির্দিষ্ট মানুষ দলে আছেন (C(n − 1, k − 1)) বা নেই (C(n − 1, k)).

Markov: X ≥ 0 আর a > 0, P(X ≥ a) ≤ E[X]/a. Chebyshev: variance সসীম, P(|X − μ| ≥ kσ) ≤ 1/k². পর্ব ৪১

পরের প্রশ্ন: Chernoff কখন অনেক ভালো? — স্বাধীন Bernoulli-র যোগফলে; লেজ exponential হারে ছোট হয়।

n জোড়া balanced বন্ধনী, n টি internal node-এর binary tree, (n + 2)-ভুজের triangulation, Dyck path: সবই C_n = C(2n, n)/(n + 1); 1, 1, 2, 5, 14, 42, … পর্ব ৫০

পরের প্রশ্ন: recurrence? — C_n+1 = ∑_i=0ⁿ C_iC_n−i: প্রথম বন্ধনী কোথায় বন্ধ হয়, তা ধরে ভাগ।

উপসমস্যা অসমান হলে, বিয়োগে ছোট হলে (T(n − 1) + n), বা চালিকা-খরচ n^d-এর মতো নয় হলে (n log n, n/log n). পর্ব ৪৭

পরের প্রশ্ন: তখন কী করবেন? — Recursion tree, substitution দিয়ে প্রমাণ, বা Akra–Bazzi.

Ordinary (∑a_nxⁿ) ক্রমহীন বাছাই আর combination-এ; exponential (∑a_nxⁿ/n!) লেবেলযুক্ত সাজানো আর permutation-এ, কারণ গুণফলে C(n, k) আপনা-আপনি আসে। পর্ব ৪৮

পরের প্রশ্ন: দুই sequence-এর convolution generating function-এ কী? — দুই series-এর গুণফল।

আলাদা রূপের (orbit) সংখ্যা = group-এর উপাদানগুলোর স্থির বিন্দুর গড়। ২ রঙে ৪ পুঁতির মালা, শুধু ঘোরানো: (16 + 2 + 4 + 2)/4 = 6. পর্ব ৫১

পরের প্রশ্ন: উল্টানোও চললে? — dihedral group নিতে হয়; সংখ্যা কমতে বা একই থাকতে পারে, কখনো বাড়ে না।

∑deg(v) = 2e, তাই বিজোড় degree-এর vertex জোড় সংখ্যক (handshake lemma). পর্ব ৫৭

পরের প্রশ্ন: ৫ জনের প্রত্যেকে ঠিক ৩ জনের সঙ্গে হাত মেলাতে পারেন? — না; 5 · 3 = 15 বিজোড়, অথচ degree-যোগফল জোড় হতে হয়।

ঠিক তখন, যখন কোনো বিজোড় দৈর্ঘ্যের cycle নেই; অর্থাৎ ২ রঙে রং করা যায়, BFS-এর স্তর দিয়ে যাচাই। পর্ব ৬৩ · পর্ব ৬৪

পরের প্রশ্ন: Hall-এর শর্ত? — X-এর প্রতিটি subset S-এ |N(S)| ≥ |S| হলেই X-কে পুরো ঢাকা matching আছে।

Connected আর acyclic; n টি vertex, n − 1টি edge আর connected; যেকোনো দুই vertex-এর মধ্যে ঠিক একটি simple path. পর্ব ৬৫

পরের প্রশ্ন: n টি লেবেলযুক্ত vertex-এ কয়টি tree? — Cayley: nⁿ⁻²; প্রমাণের একটি পথ Prüfer sequence.

প্রমাণের মূল দাবি: settled vertex-এর দূরত্ব আর কমবে না। ঋণাত্মক edge থাকলে পরে আরও ছোট পথ আসতে পারে। পর্ব ৬১

পরের প্রশ্ন: তাহলে কী? — Bellman–Ford; আর ঋণাত্মক cycle থাকলে সবচেয়ে ছোট পথই সংজ্ঞায়িত নয়।

সসীম group-এ subgroup-এর order group-এর order-কে ভাগ করে; তাই প্রতিটি উপাদানের order-ও। ফল: a^|G| = e, যা ℤ_n-এর unit-group-এ Euler-এর উপপাদ্য। পর্ব ৭০

পরের প্রশ্ন: ১৫ উপাদানের group-এ ৪ উপাদানের subgroup সম্ভব? — না; 4 ∤ 15.

d − 1টি পর্যন্ত ধরে, ⌊(d − 1)/2⌋টি পর্যন্ত শোধরায় (minimum distance). Hamming(7,4)-এ d = 3: ২টি ধরা বা ১টি শোধরানো। পর্ব ৭২

পরের প্রশ্ন: একসঙ্গে ১টি শোধরানো আর ২টি ধরা? — একটি parity বিট যোগ করে d = 4: SECDED.

না; subset construction প্রতিটি NFA-কে সমান ভাষার DFA বানায়। তবে state-সংখ্যা 2ⁿ পর্যন্ত বাড়তে পারে, আর কিছু ভাষায় তা এড়ানো যায় না। পর্ব ৭৪

পরের প্রশ্ন: regular expression কোন শ্রেণি বর্ণনা করে? — ঠিক regular language (Kleene-এর উপপাদ্য)।

2-literal-এর clause (a ∨ b) দুটি implication ¬a → b, ¬b → a; implication graph-এ কোনো x আর ¬x একই SCC-তে থাকলে unsatisfiable, নইলে satisfiable: polynomial সময়। 3-SAT NP-complete. পর্ব ৭৭

পরের প্রশ্ন: NP-complete মানে কি অসমাধ্য? — না; algorithm আছে, শুধু worst case-এ দ্রুত কোনোটি জানা নেই; halting-এর মতো undecidable নয়।