مساله ۲۰. درآمد از مهرهها

در یک مسابقه شرکت میکنید که در آن یک گوی با ۱۰۰۰ سنگریزه سیاه و ۱۰۰۰ سنگریزه سفید وجود دارد. میتونید هر بار یک سنگریزه به صورت تصادفی از گوی بردارید و آن را حذف کنید. اگر سنگریزه حذف شده سیاه باشد، یک دلار جایزه میگیرید و اگر سفید باشد یک دلار جریمه میشوید. میتونید تا زمانی که در گوی حداقل یک سنگریزه وجود دارد بازی را ادامه بدید و هر زمانی که خواستید بازی را تمام کنید. استراتژی شما در این بازی چیست؟
(استراژی بهینه نیاز به محاسبات زیاد دارد. هدف سوال پیدا کردن استراتژی هست که ساده و تقریبا بهینه باشد)
لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1687349831696809984
همون طور که گفتیم هدف سوال پیدا کردن استراتژی بهینه نیست و برای همین پاسخ های متفاوتی برای سوال وجود داره. الگوریتم پیشنهادی ما این هست که اونقدر بازی را ادامه بدیم که تعداد سنگریزه های سفید باقی مونده بیشتر از تعداد سنگریزه های سیاه باقی مونده به اضافه رادیکال تعداد سنگریزه های سیاه باقی مونده بشه. در این صورت، به صورت میانگین امتیاز ما برابر با 16.224 میشه که بیش از 98 درصد بیشترین امتیاز ممکن را به دست میاره.
ابتدا توضیح میدیم که در حالت بهینه چه انتظاری باید از امتیاز خودمون داشته باشیم. دقت کنید که در هر صورت اگر بازی را تا ته ادامه بدیم امتیاز ما ۰ خواهد بود برای همین هیچ وقت با امتیاز منفی از بازی خارج نمیشیم. به صورت شهودی، اگر یک سکه را n بار بندازیم، به احتمال نزدیک به ۱ اختلاف تعداد شیر ها و تعداد خط ها در بازی بین ۰ و n√ خواهد بود. برای همین نباید انتظار داشته باشیم که هیچ استراتژی بتونه امتیاز خیلی بیشتر (مثلا ضریب خطی از تعداد گوی ها) برای ما به دست بیاره. قبل از توضیح بیشتر اول دو مدل استراتژی که در کامنت ها بهشون اشاره شد را توضیح میدیم
- اولین استراتژی این هست که اونقدری بازی را ادامه بدیم که امتیاز ما به یک عدد خاص برسه یا این که گوی ها تمام بشن. این روش تقریب خوبی از امتیاز بهینه را برای ما به دست میاره. در نمودار پایین، شما میتونید ببینید به ازای هر عدد خاص برای حد توقف، میانگین امتیاز ما چقدر خواهد بود. بیشترین امتیازی که میتونیم با این روش به دست بیاریم برابر هست با ۱۳٫۵۶ که با حد توقف ۲۲ به دست میاد. این مقدار حدود ۸۲ درصد امتیاز بهینه هست.
- دومین استراتژی این هست که برای n مرحله بازی را ادامه بدیم، اگر امتیاز ما بعد از n مرحله مثبت بود همون جا توقف کنیم، در غیر این صورت تا انتها بازی را ادامه بدیم. در این صورت نمودار امتیاز ما بر حسب n به این صورت خواهد بود که در بهترین حالت امتیاز میانگین ما برابر با 8.92 میشه که با n=1000 به دست میاد. این عدد حدود ۵۴ درصد امتیاز بهینه هست
- شهود استراتژی ما این هست که مهم ترین عامل برای این که تشخصی بدیم آیا باید توقف کنیم یا نه این هست که چقدر تعداد گوی های سفید باقی مونده از تعداد گوی های سیاه باقی مونده بیشتر هستند. با توجه به توضیحات بالا،این رقم تابعی از رادیکال تعداد سکه های باقی مونده باید باشه برای همین ما از رادیکال تعداد سکه های سیاه باقی مونده برای این کار استفاده میکنیم