ইন্টারভিউ আর contest-এর গণিত — puzzle, counting আর graph

দুর্বল উত্তর: চুপ করে বসে থাকা, অথবা একটি সংখ্যা আন্দাজে বলে দেওয়া। কেন দুর্বল: ইন্টারভিউয়ার আপনার চিন্তা দেখতে পান না, আর আন্দাজ ভুল হলে ফেরার পথ থাকে না।

শক্ত উত্তর: প্রশ্নটি নিজের ভাষায় আবার বলুন আর শর্ত জিজ্ঞেস করুন। তারপর সবচেয়ে ছোট ক্ষেত্রটি জোরে সমাধান করুন (১টি মুদ্রা, ২ জন জলদস্যু, n = 1). একটি সাধারণ কৌশলের নাম বলে চেষ্টা করুন: “উল্টো দিক থেকে ভাবি”, “কোনো জিনিস কি বদলায় না?”, “খোপ আর কবুতর কী?”। সংকেত পেলে ধন্যবাদ দিয়ে সেটি ব্যবহার করুন। উত্তর না পেলেও যা প্রমাণ করেছেন আর যা অনুমান, তা আলাদা করে বলুন; সৎ আংশিক উত্তর আত্মবিশ্বাসী ভুলের চেয়ে ভালো। রিভিশন: পর্ব ০৯ প্রমাণের কৌশল.

উত্তর: ২ বার। ৩-৩-৩ তিন ভাগ করুন; দুই ভাগ দুই পাল্লায়। যে দিক নামে, ভারীটি সেখানে; সমান হলে বাইরের ভাগে। এবার সেই তিনটির দুটি দুই পাল্লায়, একই যুক্তি।

কেন ১ বারে অসম্ভব: প্রতিটি মাপার তিনটি ফল (বাঁ ভারী, সমান, ডান ভারী), তাই h বার মাপা একটি ternary decision tree, যার leaf বড়জোর 3^h. ৯টি সম্ভাবনার প্রতিটির আলাদা leaf লাগে, তাই 3^h ≥ 9, h ≥ 2. মূল কৌশল: দুই ভাগে নয়, তিন ভাগে ভাগ করুন, কারণ পাল্লার উত্তর তিন রকম। রিভিশন: পর্ব ৬৫ Tree.

নিচের সীমা: সম্ভাব্য উত্তর 12 × 2 = 24টি, আর তিনবারে বড়জোর 3³ = 27টি ফল; 24 ≤ 27, তাই তিনবার যথেষ্ট হতে পারে, দুবার (9 < 24) কখনো নয়। পর্ব ৬৫-এ এই যুক্তি আছে।

একটি আগে-ঠিক-করা পরিকল্পনা: প্রতিটি মুদ্রাকে তিন অক্ষরের একটি “কোড” দিন, প্রতিটি অক্ষর +1 (বাঁ পাল্লা), −1 (ডান পাল্লা) বা 0 (বাইরে)। শর্ত তিনটি: (১) কোনো কোড শূন্য নয়; (২) কোনো দুটি কোড সমান বা পরস্পরের উল্টো নয়; (৩) প্রতিটি মাপায় বাঁয়ে ৪টি, ডানে ৪টি, যাতে নকল না থাকলে পাল্লা সমান থাকে। তখন নকলটি ভারী হলে তিন মাপার ফল ঠিক তার কোড, হালকা হলে কোডের উল্টো। ২৪টি পরিস্থিতির ফল সব আলাদা, তাই ফল দেখে মুদ্রা আর ভারী-হালকা দুটিই জানা যায়। (13টি “±” জোড়ার একটি, (1, 1, 1), বাদ রেখে বাকি ১২টি থেকে চিহ্ন বেছে শর্ত (৩) মেলানো হয়েছে।) নিচের ব্লক ২৪টি পরিস্থিতিই সত্যিকারের ওজন দিয়ে মাপে। রিভিশন: পর্ব ৬৫ Tree, পর্ব ৩১ গণনার মূল নিয়ম.

অতিথি = vertex, হাত মেলানো = edge; একজনের হাত মেলানোর সংখ্যা তাঁর degree.

1. (ক) degree-র সম্ভাব্য মান 0, 1, …, n − 1, মোট n টি। কিন্তু 0 আর n − 1 একসাথে থাকতে পারে না: কেউ সবার সাথে হাত মেলালে কেউ শূন্য নন। — case
2. তাই বাস্তবে বড়জোর n − 1টি মান, অতিথি n জন; pigeonhole অনুযায়ী দুজনের degree সমান। ∎
3. (খ) প্রতিটি হাত মেলানো দুজনের degree-তে ১ করে যোগ করে, তাই সব degree-র যোগফল 2E, জোড়। — handshake lemma
4. জোড় degree-গুলোর যোগফল জোড়, তাই বিজোড় degree-গুলোর যোগফলও জোড়; বিজোড় সংখ্যার যোগফল জোড় হয় কেবল তাদের সংখ্যা জোড় হলে। ∎

রিভিশন: পর্ব ৩২ Pigeonhole principle, পর্ব ৫৭ গ্রাফ.

প্রতিটি মানুষের জন্য একটি proposition নিন: A = “A knight”. Knight-এর কথা সত্য, knave-এর কথা মিথ্যা, তাই প্রতিটি কথা একটি biconditional: A ↔ ¬B, B ↔ (A ↔ C), C ↔ ¬A.

1. ধরি A knave. তাহলে C ↔ ¬A থেকে C knight, আর A ↔ ¬B থেকে B knight.
2. B knight হলে তাঁর কথা সত্য: A আর C একই ধরনের। কিন্তু A knave, C knight — বিরোধ। তাই A knight.
3. A knight ⇒ B knave (A-র কথা) আর C knave (C ↔ ¬A).
4. যাচাই: B knave, তাই “A আর C একই ধরনের” মিথ্যা হওয়া চাই; সত্যিই A knight, C knave, আলাদা। ∎

উত্তর: A knight, B আর C knave. আটটি সম্ভাবনার truth table পুরোটা দেখলেও একটিই সারি টেকে (নিচের ব্লক)। রিভিশন: পর্ব ০২ Propositional logic, পর্ব ০৭ কাজে যুক্তি.

এটি একটি বহুল প্রচলিত পুরোনো ধাঁধা, যার নিয়ম বইভেদে একটু আলাদা; উত্তর নিয়মের ওপর নির্ভর করে, তাই আগে নিয়ম জিজ্ঞেস করে নিন। কৌশল: backward induction, অর্থাৎ শেষ থেকে শুরু।

1. ১ জন বাকি (৫ নম্বর): সব ১০০ তাঁর। ২ জন (৪, ৫): ৪ নিজের ভোটেই অর্ধেক, তাই (100, 0).
2. ৩ জন (৩, ৪, ৫): ২টি ভোট লাগে। ৫ নম্বর পরের ধাপে ০ পাবেন, তাই ১টি মুদ্রায় কেনা যায়: (99, 0, 1).
3. ৪ জন (২–৫): ২টি ভোট; পরের ধাপে ৪ নম্বর ০ পান, তাঁকে ১: (99, 0, 1, 0).
4. ৫ জন (১–৫): ৩টি ভোট, অর্থাৎ নিজের বাইরে আরও ২টি। পরের ধাপে ৩ আর ৫ নম্বর ০ পান; প্রত্যেককে ১টি করে দিলেই তাঁরা ভালো থাকেন: (98, 0, 1, 0, 1). ∎

প্রতিটি ধাপ আগের ধাপের ফল ব্যবহার করে, যা strong induction-এর মতো। নিয়ম বদলালে (যেমন “অর্ধেকের বেশি” লাগলে) উত্তর বদলায়; ইন্টারভিউতে এটি বলে দেওয়াই পরিপক্বতা। রিভিশন: পর্ব ১১ Strong induction.

উত্তর: ৬. প্রতিবার সফলতার সম্ভাবনা p = 1/6, আর প্রথম সফলতা পর্যন্ত চেষ্টার সংখ্যা geometric distribution মানে; E = 1/p. এক লাইনের প্রমাণ: E = 1 + (1 − p)·E, কারণ একবার ছুড়তেই হয়, আর ব্যর্থ হলে (সম্ভাবনা 1 − p) একই অবস্থা থেকে আবার শুরু। সমাধান E = 1/p. রিভিশন: পর্ব ৪০ প্রত্যাশা.

এটি coupon collector সমস্যা। i রকম হাতে থাকলে নতুন একটি পাওয়ার সম্ভাবনা (6 − i)/6, তাই সেই ধাপে গড় অপেক্ষা 6/(6 − i) (প্র ৭-এর সূত্র)। মোট অপেক্ষা ধাপগুলোর যোগফল, আর linearity অনুযায়ী গড়ও যোগ হয়:

E = 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 6 · H₆ = 6 · 49/20 = 14.7

সাধারণভাবে n রকমে n·H_n ≈ n ln n, যেখানে H_n = 1 + 1/2 + … + 1/n একটি harmonic number. শেষের কয়েকটি রকমই বেশি সময় নেয়: শেষ কার্ডটির জন্যই গড়ে ৬টি প্যাকেট। রিভিশন: পর্ব ৪০ প্রত্যাশা.

উত্তর: ২৩ জন, সম্ভাবনা প্রায় ০.৫০৭. পরিপূরক নিন: সবার জন্মদিন আলাদা হওয়ার সম্ভাবনা (365/365)(364/365)…((365 − n + 1)/365); এটি ১ থেকে বিয়োগ করলে উত্তর। অবাক লাগে, কারণ আমরা “আমার সাথে কারও মিল” ভাবি, অথচ গোনা হয় যেকোনো জোড়া: ২৩ জনে C(23, 2) = 253টি জোড়া। এর প্রয়োগ hash collision: k-বিটের hash-এ মোটামুটি 2^k/2টি মান নিলেই মিলের সম্ভাবনা উল্লেখযোগ্য; এটিই birthday paradox-এর শিক্ষা। রিভিশন: পর্ব ৪২ Birthday paradox আর hash collision.

উত্তর: HH-এ ৬, HT-তে ৪ — সমান নয়। অবস্থা ধরে প্রত্যাশিত মান-এর সমীকরণ লিখুন। E₀ = শুরু থেকে বাকি গড়, E₁ = শেষে একটি H আছে এমন অবস্থা থেকে।

1. HH: E₀ = 1 + ½E₁ + ½E₀; E₁ = 1 + ½·0 + ½E₀ (T এলে আবার শুরু)। সমাধান E₀ = 6.
2. HT: E₀ = 1 + ½E₁ + ½E₀; E₁ = 1 + ½E₁ + ½·0 (H এলে H-এই থাকি, শুরুতে ফিরি না)। তাই E₁ = 2, E₀ = 4. ∎

পার্থক্যের কারণ: HH-এর মাঝপথে T এলে পুরো অগ্রগতি হারায়, HT-র মাঝপথে H এলে কিছুই হারায় না। একই পদ্ধতিতে ছক্কায় পরপর দুটি ৬: 6 + 6² = 42. রিভিশন: পর্ব ৩৯ শর্তসাপেক্ষ সম্ভাবনা, পর্ব ৪০ প্রত্যাশা.

উত্তর: C(9, 2)² = 36² = 1296. বোর্ডে ৯টি খাড়া আর ৯টি আড়াআড়ি রেখা। প্রতিটি আয়তক্ষেত্র ঠিক দুটি খাড়া আর দুটি আড়াআড়ি রেখা দিয়ে ঘেরা, আর উল্টোভাবে প্রতিটি এমন বাছাই একটি আয়তক্ষেত্র দেয়: এটি একটি bijection. তাই গুণের নিয়মে C(9, 2) × C(9, 2). ঘর ধরে গুনতে গেলে জট পাকে; রেখা ধরে গোনাই কৌশল। রিভিশন: পর্ব ৩৩ Permutation আর combination, পর্ব ৩৭ গণনার কৌশল.

x-কে binary-তে লিখুন: শেষ অংশটি একটি 1, তারপর k টি 0. x − 1-এ সেই 1 হয়ে যায় 0, আর পরের k টি 0 হয়ে যায় 1; ওপরের অংশ একই থাকে। AND নিলে ওপরের অংশ টিকে থাকে, নিচের সব শূন্য: সবচেয়ে ডানের 1-বিটটি মুছে যায়। উদাহরণ: 40 = 101000, 40 & 39 = 100000 = 32.

2-এর ঘাতে ঠিক একটি 1-বিট, তাই x > 0 আর x & (x - 1) == 0 ⇔ x একটি 2-এর ঘাত। শর্ত x > 0 জরুরি: x = 0-তেও 0 & -1 == 0, অথচ 0 কোনো ঘাত নয়। একই কৌশল বারবার চালালে 1-বিট গোনা যায় (প্রতিটি ধাপে একটি বিট মোছে)। পর্ব ৭৭-এ Z3 দিয়ে এই নিয়ম সব 32-বিট মানে প্রমাণ করা হয়েছে। রিভিশন: পর্ব ৭৭ SAT আর SMT solver.

সবগুলোর XOR নিন। কারণ: XOR (বিট ধরে ২ দিয়ে ভাগশেষের যোগ) associative আর commutative, a ⊕ a = 0, a ⊕ 0 = a. তাই ক্রম বদলে জোড়াগুলো পাশাপাশি আনা যায়; প্রতিটি জোড়া 0 হয়, বাকি থাকে একক সংখ্যাটি। ∎ বীজগণিতের ভাষায়, k-বিট সংখ্যা XOR-এর অধীনে একটি group, যেখানে প্রতিটি উপাদান নিজেই নিজের inverse. রিভিশন: পর্ব ৭০ Group.

এটি Gray code: g(i) = i ⊕ (i >> 1). ৩ বিটে: 000, 001, 011, 010, 110, 111, 101, 100. Recursive গঠন: n − 1 বিটের তালিকা, তারপর সেটি উল্টো ক্রমে আর সামনে একটি 1. সংযোগস্থলে শুধু সামনের বিট বদলায়, আর দুই অর্ধেকের ভেতরে induction অনুযায়ী এক বিট। Graph-এর ভাষায় এটি n-মাত্রার cube-এ একটি Hamilton path. রিভিশন: পর্ব ৩৬ Permutation আর combination তৈরি, পর্ব ৬০ Euler আর Hamilton path.

উত্তর: ৯. একক অঙ্ক মানে mod 10. 7¹ ≡ 7, 7² ≡ 9, 7³ ≡ 3, 7⁴ ≡ 1 (mod 10), তাই ঘাতগুলো ৪-এর চক্রে ঘোরে। 2026 = 4 · 506 + 2, তাই 7²⁰²⁶ ≡ (7⁴)⁵⁰⁶ · 7² ≡ 1 · 9 ≡ 9. বড় ঘাতে কোডে pow(7, 2026, 10) বা repeated squaring, যা log₂ 2026-এর কাছাকাছি গুণে কাজ সারে। রিভিশন: পর্ব ২২ Modular arithmetic.

Modular হিসাবে সরাসরি ভাগ নেই; ভাগের বদলে modular inverse দিয়ে গুণ। p = 10⁹ + 7 মৌলিক, আর p ∤ a হলে Fermat-এর ছোট উপপাদ্য a^p−1 ≡ 1 দেয়, তাই a⁻¹ ≡ a^p−2 (mod p). তাই C(n, r) ≡ n! · (r!)^p−2 · ((n − r)!)^p−2 (mod p).

শর্ত: p মৌলিক, আর r! ও (n − r)! p দিয়ে বিভাজ্য নয়, যা n < p হলে নিশ্চিত। Modulus মৌলিক না হলে Fermat চলে না; তখন extended Euclid, আর gcd(a, m) = 1 হলেই কেবল inverse আছে। আরেকটি ফাঁদ: C বা Java-তে ঋণাত্মক সংখ্যার % ঋণাত্মক হতে পারে, তাই ((a % m) + m) % m লিখুন। রিভিশন: পর্ব ২১ GCD আর Euclid, পর্ব ২৪ Fermat আর Euler.

উত্তর: ২৪. প্রতিটি শেষের শূন্য একটি 10 = 2 × 5 উৎপাদক। 100!-এ ২-এর উৎপাদক ৫-এর চেয়ে অনেক বেশি, তাই শূন্যের সংখ্যা = ৫-এর ঘাত। Legendre-এর সূত্র: ⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24. ২৫, ৫০, ৭৫, ১০০ প্রত্যেকে দুটি ৫ দেয়; এগুলো ভুলে গেলে উত্তর ২০ আসে, যা সবচেয়ে পরিচিত ভুল। রিভিশন: পর্ব ২০ বিভাজ্যতা আর মৌলিক সংখ্যা.

Tree = connected আর cycle নেই। উপপাদ্য: n টি vertex-এর graph-এ এই তিনটির যেকোনো দুটি সত্য হলে তৃতীয়টিও সত্য — connected, acyclic, ঠিক n − 1টি edge. তাই পরীক্ষা: edge গুনুন (n − 1 কি?), তারপর একবার BFS বা DFS-এ সব vertex পৌঁছায় কি না।

Edge একে একে এলে union-find: প্রতিটি component একটি সেট। নতুন edge (u, v)-এর দুই প্রান্ত আগে থেকেই একই সেটে থাকলে তাদের মধ্যে আগেই একটি পথ আছে, তাই এই edge একটি cycle বন্ধ করে; না থাকলে দুই সেট জুড়ে দিন। রিভিশন: পর্ব ৬৫ Tree; কোডে DSA কোর্সের পর্ব ৩৩.

রাইডার = vertex, দ্বন্দ্ব = edge; প্রশ্নটি হলো graph-টি bipartite কি না। উপপাদ্য: graph bipartite ⇔ কোনো বিজোড় দৈর্ঘ্যের cycle নেই।

1. (⇒) bipartite হলে প্রতিটি edge দুই দলের মধ্যে যায়, তাই একটি cycle-এ দল পালাক্রমে বদলায়; শুরুর দলে ফিরতে জোড় সংখ্যক ধাপ লাগে।
2. (⇐) প্রতিটি component-এ একটি vertex থেকে BFS চালিয়ে দূরত্ব জোড় হলে রং ০, বিজোড় হলে ১ দিন। একই রঙের দুটি vertex-এর মধ্যে edge থাকলে, দুজনের BFS পথ আর সেই edge মিলে একটি বিজোড় দৈর্ঘ্যের closed walk হয়, যার ভেতরে একটি বিজোড় cycle থাকে; অনুমানের সাথে বিরোধ। ∎

Algorithm সরাসরি প্রমাণ থেকে আসে: BFS-এ রং দিন, বিরোধ পেলে থামুন। রিভিশন: পর্ব ৬৩ Graph coloring.

শর্তগুলো একটি directed graph. Topological order আছে ⇔ graph-টি DAG (directed cycle নেই)। Cycle থাকলে সেই cycle-এর কোনো কাজই প্রথমে আসতে পারে না। উল্টো দিকের মূল lemma: প্রতিটি সসীম DAG-এ অন্তত একটি vertex-এ কোনো arc ঢোকে না। প্রমাণ: না থাকলে প্রতিটি vertex থেকে একটি arc উল্টো দিকে ধরে পিছিয়ে যেতে পারতেন অসীম সময় ধরে; vertex সসীম, তাই pigeonhole অনুযায়ী কোনো vertex ফিরে আসে, অর্থাৎ cycle, বিরোধ। সেই vertex প্রথমে বসিয়ে মুছে দিন; বাকিটাও DAG, তাই induction-এ বাকি ক্রম। এটিই Kahn-এর algorithm, আর কাজ আটকে গেলে বাকি vertex-গুলো cycle-এর খবর দেয়। রিভিশন: পর্ব ৫৬ Partial order আর topological sort.

Dijkstra B-কে আগে বের করে (দূরত্ব 2) আর “চূড়ান্ত” ধরে; পরে C (5) থেকে C→B দিয়ে 1 পাওয়া যেত, কিন্তু B তখন বন্ধ। তাই B = 2 আর D = 3, যেখানে আসল উত্তর B = 1, D = 2. Dijkstra-র সঠিকতার প্রমাণের মূল ধাপ: “যে vertex বের হলো, তার চেয়ে ছোট পথ পরে আসতে পারে না, কারণ পরের পথ শুধু লম্বা হয়” — এটি সব weight ≥ 0 ধরে নেয়। একটি ঋণাত্মক edge থাকলেই ধাপটি ভাঙে। Bellman-Ford প্রতিটি arc |V| − 1 বার relax করে ঠিক উত্তর দেয়, যদি A থেকে পৌঁছানো যায় এমন কোনো ঋণাত্মক cycle না থাকে। রিভিশন: পর্ব ৬১ Shortest path-এর গণিত; কোডে DSA কোর্সের পর্ব ৪৪.

(ক) না। প্রতিটি spanning tree-তে ঠিক n − 1টি edge, তাই প্রতিটির মোট weight ঠিক (n − 1)c বাড়ে; সবচেয়ে ছোটটি সবচেয়ে ছোটই থাকে। আরেক দিক থেকে: Kruskal শুধু edge-গুলোর ক্রম দেখে, আর c যোগে ক্রম বদলায় না। Cut property-ও একই কথা বলে।

(খ) হ্যাঁ, বদলাতে পারে। পথে edge-এর সংখ্যা আলাদা হতে পারে, আর k টি edge-এর পথ kc বাড়ে। উদাহরণ: A–C সরাসরি 3, A–B–C পথে 1 + 1 = 2; সবচেয়ে ছোট A–B–C. c = 2 যোগ করলে সরাসরি 5, অন্যটি 3 + 3 = 6; এখন সরাসরি পথই ছোট। শিক্ষা: MST আর shortest path আলাদা প্রশ্ন; একটির ধর্ম অন্যটিতে ধরে নেবেন না। রিভিশন: পর্ব ৬৭ Spanning tree, পর্ব ৬১ Shortest path.

a_n = n ধাপে ওঠার উপায়। শেষ পা ১ ধাপের হলে আগে n − 1 ধাপ, ২ ধাপের হলে n − 2: তাই a_n = a_n−1 + a_n−2, a₁ = 1, a₂ = 2. টেবিল: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. এটি Fibonacci, এক ঘর সরানো। দুটি basis লাগে, কারণ recurrence দুই ধাপ পেছনে যায়। Recursion সরাসরি লিখলে একই মান বারবার হিসাব হয় আর সময় সূচকীয়; টেবিলে রাখলে O(n). রিভিশন: পর্ব ৪৪ Recurrence দিয়ে মডেল.

বাঁ দিক থেকে দেখুন: প্রথম কলাম হয় একটি খাড়া টাইলে ঢাকা (বাকি 2 × (n − 1)), নয় দুটি শোয়ানো টাইল একসাথে প্রথম দুই কলাম ঢাকে (বাকি 2 × (n − 2)); একটি শোয়ানো টাইল একা থাকতে পারে না, কারণ তার নিচের ঘর তখন আরেকটি শোয়ানো টাইল ছাড়া ঢাকা যায় না। তাই t_n = t_n−1 + t_n−2, t₁ = 1, t₂ = 2: সিঁড়ির একই সংখ্যা। Bijection: খাড়া টাইল ↔ ১ ধাপ, দুটি শোয়ানো ↔ ২ ধাপ। 2 × 10-এ ৮৯. রিভিশন: পর্ব ৪৪ Recurrence দিয়ে মডেল, পর্ব ৩৭ গণনার কৌশল — bijection.

n বিজোড় হলে ০: ঘর 3n টি, বিজোড়, আর প্রতিটি domino ২টি ঘর ঢাকে। n জোড় হলে মানগুলো (n = 2, 4, 6, 8) 3, 11, 41, 153, আর তারা মেনে চলে a_n = 4a_n−2 − a_n−4; যেমন 4 · 41 − 11 = 153. এই recurrence আসে একটি সহায়ক গণনা থেকে: এক কোণার ঘর বাদ দেওয়া 3 × n বোর্ডের tiling, যার সাথে মূল গণনা পরস্পর জড়িয়ে থাকে; দুটি মিলিয়ে সহায়কটি বাদ দিলে এই রূপ। ইন্টারভিউতে পুরো derivation না পারলেও “বিজোড়ে অসম্ভব”, ছোট মানের brute force আর অনুমিত recurrence-এর যাচাই দেখানোই শক্ত উত্তর। রিভিশন: পর্ব ৪৫ Linear recurrence সমাধান.

উত্তর Catalan সংখ্যা C_n = C(2n, n)/(n + 1): n = 3-এ ৫ — ((())), (()()), (())(), ()(()), ()()() — আর n = 5-এ ৪২. Recurrence: প্রথম “(” যে “)”-এর সাথে জোড়া বাঁধে, তার ভেতরে k জোড়া আর বাইরে n − 1 − k জোড়া, তাই C_n = Σ C_kC_n−1−k. একই সংখ্যা গোনে n টি node-এর binary tree-র আকার আর কর্ণ না-পেরোনো lattice path; ইন্টারভিউতে “এটি Catalan” চেনাই অর্ধেক কাজ। রিভিশন: পর্ব ৫০ বিশেষ সংখ্যা.

না। দাবার রং দিন। বিপরীত কোণার দুটি ঘর একই রঙের (দুটির সারি আর কলামের যোগফলের parity এক), তাই বাকি থাকে এক রঙের ৩০টি আর অন্য রঙের ৩২টি। প্রতিটি domino পাশাপাশি দুটি ঘর ঢাকে, যারা সবসময় ভিন্ন রঙের; তাই যেকোনো আংশিক ঢাকায় “দুই রঙের ঢাকা ঘরের পার্থক্য” = 0, একটি invariant. পুরো ঢাকায় পার্থক্য হতো 32 − 30 = 2. বিরোধ। ∎ ছবি ৮৩.২ একই যুক্তি ৪ × ৪-এ দেখায়। শিক্ষা: গণনা (৬২ জোড়) ঠিক থাকলেও গঠন অসম্ভব হতে পারে। রিভিশন: পর্ব ৮২ প্রমাণ লেখার অনুশীলন.

না, শেষ সংখ্যা সবসময় বিজোড়। Invariant: সব সংখ্যার যোগফলের parity. একটি চালে যোগফল থেকে a + b যায় আর |a − b| আসে; a + b আর |a − b|-এর পার্থক্য 2·min(a, b), জোড়, তাই parity একই থাকে। শুরুতে 1 + 2 + … + 10 = 55, বিজোড়। শেষে একটিই সংখ্যা, তাই সেটি বিজোড়, ০ নয়। ∎ নিচের ব্লক n ≤ 8-এ প্রতিটি সম্ভাব্য চালের ক্রম ঘুরে দেখায়, শেষ সংখ্যার parity সবসময় যোগফলের parity-র সমান।

1. নিয়ম: যতক্ষণ কোনো সারি বা কলামের যোগফল s < 0, সেটির চিহ্ন উল্টান। — প্রক্রিয়া
2. সেই চালে পুরো সারণির মোট যোগফল −2s পরিমাণ বাড়ে, যা ধনাত্মক; মোট যোগফল কড়াভাবে বাড়ে। — monovariant
3. প্রতিটি ঘরের মান শুধু ±(মূল মান) হতে পারে, তাই সম্ভাব্য সারণি বড়জোর 2^mnটি, আর মোট যোগফল সসীম কয়েকটি মানের একটি। — সসীমতা
4. কড়াভাবে বাড়তে থাকা রাশি সসীম মানের মধ্যে অসীমবার বাড়তে পারে না, তাই প্রক্রিয়া থামে; থামে কেবল যখন কোনো সারি বা কলামের যোগফল ঋণাত্মক নয়। ∎

প্রমাণটি অস্তিত্বের, আর algorithm-ও দেয়। একই ধারণায় দেখানো হয় যে অনেক local search থামে। রিভিশন: পর্ব ১১ Well-ordering, পর্ব ১৩ Program-এর সঠিকতা.

হারা অবস্থান ঠিক ৪-এর গুণিতকগুলো; পর্ব ১১-এ strong induction-এ এটি প্রমাণিত। ২০ ৪-এর গুণিতক, তাই প্রথম জন হারবেন, যদি দ্বিতীয় জন প্রতিবার মোট ৪ পূরণ করেন: প্রথম জন k টি তুললে তিনি তোলেন 4 − k টি। ২২-এ প্রথম জন ২টি তুলে ২০-এ পাঠান, তারপর একই “৪ পূরণ” কৌশলে জেতেন। এটি Nim-এর এক স্তূপের একটি সীমিত রূপ; পরের প্রশ্নে পুরো Nim. রিভিশন: পর্ব ১১ Strong induction.

স্তূপ h₁, …, h_k, আর nim-sum s = h₁ ⊕ … ⊕ h_k. দুটি lemma, তারপর strong induction.

1. Lemma ১: s = 0 হলে প্রতিটি চালের পরে s ≠ 0. একটি স্তূপ h_i থেকে h' < h_i-তে গেলে নতুন nim-sum s' = s ⊕ h_i ⊕ h' = h_i ⊕ h' ≠ 0, কারণ h' ≠ h_i. — XOR-এর ধর্ম: a ⊕ a = 0
2. Lemma ২: s ≠ 0 হলে এমন একটি চাল আছে, যার পরে s = 0. s-এর সবচেয়ে বাঁয়ের 1-বিটটি d নিন; কোনো স্তূপ h_i-তে বিট d আছে (নইলে s-এ থাকত না)। h' = h_i ⊕ s নিন: বিট d-তে 1 থেকে 0 হয়, তার ওপরের বিট একই, তাই h' < h_i, অর্থাৎ বৈধ চাল; নতুন nim-sum s ⊕ h_i ⊕ h' = s ⊕ s = 0. — binary তুলনা
3. Induction (মোট কাঠির সংখ্যা N-এর ওপর): N = 0-তে s = 0 আর কোনো চাল নেই, তাই হারা। ছোট সব N-এ দাবি সত্য ধরে নিন। s = 0 হলে Lemma ১ অনুযায়ী প্রতিটি চাল কম কাঠির একটি s ≠ 0 অবস্থানে যায়, যা hypothesis অনুযায়ী জেতা; তাই বর্তমানটি হারা। s ≠ 0 হলে Lemma ২-এর চাল একটি হারা অবস্থানে পাঠায়; তাই বর্তমানটি জেতা। ∎

পর্ব ১১-এ যেমন বলা আছে, Nim-এর এই সমাধান সাধারণত Charles L. Bouton-এর (১৯০১) বলে উল্লেখ করা হয়। নিচের stepper (3, 4, 5) থেকে একটি পুরো খেলা দেখায়।

সংকেত: শুধু ভাগশেষ গুরুত্বপূর্ণ।

সমাধান: c_r = যতগুলোর ভাগশেষ r. যোগফল k দিয়ে বিভাজ্য ⇔ ভাগশেষ দুটি r আর k − r (mod k). তাই উত্তর C(c₀, 2) + Σ_{1 ≤ r < k/2} c_r·c_k−r, আর k জোড় হলে আরও C(c_k/2, 2). r = 0 আর r = k/2-এ দুটি সংখ্যাই একই দলের, তাই সেখানে গুণ নয়, C(c, 2); এটি ভুলে গেলে দুবার গোনা হয়। সময় O(n + k). রিভিশন: পর্ব ২২ Modular arithmetic, পর্ব ৩৩ Combination.

সংকেত: prefix sum আর pigeonhole.

1. S₀ = 0, S_j = a₁ + … + a_j (j = 1…n): মোট n + 1টি prefix sum.
2. Mod n-এ ভাগশেষ মাত্র n টি, তাই pigeonhole অনুযায়ী দুটি S_i, S_j (i < j)-এর ভাগশেষ সমান।
3. তাহলে S_j − S_i = a_i+1 + … + a_j ≡ 0 (mod n), আর অংশটি খালি নয়, কারণ i < j. ∎

Algorithm: একটি dictionary-তে প্রতিটি ভাগশেষ প্রথম কোথায় দেখা গেছে, তা রাখুন; একই ভাগশেষ আবার এলেই উত্তর। ঋণাত্মক সংখ্যাতেও কাজ করে, যদি ভাগশেষ 0…n − 1-এ নেওয়া হয়। রিভিশন: পর্ব ৩২ Pigeonhole principle.

সংকেত: একক সেটগুলো যোগ, জোড়ার ছেদ বিয়োগ, তিনটির ছেদ আবার যোগ।

সমাধান: Inclusion–exclusion: ⌊1000/2⌋ + ⌊1000/3⌋ + ⌊1000/5⌋ − ⌊1000/6⌋ − ⌊1000/10⌋ − ⌊1000/15⌋ + ⌊1000/30⌋ = 500 + 333 + 200 − 166 − 100 − 66 + 33 = 734. ২ আর ৩ দুটি দিয়েই বিভাজ্য মানে ৬ দিয়ে বিভাজ্য, কারণ তারা পরস্পর মৌলিক; ৪ আর ৬ হলে ছেদ হতো ১২-র গুণিতক, ২৪-এর নয়। রিভিশন: পর্ব ৪৯ Inclusion–exclusion.

সংকেত: প্রথম অতিথি যাঁর ছাতা পেলেন, তিনি প্রথম জনের ছাতা পেলেন কি না।

সমাধান: এগুলো derangement. অতিথি ১ পান অতিথি j-এর ছাতা (n − 1টি উপায়)। j পান ১-এর ছাতা হলে বাকি n − 2 জন নিজেদের মধ্যে derangement: D_n−2; না পেলে j-এর জন্য “১-এর ছাতা নিষেধ” ঠিক “নিজের ছাতা নিষেধ”-এর মতো, তাই D_n−1. সুতরাং D_n = (n − 1)(D_n−1 + D_n−2), D₁ = 0, D₂ = 1: 0, 1, 2, 9, 44. সম্ভাবনা 44/120 ≈ 0.367; n বাড়লে D_n/n! → 1/e ≈ 0.368 (inclusion–exclusion-এর সূত্র থেকে)। রিভিশন: পর্ব ৪৯ Inclusion–exclusion আর derangement.