مساله ۶۴. کلوچه‌های نصفه

در ظرفی ۱۵ کلوچه کامل داریم. هر روز یکی از محتویات این ظرف را به صورت تصادفی برمی‌داریم. اگر کلوچه‌ی کامل بود، نصفش رو می‌خوریم و نصف دیگر رو برمی‌گردونیم داخل ظرف. اگر کلوچه‌ی نصفه بود، می‌خوریمش.

امید ریاضی تعداد کلوچه‌های نصفه باقیمانده در ظرف وقتی آخرین کلوچه کامل را برمی‌داریم چند است؟

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

پاسخ مساله تقریبا برابر است با ۲٫۳۱۸۲. در اینجا هدف پیدا کردن امید ریاضی تعداد نیم‌کلوچه‌های داخل ظرف را وقتی کلوچه کامل آخر را برمی‌داریم و هنوز نصفه‌اش را هنوز به ظرف برنگردانده‌ایم است.

اگر کلوچه‌های کامل را به ازای ترتیب برداشته شدن از ظرف شماره‌گذاری کنیم، نیم‌کلوچه‌ای که پس از نصف کردن k-مین کلوچه کامل در ظرف گذاشته می‌شود را k-مین نیم‌کلوچه می‌نامیم. مقدار متغیر تصادفی $X_k$ را 1 قرار می‌دهیم اگر ترتیب خارج شدن k-مین نیم‌کلوچه از ظرف پس از آخرین کلوچه کامل باشد، و در غیر اینصورت $X_k=0‏$‎ قرار می‌دهیم.

با توجه به اینکه می‌خواهیم امیدریاضی تعداد نیم‌کلوچه‌های اول تا ۱۴ ام را که ترتیب خروجشان پس از کلوچه کامل ۱۵ ام است را پیدا کنیم، پاسخ مساله برابر است با

$$ E(X_1+X_2+...+X_{14}) = E(X_1)+E(X_2)+...+E(X_{14}) $$

پس از اینکه k-مین نیم‌کلوچه به ظرف برگردانده می‌شود، هنوز $15-k‏$‎ کلوچه کامل در ظرف وجود دارد، و $X_k=1‏$‎ اگر و تنها اگر در مجموعه کلوچه‌های این $15-k‏$‎ کلوچه کامل و k-مین نیم‌کلوچه، k-مین نیم‌کلوچه آخرینی باشد که از ظرف خارج می‌شود. از آنجا که در هر گام، احتمال خارج شدن تمام اعضای این مجموعه یکسان است، داریم:

$$ E(X_k) = Pr_n(X_k = 1)=\frac{1}{15-k+1} $$

بنابراین پاسخ مساله برابر است با:

$$ E(X_1)+...E(X_{14}) = 1/15+1/14+...+1/2 \approx 2.3182 $$

منبع سوال و راه‌حل:

Velleman, Daniel (April 2014). "Drug Induced Random Walk". American Mathematical Monthly (http://dx.doi.org/10.4169/amer.math.monthly.121.04.299)