Numerical সমস্যার অনুশীলন — discrete math-এর হিসাব, পূর্ণ সমাধানসহ

(a) ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q)      De Morgan
                    ≡ ¬p ∧ (p ∨ ¬q)       De Morgan + double negation
                    ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) distributive
                    ≡ F ∨ (¬p ∧ ¬q) ≡ ¬p ∧ ¬q
(b) the only way to make "X → Y" false: X true, Y false.
    Y = p → r false needs p = T, r = F. Then X needs p → q (so q = T)
    and q → r (so q = F): impossible. All 8 rows T -> tautology.
(c) true when an odd number of p, q, r are T: 100, 010, 001, 111 -> 4 minterms

(খ)-তে ৮টি সারি না লিখে “কখন মিথ্যা হতে পারে” খোঁজাই দ্রুত পথ; একে hypothetical syllogism বলে। পরীক্ষায় table চাইলে ৮টি সারিই লিখুন, তবে এই যুক্তি দিয়ে উত্তর মিলিয়ে নিন।

(a) TRUE : for each x choose y = 7 - x, which is in D
(b) FALSE: one fixed y must work for all x; x = 1 needs y = 6, x = 2 needs y = 5
(c) FALSE: x = 6 has no larger y in D
(d) ¬∀x ∃y (x < y) ≡ ∃x ∀y ¬(x < y) ≡ ∃x ∀y (x ≥ y) ; witness x = 6

(ক) আর (খ)-তে শুধু quantifier-এর ক্রম আলাদা, অথচ সত্যমান উল্টো। ∀x ∃y-তে y নির্ভর করতে পারে x-এর ওপর; ∃y ∀x-এ একটিই y সবার জন্য। আর (গ) ℕ-এ সত্য হতো; domain বদলালেই উত্তর বদলায়, তাই domain সবসময় লিখে নিন।

Basis n = 1 : LHS = 1·2 = 2 ; RHS = 1·2·3/3 = 2
Hypothesis  : sum up to k = k(k+1)(k+2)/3
Step        : sum up to k+1 = k(k+1)(k+2)/3 + (k+1)(k+2)
                            = (k+1)(k+2)(k/3 + 1)
                            = (k+1)(k+2)(k+3)/3      -> the claim for k+1  ∎
n = 10      : 10·11·12/3 = 440

Inductive step-এ মূল চাল হলো সাধারণ উৎপাদক (k + 1)(k + 2) বের করা। n = 10-এর উত্তর ২ + ৬ + ১২ + … + ১১০ সরাসরি যোগ করেও ৪৪০ আসে; চেকার n = 1 থেকে 50 পর্যন্ত সূত্রটি মিলিয়েছে, তবে মনে রাখবেন, ৫০টি ক্ষেত্র মেলানো প্রমাণ নয়, প্রমাণ হলো ওপরের induction.

(a) 4^3 = 64
(b) 4 · 3 · 2 = 24
(c) 0 : 3 inputs cannot cover 4 outputs (pigeonhole in reverse)
(d) 3! · S(4, 3) = 6 · 6 = 36
    or inclusion-exclusion: 3^4 - 3·2^4 + 3·1^4 = 81 - 48 + 3 = 36
(e) subsets of A × A : 2^(3·3) = 2^9 = 512

(ঘ)-র দুটি পথ একে অপরের যাচাই। S(4, 3) = 6 মানে চারটি জিনিসকে তিনটি অশূন্য দলে ভাগের উপায় (দুটি একসঙ্গে, বাকি দুটি একা: C(4, 2) = 6); তারপর তিন দলকে A-এর তিন সদস্যে বসানো 3!.

(a) (2+3)(2+3+1)/2 + 3 = 15 + 3 = 18
(b) find the diagonal d = x + y with T(d) = d(d+1)/2 <= 25 < T(d+1):
    T(6) = 21, T(7) = 28 -> d = 6 ; y = 25 - 21 = 4 ; x = 6 - 4 = 2 -> (2, 4)
(c) length 0: 1 string, length 1: 2, length 2: 4 -> 7 strings before length 3
    among length 3, "101" is binary 5 -> position 7 + 5 = 12
(d) diagonal bits: s0[0]=0, s1[1]=0, s2[2]=0, s3[3]=0 -> flip -> 1111…

(গ) এই তালিকা দেখায় যে finite string-এর সেট countable: প্রতিটি string একটি নির্দিষ্ট স্থানে আসে। (ঘ)-র sequence প্রতিটি s_i-এর সঙ্গে অন্তত i-তম বিটে আলাদা, তাই তালিকায় নেই; অসীম sequence-এর সেট uncountable হওয়ার যুক্তি এটিই।

(a) rows: 1: 0100 ; 2: 0010 ; 3: 1001 ; 4: 1000
(b) A^2 rows: 0010 ; 1001 ; 1100 ; 0100
    A^3 rows: 1001 ; 1100 ; 0110 ; 0010
    (A^3)[1][1] = 1 : the walk 1 -> 2 -> 3 -> 1
(c) A ∨ A^[2] ∨ A^[3] ∨ A^[4] = all ones (every hub reaches every hub)

সব ঘর ১, কারণ 1 → 2 → 3 → 1 একটি cycle আর 4 থেকে 1-এ ফেরা যায়: graph-টি strongly connected. n = 4 vertex-এ closure-এর জন্য A^[4] পর্যন্ত Boolean ঘাত যথেষ্ট, কারণ cycle ছাড়া কোনো path-এ ৪টির বেশি edge থাকে না।

1147 = 1·851 + 296
 851 = 2·296 + 259
 296 = 1·259 + 37
 259 = 7·37  + 0          -> gcd = 37
37 = 296 - 259
   = 296 - (851 - 2·296) = 3·296 - 851
   = 3·(1147 - 851) - 851 = 3·1147 - 4·851   -> x = 3, y = -4
check: 3441 - 3404 = 37 ; lcm = 1147·851/37 = 26381

নিচের stepper একই হিসাব ধাপে ধাপে দেখায়। Back-substitution-এ প্রতিবার শুধু ভাগশেষকে আগের লাইনের রূপে বদলান; চিহ্নের ভুল এড়াতে শেষে গুণ করে যাচাই বাধ্যতামূলক ভাবুন।

(a) 43 = 2·17 + 9 ; 17 = 1·9 + 8 ; 9 = 1·8 + 1
    1 = 9 - 8 = 9 - (17 - 9) = 2·9 - 17 = 2·(43 - 2·17) - 17 = 2·43 - 5·17
    -> 17^-1 ≡ -5 ≡ 38 (mod 43) ; check 17·38 = 646 = 15·43 + 1
(b) x ≡ 38·5 = 190 ≡ 190 - 4·43 = 18 (mod 43)
(c) g = gcd(6, 15) = 3, and 3 | 9 -> exactly 3 solutions mod 15
    divide by 3: 2x ≡ 3 (mod 5) ; 2^-1 = 3 -> x ≡ 9 ≡ 4 (mod 5)
    solutions mod 15: 4, 9, 14

(গ)-তে ৩ দিয়ে ভাগ না করে সরাসরি 6⁻¹ mod 15 খোঁজা ভুল: gcd(6, 15) = 3 ≠ 1, তাই সেই inverse নেই। যাচাই: 6 · 4 = 24 ≡ 9, 6 · 9 = 54 ≡ 9, 6 · 14 = 84 ≡ 9 (mod 15).

x ≡ 1 (mod 4), x ≡ 2 (mod 5), x ≡ 3 (mod 7) ; 4, 5, 7 pairwise coprime ; M = 140
M1 = 35, 35 ≡ 3 (mod 4), inverse y1 = 3   (3·3 = 9 ≡ 1)
M2 = 28, 28 ≡ 3 (mod 5), inverse y2 = 2   (3·2 = 6 ≡ 1)
M3 = 20, 20 ≡ 6 (mod 7), inverse y3 = 6   (6·6 = 36 ≡ 1)
x = 1·35·3 + 2·28·2 + 3·20·6 = 105 + 112 + 360 = 577 ≡ 577 - 4·140 = 17 (mod 140)
check: 17 = 4·4 + 1 = 3·5 + 2 = 2·7 + 3

CRT বলে mod 140-এ উত্তর অনন্য, তাই ১৪০-এর কম একটিই সংখ্যা: ১৭টি বাক্স। Modulus-গুলো জোড়ায় জোড়ায় coprime না হলে (যেমন 4 আর 6) এই সূত্র সরাসরি খাটে না।

(a) 117 = 64 + 32 + 16 + 4 + 1 = 1110101 (binary)
    5^1 = 5, 5^2 = 6, 5^4 = 17, 5^8 = 4, 5^16 = 16, 5^32 = 9, 5^64 = 5   (mod 19)
    5^117 = 5^64 · 5^32 · 5^16 · 5^4 · 5^1 = 5·9·16·17·5
          : 5·9 = 45 ≡ 7 ; 7·16 = 112 ≡ 17 ; 17·17 = 289 ≡ 4 ; 4·5 = 20 ≡ 1
(b) 19 prime, 19 ∤ 5 -> 5^18 ≡ 1 ; 117 = 6·18 + 9 -> 5^117 ≡ 5^9 = 5^8·5 = 4·5 = 20 ≡ 1
(c) order divides 18 ; 5^1, 5^2 = 6, 5^3 = 11, 5^6 = 7 are not 1 ; 5^9 ≡ 1 -> order 9

৬টি বর্গ (5⁶⁴ পর্যন্ত) আর ৪টি গুণ, মোট ১০টি গুণে কাজ শেষ; সরাসরি ১১৬টি গুণ লাগত। (গ)-তে Lagrange-এর ফল কাজে লাগে: order অবশ্যই 18-এর ভাজক, তাই 1, 2, 3, 6, 9, 18 ছাড়া কিছু দেখার দরকার নেই।

(a) 360 = 2^3·3^2·5 -> φ = 360·(1/2)(2/3)(4/5) = 96
(b) gcd(7, 360) = 1 ; 962 = 10·96 + 2 -> 7^962 ≡ 7^2 = 49 (mod 360)
(c) φ(100) = 40 ; 2026 = 50·40 + 26 -> 3^26 mod 100
    3^5 = 243 ≡ 43 ; 3^10 ≡ 43^2 = 1849 ≡ 49 ; 3^20 ≡ 49^2 = 2401 ≡ 1
    3^26 = 3^20·3^5·3 ≡ 1·43·3 = 129 ≡ 29 -> last two digits 29
(d) No. Fermat: p prime => a^(p-1) ≡ 1. The converse is false.
    341 is a Fermat pseudoprime to base 2.

(গ)-তে মজার ব্যাপার: 3²⁰ ≡ 1 (mod 100), অর্থাৎ 3-এর order এখানে 20, φ(100) = 40-এর চেয়ে ছোট। Euler-এর উপপাদ্য একটি ঘাত দেয় যা কাজ করে; সবচেয়ে ছোটটি নয়।

340 = 2^2 · 85 -> s = 2, d = 85
2^85 mod 341 = 32           (not 1, not 340 = -1)
2^170 = 32^2 = 1024 = 3·341 + 1 ≡ 1
-> 32 is a square root of 1 other than ±1 -> 341 is COMPOSITE, 2 is a witness
bonus: 32^2 ≡ 1 -> 341 | (32-1)(32+1) -> gcd(31, 341) = 31, and 341 = 31 · 11

৩.৫-এর Fermat পরীক্ষা base 2-এ 341-কে ধরতে পারেনি, Miller–Rabin একই base-এ ধরল, কারণ সে শুধু শেষ ঘাত নয়, ১-এ পৌঁছানোর পথটিও দেখে। মৌলিক modulus-এ ১-এর বর্গমূল শুধু ±1; অন্য বর্গমূল মানেই witness.

(a) n = 247 ; φ = 12·18 = 216 ; gcd(5, 216) = 1
    216 = 43·5 + 1 -> 1 = 216 - 43·5 -> d ≡ -43 ≡ 173 ; check 5·173 = 865 = 4·216 + 1
(b) 42^2 = 1764 ≡ 1764 - 7·247 = 35
    42^4 ≡ 35^2 = 1225 ≡ 1225 - 4·247 = 237 ≡ -10
    42^5 ≡ -10·42 = -420 ≡ -420 + 2·247 = 74     -> c = 74
(c) 74^173 mod 247 = 42 (square-and-multiply; 173 = 10101101 in binary)

(খ)-তে −10 লেখার কৌশল লক্ষ করুন: 237 ≡ −10 (mod 247) ধরলে পরের গুণ ছোট থাকে। (গ)-র হাতের হিসাব লম্বা; পরীক্ষায় CRT দিয়ে mod 13 আর mod 19-এ আলাদা করলে দ্রুত হয়: 74 ≡ 9 (mod 13), 9^{173 mod 12} = 9⁵ ≡ 3, আর 42 ≡ 3 (mod 13) মেলে।

(a) order divides 28 = 2^2·7 ; test 28/2 = 14 and 28/7 = 4:
    2^4 = 16 ≠ 1 ; 2^7 = 128 ≡ 12 ; 2^14 ≡ 144 ≡ 28 ≡ -1 ≠ 1 -> order 28: primitive root
(b) A = 2^6 = 64 ≡ 6 ; B = 2^11 = 2048 ≡ 2048 - 70·29 = 18
    Rafi: 18^6 mod 29 = 9 ; Tania: 6^11 mod 29 = 9 -> key 9
(c) try x = 0, 1, 2, … : 2^17 ≡ 21 (mod 29) -> a = 17

(গ) ছোট p-তে discrete log সহজ, কারণ মাত্র ২৮টি ঘাত দেখতে হয়। বাস্তবের p হাজার bit লম্বা হলে সাধারণ brute force অসম্ভব; আর DH নিজে প্রমাণীকরণ দেয় না, তাই man-in-the-middle ঠেকাতে আলাদা ব্যবস্থা লাগে।

(a) B=1 -> 10=K ; A=0 -> 3=D ; Z=25 -> 178 ≡ 22=W ; A -> D ; R=17 -> 122 ≡ 18=S
    BAZAR -> KDWDS
(b) 7·15 = 105 = 4·26 + 1 -> 7^-1 = 15 ; D(y) = 15(y - 3) mod 26
    K=10: 15·7 = 105 ≡ 1 = B  (one check)
(c) a with gcd(a, 26) = 1: 12 choices (odd, not 13) ; b: 26 -> 12·26 = 312

দুটি A একই D হয়ে যাওয়াই affine cipher-এর দুর্বলতা: অক্ষরের ঘনত্ব (frequency) অপরিবর্তিত থাকে, আর মাত্র ৩১২টি key-তে brute force এক মুহূর্তের কাজ।

key shifts  D=3 H=7 A=0 K=10 A=0 | D=3 H=7 A=0 K=10
plaintext   B   A   Z   A    R   | G   H   A   R
            1   0   25  0    17  | 6   7   0   17
+ shift     4   7   25  10   17  | 9   14  0   27≡1
ciphertext  E   H   Z   K    R   | J   O   A   B      -> EHZKRJOAB

প্লেইনটেক্সটের তিনটি A হয়েছে H, K আর A, কারণ তারা key-এর ভিন্ন অবস্থানে পড়েছে। তাই সরল frequency analysis কাজ করে না; তবে key-এর দৈর্ঘ্য (এখানে ৫) জানা গেলে প্রতিটি ৫ম অক্ষর একটি shift cipher, আর আক্রমণ আবার সহজ।

(a) all - no digit = 36^6 - 26^6 = 2176782336 - 308915776 = 1867866560
(b) first digit 9 ways (1-9), then 9, 8, 7 -> 9·9·8·7 = 4536

(ক)-তে “অন্তত একটি অঙ্কের ঘর বেছে, বাকি ৫টি যেকোনো” (6 · 10 · 36⁵) লিখলে একাধিক অঙ্কের password বারবার গোনা হয়; complement-ই নিরাপদ পথ। (খ)-তে বাধাওয়ালা ঘর (প্রথম অঙ্ক) আগে ভরুন।

(a) boxes {1,8} {2,7} {3,6} {4,5} : 4 boxes, 5 numbers -> one box gets 2 -> sum 9
    with 4 numbers {1,2,3,4} no pair sums to 9
(b) ⌈100/7⌉ = 15
(c) 2 per month is possible with 24 people ; 2·12 + 1 = 25

Pigeonhole-এ আসল কাজ বাক্স বানানো: এখানে যোগফল 9-এর জোড়াই বাক্স। (গ)-তে উত্তর ২৫ “ন্যূনতম” হওয়ার প্রমাণে দুটি অংশ লাগে: ২৫-এ নিশ্চয়তা, আর ২৪ জনের এমন উদাহরণ যেখানে প্রতি মাসে ঠিক দুজন।

(a) term C(8,3)(2x)^3(-y)^5 -> 56 · 8 · (-1) = -448
(b) 10 steps, choose which 4 are "up": C(10, 4) = 210
(c) (0,0)->(3,2): C(5,2) = 10 ; (3,2)->(6,4): C(5,2) = 10 -> 10·10 = 100

(ক)-তে সবচেয়ে সাধারণ ভুল 2³ আর (−1)⁵ ভুলে যাওয়া; উত্তর ৫৬ নয়। (গ) গুণের নিয়ম: দুই অংশের পথ স্বাধীনভাবে বাছা যায়।

(a) C(15 + 3, 3) = C(18, 3) = 816
(b) give 2 and 1 first: 12 left -> C(15, 3) = 455
(c) inclusion-exclusion on "x_i >= 7":
    816 - C(4,1)·C(11,3) + C(4,2)·C(4,3) = 816 - 4·165 + 6·4 = 816 - 660 + 24 = 180
    (three branches with >= 7 need 21 > 15 coupons: 0)

(গ)-তে x₁ ≥ 7 হলে আগে ৭টি দিয়ে বাকি ৮টি ভাগ: C(11, 3) = 165. দুটি শাখা ≥ 7 হলে বাকি ১টি: C(4, 3) = 4. চেকার 16⁴টি tuple গুনে তিনটি উত্তরই মেলায়।

P(flag | fraud) P(fraud) = 0.95 · 0.02 = 0.0190
P(flag | honest) P(honest) = 0.04 · 0.98 = 0.0392
P(flag) = 0.0582
P(fraud | flag) = 0.0190 / 0.0582 = 95/291 ≈ 0.3265
natural frequencies, per 10,000 orders: 200 fraud -> 190 flagged ; 9800 honest -> 392 flagged
-> 190 of 582 flagged orders are fraud

৯৫% নির্ভুল ব্যবস্থা, অথচ দাগানো অর্ডারের মাত্র এক-তৃতীয়াংশ প্রতারণা। কারণ base rate মাত্র ২%; সৎ অর্ডার এত বেশি যে ৪% ভুলও সংখ্যায় বড়। ১০,০০০টি অর্ডারের গণনায় ভাবলে ফাঁদটি চোখে পড়ে।

(a) E = 21/6 = 7/2 ; E[X^2] = 91/6 ; Var = 91/6 - 49/4 = 35/12 ≈ 2.9167
(b) independent -> variances add: 35/12 + 35/12 = 35/6
(c) E = np = 3 ; Var = np(1 - p) = 2.1
(d) indicator for each pair: C(30,2) pairs, each P = 1/365
    E = 435/365 = 87/73 ≈ 1.1918

(ঘ)-তে linearity of expectation-এর শক্তি: জোড়াগুলো স্বাধীন নয়, তবু প্রত্যাশা যোগ হয়। Variance-এ একই কাজ চলে না; (খ)-তে যোগ করা গেছে শুধু স্বাধীনতার জন্য।

(a) P(no match, k people) = (365/365)(364/365)…((365-k+1)/365)
    k = 23: 1 - 0.4927 = 0.5073 ; k = 22: 0.4757
(b) smallest k with 1 - ∏(1 - i/N) >= 0.5 : k = 302
    approximation k ≈ sqrt(2 N ln 2) ≈ 1.1774 · sqrt(N) = 1.1774 · 256 ≈ 301.4

N-এর বর্গমূলের কাছেই collision: ৬৫ হাজার মানের hash-এ মাত্র ৩০২টি key. তাই ১৬ bit-এর hash পরিচয় হিসেবে দুর্বল, আর cryptographic hash-এর output অনেক লম্বা রাখা হয়।

(a) r^2 - 5r + 6 = 0 -> r = 2, 3 ; a_n = A·2^n + B·3^n
    A + B = 1 ; 2A + 3B = 4 -> B = 2, A = -1 -> a_n = 2·3^n - 2^n
    check a_2 = 18 - 4 = 14 = 5·4 - 6·1
(b) r^2 - 4r + 4 = 0 -> r = 2 (double) ; a_n = (A + Bn)·2^n
    A = 1 ; 2(1 + B) = 6 -> B = 2 -> a_n = (1 + 2n)·2^n
    check a_2 = 5·4 = 20 = 4·6 - 4·1

দ্বিগুণ root-এ (A + Bn) না লিখে শুধু A · 2ⁿ লিখলে দুটি প্রাথমিক শর্ত একসঙ্গে মেলানো যায় না; এটিই সংকেত যে n-এর গুণক লাগবে।

(a) homogeneous: A·3^n ; try p_n = C·2^n:
    C·2^n = 3C·2^(n-1) + 2^n -> C = 3C/2 + 1 -> C = -2
    a_n = A·3^n - 2^(n+1) ; a_0: A - 2 = 1 -> A = 3 -> a_n = 3^(n+1) - 2^(n+1)
    check a_1 = 9 - 4 = 5 = 3·1 + 2
(b) 2 is a root of r - 2 = 0 -> try p_n = C·n·2^n:
    Cn·2^n = 2C(n-1)·2^(n-1) + 2^n -> Cn = C(n-1) + 1 -> C = 1
    a_n = A·2^n + n·2^n ; A = 1 -> a_n = (n + 1)·2^n

(খ)-তে C · 2ⁿ বসালে C = C + 1 আসে, যা অসম্ভব। Forcing term-এর ভিত্তি characteristic root হলে n দিয়ে গুণ করতে হয়; একে resonance বলে।

(a) log2 4 = 2 > d = 1 -> Θ(n^2)
(b) log2 2 = 1 = d     -> Θ(n log n)
(c) log4 3 ≈ 0.792 < 1 -> Θ(n)
(d) log2 7 ≈ 2.807 > 2 -> Θ(n^2.807)   (Strassen-type)
(e) f(n) = n log n is not Θ(n^d) ; recursion tree: each level n log(n/2^j) -> Θ(n log^2 n)

তিন case মনে রাখার সহজ ছবি: q = a/b^d > 1 হলে পাতা-ভারী গাছ, q = 1 সুষম, q < 1 মূল-ভারী। (ঙ)-র উত্তর পর্ব ৪৭-এ recursion tree দিয়ে পাওয়া।

(a) G(x) = 1/((1-x)(1-x^2)(1-x^5)) ; need [x^10]
    no 5-taka coin : 10 left, twos = 0..5 (ones fill the rest) -> 6
    one 5-taka coin: 5 left,  twos = 0..2                     -> 3
    two 5-taka coins: 0 left                                  -> 1
    total 6 + 3 + 1 = 10
(b) 1/(1-x)^3 = ∑ C(n + 2, 2) x^n -> C(7, 2) = 21

(ক)-তে সহগ বের করা মানে আসলে পাঁচ টাকার মুদ্রার সংখ্যা ধরে ভাগ করে গোনা; generating function এই গোনাকে গুণফলের সহগে রূপ দেয়। (খ) ঠিক ৫.৪-এর stars and bars: তিন চলকের যোগফল ৫.

(a) |A2| = 500, |A3| = 333, |A5| = 200
    |A2∩A3| = 166, |A2∩A5| = 100, |A3∩A5| = 66, |A2∩A3∩A5| = 33
    |union| = 1033 - 332 + 33 = 734 -> 1000 - 734 = 266
(b) D_5 = 5!(1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 60 - 20 + 5 - 1 = 44
    or D_n = (n-1)(D_(n-1) + D_(n-2)): D_3 = 2, D_4 = 9, D_5 = 4·(9 + 2) = 44
    P = 44/120 ≈ 0.3667   (close to 1/e ≈ 0.3679)

(ক)-তে ⌊1000/6⌋ = 166, ⌊1000/15⌋ = 66, ⌊1000/30⌋ = 33: floor না নিলে ভগ্নাংশ এসে উত্তর ভুল হয়। (খ)-র দুই পথের মিল একটি ভালো যাচাই।

(a) S(n,k) = k·S(n-1,k) + S(n-1,k-1)
    S(5,2) = 2^4 - 1 = 15 ; S(5,3) = 3·S(4,3) + S(4,2) = 3·6 + 7 = 25
    B5 = S(5,1..5) = 1 + 15 + 25 + 10 + 1 = 52
(b) C5 = C(10,5)/6 = 252/6 = 42
(c) p(7) = 15 ; distinct parts: 7, 6+1, 5+2, 4+3, 4+2+1 -> 5
    (Euler: equals partitions into odd parts: 7, 5+1+1, 3+3+1, 3+1+1+1+1, 1×7 -> 5)

S(5, 2) = 2⁴ − 1-এর যুক্তি: প্রথম জন যে দলে, বাকি চারজন প্রত্যেকে “সঙ্গে” বা “অন্য দলে”; সবাই সঙ্গে থাকলে দ্বিতীয় দল খালি, তাই বাদ।

(a) rotation by r positions fixes k^gcd(r, 6) colourings (k = 2):
    r = 0: 2^6 = 64 ; r = 1, 5: 2^1 = 2 each ; r = 2, 4: 2^2 = 4 each ; r = 3: 2^3 = 8
    (64 + 2 + 4 + 8 + 4 + 2)/6 = 84/6 = 14
(b) (3^4 + 3^1 + 3^2 + 3^1)/4 = (81 + 3 + 9 + 3)/4 = 96/4 = 24

২^৬/৬ ভগ্নাংশ (১০.৬৭) দেয়, তাই সরল ভাগ ভুল: যে মালা ঘোরালে বদলায় না (যেমন সব লাল), তার শ্রেণি ছোট। Burnside-এর গড় সবসময় পূর্ণসংখ্যা আসে, আর তা না এলে হিসাবে ভুল আছে।

reflexive     : YES, (1,1) (2,2) (3,3) (4,4) all present
symmetric     : NO , (3,4) in R but (4,3) not
antisymmetric : NO , (1,2) and (2,1) with 1 ≠ 2
transitive    : YES, every chain checked: (1,2)(2,1)->(1,1) ok, (2,1)(1,2)->(2,2) ok,
                (3,4)(4,4)->(3,4) ok, (3,3)(3,4)->(3,4) ok, ...
antisymmetric relations on 4 elements: 2^4 · 3^6 = 16 · 729 = 11664

Symmetric নয় আর antisymmetric-ও নয়, দুটি একসঙ্গে হতে পারে: দুটি ধর্ম একে অপরের উল্টো নয়। শেষ গণনায় ৪টি diagonal ঘর স্বাধীন (2⁴), আর প্রতিটি অ-diagonal জোড়ার {(i, j), (j, i)}-এ তিনটি বৈধ বিকল্প: কোনোটি নয়, শুধু একটি, শুধু অন্যটি।

rows (1..4) as bit strings of columns 1..4
W0 = R : 0100 0010 0001 0100
W1     : 0100 0010 0001 0100   (nobody reaches 1)
W2     : 0110 0010 0001 0110   (1->2->3, 4->2->3)
W3     : 0111 0011 0001 0111   (via 3: reach 4)
W4     : 0111 0111 0111 0111   (via 4: 2->...->4->2, 3->4->2)
missing: (1,1), (2,1), (3,1), (4,1) — no arrow ever enters 1

ধাপ k-তে শুধু k-কে মাঝের vertex হিসেবে অনুমতি দেওয়া হয়। Column 1-এ কেউ পৌঁছায় না, তাই closure-এ সেটি খালি; 2, 3, 4 একটি cycle, তাই তাদের নিজেদের সঙ্গে (2, 2), (3, 3), (4, 4) যোগ হয়।

(a) 3 classes [0], [1], [2] ; -7 = 3·(-3) + 2 -> [2]
(b) number of 1s = 0, 1, 2, 3 -> 4 classes of sizes 1, 3, 3, 1 (total 8)
(c) equivalence relations <-> partitions -> Bell number B4 = 15

(ক)-তে −7 mod 3-কে −1 লেখা সাধারণ ভুল; এই পাতার নিয়মে ভাগশেষ 0 থেকে 2-এর মধ্যে। (গ) equivalence relation আর partition-এর এক-এক মিল থেকে; B₄ = 1 + 7 + 6 + 1 = 15.

divisors: 1 2 3 4 6 9 12 18 36  (36 = 2^2·3^2 -> a 3×3 grid)
(a) covers multiply by one prime: 2 directions × 2 steps × 3 lines = 12 edges
(b) chain 1 | 2 | 4 | 12 | 36 (5 elements) ; antichain {4, 6, 9} (3 elements)
(c) lub(4, 6) = lcm = 12 ; glb(12, 18) = gcd = 6
(d) 1, 2, 3, 4, 6, 9, 12, 18, 36 (any order that puts each divisor before its multiples)

এই poset একটি lattice, কারণ যেকোনো দুটির lcm আর gcd ভাজকের মধ্যেই থাকে। মোট কয়টি topological sort সম্ভব, তা গোনা কঠিন প্রশ্ন: scratch script-এ সব ক্রম পরীক্ষা করে উত্তর এসেছে ৪২.

(a) sum = 18 -> 9 edges ; odd-degree vertices: two (the 3s)
    -> Euler path (between the two 3s), no Euler circuit
(b) 3,3,3,1 -> remove 3, subtract 1 from next 3: 2,2,0
    -> remove 2, subtract from next 2: 1,-1 -> negative: NOT graphical
(c) fix a start vertex, order the other 4: 4! = 24 ; each cycle counted twice
    (two directions) -> 12

(খ)-র সহজ কারণও আছে: degree 3-এর তিনটি vertex-এর প্রত্যেকে বাকি তিনজনের সঙ্গেই যুক্ত, ফলে চতুর্থটির degree অন্তত 3 হতো, 1 নয়। (ক)-তে sequence-টি বাস্তবে সম্ভব কি না Havel–Hakimi দিয়ে যাচাই করা হয়েছে (চেকার দেখুন)।

settle A(0) : B 4, C 2
settle C(2) : B min(4, 2+1) = 3 ; D 2+8 = 10 ; E 2+10 = 12
settle B(3) : D min(10, 3+5) = 8
settle D(8) : E min(12, 8+2) = 10 ; F 8+4 = 12
settle E(10): F min(12, 10+3) = 12 (no change)
settle F(12)
order A C B D E F ; parents: C<-A, B<-C, D<-B, E<-D, F<-D

B-তে সরাসরি রাস্তা ৪ মিনিট, অথচ C হয়ে ৩: “সরাসরি পথই ছোট” ধারণা ভুল। Dijkstra-র সঠিকতার শর্ত সব weight অঋণাত্মক; এখানে তা সত্য। নিচের stepper প্রতিটি settle-এর পরের দূরত্বের তালিকা দেখায়।

(a) V - E + F = 2 -> F = 2 - 10 + 15 = 7
(b) K3,3: V = 6, E = 9 ; bipartite -> no triangle -> planar would need E <= 2V - 4 = 8
    9 > 8 -> not planar
(c) chromatic polynomial of C_n: (k-1)^n + (-1)^n (k-1)
    C4, k = 3: 2^4 + 2 = 18 ; C5 is an odd cycle -> 2 colours impossible -> χ = 3

(খ)-তে E ≤ 3V − 6 = 12 শর্ত K_3,3 পূরণ করে, তাই তা দিয়ে কিছু প্রমাণ হয় না; triangle-হীন graph-এর কড়া শর্ত 2V − 4 লাগে। মনে রাখুন, শর্ত পূরণ হলেই planar নয়: এগুলো শুধু প্রয়োজনীয় শর্ত।

(a) start at free R2: R2 - O1 = R1 - O2 = R3 - O3 = R4 - O4 (free)
    ( - : non-matching edge, = : matching edge ) ; flip all edges:
    R2-O1, R1-O2, R3-O3, R4-O4 : size 4 (perfect)
(b) all four riders together can only take {O1, O2, O3}: 3 < 4
    Hall's condition fails -> maximum matching 3

Augmenting path দুই প্রান্তেই খালি vertex, আর edge-গুলো পালাক্রমে matching-এর বাইরে ও ভেতরে; উল্টে দিলে matching এক বাড়ে, এটিই Berge-এর উপপাদ্যের মূল কথা। (খ)-তে Hall-এর শর্ত ভাঙার একটি সেটই অসম্ভবতার প্রমাণ।

(a) 19 ; forest: each component loses one -> 20 - 3 = 17
(b) n = 3·10 + 1 = 31 ; leaves = 2·10 + 1 = 21
(c) 2^h >= 100 -> h >= ⌈log2 100⌉ = 7
(d) Cayley 5^(5-2) = 125

(গ)-র যুক্তিই comparison sort-এর নিচের সীমার ভিত্তি: n!টি leaf-এর decision tree-র height অন্তত ⌈log₂ n!⌉. (ঘ)-র ১২৫ চেকার K₅-এর সব ৪-edge উপসেট পরীক্ষা করে মিলিয়েছে।

(a) leaves 1,2,3,6 ; remove 1 -> write 4 ; remove 2 -> 4 ; remove 3 -> 4
    now 4 is a leaf (neighbour 5), leaves 4,6 -> remove 4 -> write 5 ; stop (n - 2 = 4)
    code (4, 4, 4, 5)
(b) n = 6 ; degree = 1 + appearances: d1=1 d2=2 d3=3 d4=1 d5=2 d6=1
    smallest leaf 1 -> edge 1-2 ; then 2 is a leaf -> edge 2-3
    smallest leaf 4 -> edge 4-3 ; then 3 is a leaf -> edge 3-5
    last two degree-1 vertices 5, 6 -> edge 5-6

একটি vertex code-এ যতবার আসে, তার degree তার চেয়ে এক বেশি: (ক)-তে 4 এসেছে তিনবার, degree 4. এই নিয়মে শুরুতেই leaf-গুলো চেনা যায়, যা decode-এর মূল চাবি।

sorted: B-C 1, A-C 2, D-E 2, E-F 3, A-B 4, D-F 4, B-D 5, C-D 8, C-E 10
take B-C 1, A-C 2, D-E 2, E-F 3
skip A-B 4 (A-C-B cycle), skip D-F 4 (D-E-F cycle)
take B-D 5 -> 5 edges = V - 1 : stop ; weight 1+2+2+3+5 = 13
shortest path tree from A: A-C, C-B, B-D, D-E, D-F -> weight 2+1+5+2+4 = 14

দুটি আলাদা: MST মোট তারের দৈর্ঘ্য ছোট করে, shortest path tree একটি উৎস থেকে প্রতিটি গন্তব্যের পথ ছোট করে। MST-তে A থেকে F-এ যেতে লাগে 2 + 1 + 5 + 2 + 3 = 13, অথচ সবচেয়ে ছোট পথ 12. A–B আর D–F-এর ওজন সমান (4) হলেও দুটিই বাদ, তাই এখানে tie ফলাফল বদলায় না।

(a) merges: 5+8=13 ; 12+13=25 ; 15+20=35 ; 25+35=60 ; 40+60=100
    codes (lighter tree = 0): a 0, d 100, f 1010, e 1011, c 110, b 111
(b) 40·1 + 20·3 + 15·3 + 12·3 + 8·4 + 5·4 = 233 bits per 100 -> 2.33 bits/symbol
    fixed length: ⌈log2 6⌉ = 3 bits -> saves 0.67 bits (about 22%)
(c) H = -∑ p log2 p ≈ 2.2784 <= 2.33 < H + 1

নিচের stepper পাঁচটি জোড়া লাগানো দেখায়। Tie না থাকায় দৈর্ঘ্যগুলো অনন্য; tie থাকলে tree বদলাতে পারে, কিন্তু গড় দৈর্ঘ্য একই থাকে। Entropy-র নিচে কোনো prefix code যেতে পারে না।

minterms (abcd): 0000 0001 0010 0101 1000 1001 1010
group 0,1,8,9   : b=0, c=0        -> b'c'
group 0,2,8,10  : b=0, d=0        -> b'd'   (four corners of the map)
group 1,5       : a=0, c=0, d=1   -> a'c'd
F = b'c' + b'd' + a'c'd
essential: b'c' (only one covering 9), b'd' (only one covering 2, 10), a'c'd (only one covering 5)

তিনটিই essential, তাই উত্তর অনন্য। চার কোণের group (0, 2, 8, 10) K-map-এ চোখ এড়িয়ে যায়, কারণ map-এর কিনারা গোল হয়ে মেলে; Quine–McCluskey-তে এটি সারি মিলিয়েই ধরা পড়ে।

(a) order of 8 = 12/gcd(8, 12) = 3 (8, 16≡4, 24≡0) ; generators: gcd(k,12)=1 -> 1,5,7,11 -> 4
(b) U(15) = {1,2,4,7,8,11,13,14} -> order 8 ; 2,4,8,16≡1 -> order of 2 = 4
(c) H, 1+H = {1,5,9}, 2+H = {2,6,10}, 3+H = {3,7,11} -> 4 cosets = 12/3
(d) No: 5 does not divide 12 (Lagrange)

(খ)-তে 2-এর order ৪, যা group-এর order ৮-কে ভাগ করে, Lagrange-এর সঙ্গে মিল। Coset-গুলো সমান আকারের আর পরস্পর বিচ্ছিন্ন, পুরো group-কে ভাগ করে; Lagrange-এর প্রমাণ ঠিক এই।

(a) bits: 1100101 ÷ 1011 (subtraction = XOR)
    1100101 xor 1011000 = 0111101   (q gets x^3)
    0111101 xor 0101100 = 0010001   (q gets x^2)
    0010001 xor 0010110 = 0000111   (q gets x^1)
    quotient x^3 + x^2 + x ; remainder x^2 + x + 1 (111)
(b) degree 3: reducible would need a linear factor = a root in GF(2)
    p(0) = 1, p(1) = 1 + 1 + 1 = 1 -> no root -> irreducible
(c) 1101011 000 ÷ 1011 -> remainder 110 -> send 1101011110

GF(2)-এ যোগ আর বিয়োগ একই (XOR), তাই কোনো “ধার” নেই। (খ)-র root পরীক্ষা শুধু degree ২ বা ৩-এ যথেষ্ট; degree ৪-এ দুটি degree-২ উৎপাদকও দেখতে হয়।

(a) c3 c5 c6 c7 = 1 1 0 1
    p1 = c3^c5^c7 = 1^1^1 = 1 ; p2 = c3^c6^c7 = 1^0^1 = 0 ; p4 = c5^c6^c7 = 1^0^1 = 0
    codeword c1..c7 = 1 0 1 0 1 0 1 = 1010101
(b) 1s at positions 1,3,5,6,7 -> XOR of positions: 1^3^5^6^7 = 6 -> syndrome 110 = 6
    flip bit 6 -> 1010101 ; data 1101
(c) 1s at 1,2,3,7 -> 1^2^3^7 = 7 -> decoder flips bit 7 -> 1110000 : WRONG codeword

Minimum distance ৩ মানে একটি error শোধরানো যায়, কিন্তু দুটি error-এ decoder ভুল দিকে “শোধরায়”। তাই বাড়তি একটি parity বিট দিয়ে SECDED (8,4) code ব্যবহার হয়: একটি শোধরায়, দুটি অন্তত ধরে।

state 0 -1-> (0·2+1)=1 -0-> 2 -1-> (4+1)%3=2 -1-> 2 -0-> (4+0)%3=1
final state 1 -> REJECT ; check 10110 = 22 = 7·3 + 1
length 5 = values 0..31 ; multiples of 3: 0, 3, …, 30 -> 11 strings

State-এর অর্থ “এ পর্যন্ত পড়া সংখ্যার mod 3”; নতুন বিট এলে মান দ্বিগুণ হয়ে বিট যোগ হয়। এই invariant-ই DFA-টির সঠিকতার প্রমাণ।

{q0}     -0-> {q0,q1}   -1-> {q0}
{q0,q1}  -0-> {q0,q1}   -1-> {q0,q2}
{q0,q2}  -0-> {q0,q1}   -1-> {q0}
reachable DFA states: 3 (accepting: {q0,q2})
1101: {q0} -1-> {q0} -1-> {q0} -0-> {q0,q1} -1-> {q0,q2} -> ACCEPT

সম্ভাব্য ৮টি উপসেটের মাত্র ৩টি নাগালে আসে। সব ভাষায় এত কম হয় না: “শেষ থেকে n-তম বিট 1” ভাষার জন্য যেকোনো DFA-তে অন্তত 2ⁿ state লাগে।

10111: 5 moves right to the blank, 1 move back -> q1 on the last 1
       three 1s -> 0 (carry), then 0 -> 1 and halt
       tape 11000 (23 + 1 = 24) ; steps 5 + 1 + 3 + 1 = 10
111  : 3 + 1 + 3 = 7 steps reach the blank left of the input ; write 1: 8 steps
       tape 1000 (7 + 1 = 8)

দৈর্ঘ্য n আর শেষে পরপর k-টি 1 থাকলে ধাপ n + k + 2: 5 + 3 + 2 = 10, 3 + 3 + 2 = 8. সব 1-এর ইনপুটে যন্ত্রকে ইনপুটের বাঁয়ের ফাঁকা ঘরে লিখতে হয়; ফিতা দুই দিকেই অসীম ধরলে তা বৈধ।

(a) no unit clause ; f appears only positive -> pure literal f
(b) a = T : C2 -> c = T ; C4 -> d = F ; C5 -> e = T ; C6 -> f = T
    C1, C3 satisfied ; b free -> model a=T, c=T, d=F, e=T, f=T (b any)
(c) unit ¬c -> c = F ; C2 -> a = F ; C3 -> b = F ; C1 = (F ∨ F) empty -> UNSAT
    (no branching needed)
(d) every model needs c = T (else (c) happens), so d = F, e = T, f = T ;
    then C1 needs a or b : (a,b) = 01, 10, 11 -> 3 models

(গ) দেখায়, unit propagation একাই কখনো কখনো পুরো সূত্রকে unsatisfiable প্রমাণ করে, কোনো অনুমান ছাড়া। (ঘ)-র যুক্তি চেকার ২^৬ = ৬৪টি মান-বিন্যাস পরীক্ষা করে মিলিয়েছে।

1. 120 = 84 + 36 ; 84 = 2·36 + 12 ; 36 = 3·12 -> 12
2. 3·5 = 15 ≡ 1 (mod 7) -> 5
3. C(7, 3) = 35
4. D4 = 9
5. C(6, 2) = 15
6. F = 2 - 8 + 12 = 6
7. log2 8 = 3 > 2 -> Θ(n^3)
8. R(3, 3) = 6 ; on 5 people the pentagon (C5) and its complement (another C5) have no triangle

সবচেয়ে বেশি ভুল হয় ২ আর ৭-এ: 3⁻¹-কে 1/3 লেখা অর্থহীন, mod 7-এ এটি একটি পূর্ণসংখ্যা; আর ৭-এ n² দেখে Θ(n² log n) লেখা, যা শুধু log_ba = d হলে আসত। Ramsey-র উত্তর পর্ব ৭৬ “Ramsey theory আর extremal combinatorics-এর পরিচয়”-এর।