مساله ۷۶. طناب‌ها

۱۰ طناب داریم که هر کدام دو سر دارند. این ۲۰ سر را به صورت تصادفی دو به دو جفت می‌کنیم و گره میزنیم. به طور متوسط چند حلقه ایجاد می‌شود؟

لینک سوال در توویتر: https://x.com/Riazi_Cafe/status/1812734639238418904

-

جواب برابر است با \(\sum_{i=1}^{10} \frac{1}{2i-1} \simeq 2.133\).

فرض کنید \(f(n)\) جواب مسئله ای باشد که در آن \(n\) طناب داریم. حال، یک انتهای یکی از طناب‌ها را انتخاب کرده و به یکی از \(2n-1\) انتهای دیگر به صورت تصادفی متصل می‌کنیم. اگر هر دو انتهای انتخاب شده از یک طناب باشند، یک حلقه و \(n-1\) طناب جداگانه داریم، در غیر این صورت \(n-2\) طناب جداگانه داریم و دو طناب که از یک انتها به هم متصل هستند. توجه کنید که هنگامی که دو طناب را به هم متصل می‌کنیم، به طور تئوری آنها معادل یک طناب واحد هستند و بنابراین در هر دو حالت، میانگین تعداد حلقه‌ها برای طناب‌های باقی‌مانده برابر \(f(n-1)\) است. از آنجا که احتمال حالت اول \(\frac{1}{2n-1}\) و احتمال حالت دوم \(\frac{2n-2}{2n-1}\) است، داریم: \[f(n) = \frac{1}{2n-1} + f(n-1) = \sum_{i=1}^{n} \frac{1}{2i-1}.\]