مسئله کلاسیک ازدواج؛ دل نوشته ای در لباس ریاضیات
مرد جوانی می‌خواهد ازدواج کند. او تصمیم می‌گیرد به خواستگاری حداکثر ۱۰۰ دختر خانم برود. او پس از آشنا شدن با هر دختر تصمیم می‌گیرد که با او ازدواج کند یا به خواستگاری دختر دیگری برود. هر بار که دختری را نپذیرد دیگر نمی‌تواند دوباره از آن دختر خواستگاری کند. نهایتاً او باید فقط یک دختر را انتخاب و با او ازدواج کند.
نکتهٔ جالب این مسئله این است که مرد جوان می‌تواند به گذشته بنگرد ولی هیچ اطلاعی از آینده ندارد. او در هر لحظه می‌تواند بگوید:
دختری که اکنون از او خواستگاری کرده‌ام زیباتر و سازگارتر از همهٔ دختران قبلی است.
بر این اساس ممکن است تصمیم بگیرد که با این دختر ازدواج کند یا ممکن است فکر کند که:
این دختر عالی است ولی دل به دریا می‌زنم و به امید اینکه به زودی همسر بهتری پیدا کنم با او ازدواج نمی‌کنم.
مسئله ازدواج تعیین بهترین راهکار برای این مرد جوان است.
مسئله ازدواج یک مسئله در ریاضیات شمارشی است. هدف از مطرح کردن امروز آن نه مطرح کردن سؤالی در ریاضیات است. بل یاد‌آوری یک مسئله کلاسیک و مقایسه آن با شرایط امروز خودم است.
تذکر
نویسنده در این نوشته به مقدار زیادی از کتاب فنون مسئله حل کردن کرانتس بهره برده است. ترجمهٔ فارسی مهران اخباری‌فر از این کتاب توسط انتشارات فاطمی به چاپ رسیده است.
اما من ...
مدت‌هاست که فرصت‌ها را یکی پس از دیگری رها می‌کنم. هر بار که می‌خواهم فرصتی را رها کنم و به استقبال آینده بروم با خودم می‌گویم:
این مورد خیلی عالی است ولی دل به دریا می‌زنم و به امید اینکه به زودی فرصتی بهتر پیدا کنم این یکی را رها می‌کنم!
و پس از رها کردن آن، در نگرانی از آنچه در آینده پیش خواهد آمد، با خودم می‌گویم:
قوی باش مرد! تو فرصت‌های بهتر از این رو از دست دادی ...
راهکار یکی یکی رها کردن فرصت‌ها مرا می‌ترساند. سال‌ها پیش محکم‌تر بودم. با استقامت به مسیرم ادامه می‌دادم. اما حالا بیش از پیش می‌ترسم ...
اما جواب ...
کرانتس برای اینکه احساسات را در مسئله دخالت ندهد، مسئله را به صورت زیر بیان می‌کند:
در کلاهی ۱۰۰ نوار کاغذی ریخته‌ایم و روی هر نوار عددی طبیعی نوشته‌ایم. ( توجه کنید که عددهای روی نوار فقط عددهای ۱ تا ۱۰۰ نیستند، بلکه هر عدد طبیعی ممکن است روی نوارها نوشته شده باشد.) عددها لزوماً ترتیب یا الگوی مشخصی ندارند. روی هیچ دو نواری یک عدد نوشته نشده است و بنابراین نواری هست که عدد روی آن بزرگترین عدد است.
شخصی که هیچ اطلاع قبلی از اینکه چه عددهایی روی نوارها نوشته‌ایم ندارد ( ولی می‌داند که ۱۰۰ نوار در کلاه است) با چشمان بسته نوارها را یکی یکی از کلاه بیرون می‌آورد. او هر بار عدد روی نوار را نگاه می‌کند و تصمیم می‌گیرد که بازی را تمام کند و به اندازهٔ عدد روی نوار پول بگیرد یا اینکه به بازی ادامه دهد و نوار دیگری را بیرون آورد.
توجه کنید که بازیکن هر نوار را نگاه می‌کند و سپس تصمیم می‌گیرد که بازی را تمام کند یا ادامه دهد. او می‌تواند به پیش برود ولی نمی‌تواند به عقب برگردد. اگر تا وقتی که ۱۰۰ اُمین نوار را بیرون می‌آورد انتخابی نکرده باشداجباراً باید عدد روی ۱۰۰ اُمین نوار را بپذیرد و به اندازهٔ آن پول بگیرد! (ترسناک‌ترین قسمت ماجرا همین جاست!)
بهترین راهکار برای بازیکن چیست؟ ( در اینجا بهترین راهکار یعنی اینکه بازیکن بتواند بیشترین پول ممکن را بگیرد.)
استیون جورج کرانتس با شرمندگی اعتراف می‌کند که وقتی اولین بار این مسئله را شنید، لحظه‌ای اندیشید و گفت:
هیچ راهکاری وجود ندارد!
این مشکل تا حدی ناشی از این بود که او درست درک نکرده بود که راهکار چیست و البته مشکل اصلی این بود که او فکر نمی‌کرد!
همچنان که سیبیا حتی بعد از خواندن راه حل کرانتس با خودش اندیشید:
راه حل کرانتس فقط به درد خودش می‌خورد!
راه حل کرانتس
پیشاپیش فرض می‌کنیم که راهکار به شکل زیر خواهد بود: بازیکن تعداد مشخصی از نوارها، مثلا $ k $ نوار را بیرون می‌آورد و به دقت به عددهای روی نوارها توجه می‌کند. پس از بیرون آوردن $k$ نوار، بازیکن باید نوار بعدی را که بیرون می‌آورد تعیین کند که این نوار در ویژگی $P$ صدق می‌کند یا نه و ویژگی $P$ باید تعیین شود. بعداً بحث خواهیم کرد که چرا توجه کردن به این نوع راهکار معقول است.
محل نزاع اصلی سیبیا و کرانتس همین جاست. سیبیا و کرانتس آبشان در یک جوی نخواهد رفت! جلوتر هیچ گاه کرانتس بحث نکرده است که چرا توجه به ان نوع راهکار معقول است!
راه حل
اولین نواری را که بیرون می‌آید نوار ۱ می‌نامیم، دومین نوار را نوار ۲ می‌نامیم و همین طور تا آخر ...
هدف ما بهینه کردن مقدار پولی است که بازیکن دریافت می‌کند. هر راهکاری را که منجر به انتخاب $(l+1)$ اُمین نوار، $ l \geq k $ ، شود می‌توان بهبود بخشید. برای این کار بزرگترین عدد نوشته شده روی نوارهای $1$ ، $2$ ، ... و $l$ را $M$ می‌نامیم.و آن را به خاطر می‌سپاریم. سپس نوار بعدی را که عددی بزرگتر از $M$ روی آن نوشته شده است انتخاب می‌کنیم. ( اگر چنین نواری بیرون نیاید بازیکن مجبور است به آخرین نوار قناعت کند.) با استفاده مکرر از این مطلب در می‌یابیم که با فرضی که در بند قبل از شروع راه‌حل بیان کردیم، بهترین راهکار این است که بزرگترین عدد نوشته شده روی نوارهای $1$ ، $2$ ، ... و $k$ را که آن را $M$ می‌نامیم به خاطر بسپاریم و سپس نوار بعدی را که عددی بزرگتر از $M$ دارد انتخاب کنیم.
بعد از تعیین این طرح کار ما انتخاب بهترین مقدار ممکن برای $k$ است. بزرگترین عدد ( بین همهٔ $100$ نوار ) را $Q$ می‌نامیم و فرض می‌کنیم که $Q$ روی نوار $r+1$ نوشته شده باشد. بازیکن فقط در صورتی موفق به انتخاب این نوار می‌شود که دو شرط زیر برقرار باشد:
- $ r \geq k $ (چون مطابق راهکار ما $k$ نوار اول انتخاب نمی‌شوند؛ پس اگر $r < k$ آنگاه $(r+1)$ اُمین نوار که بزرگترین عدد را دارد انتخاب نمی‌شود.)
- بزرگترین عدد روی نوارهای از $1$ تا $r$ بزرگترین عدد روی نوارهای از $1$ تا $k$ نیز باشد. (چون اگر بزرگترین عدد روی نوارهای از $1$ تا $r$ که آن را $P$ می‌نامیم، بزرگتر از بزررگترین عدد روی نوارهای $1$ تا $k$ که آن را $M$ می‌نامیم، باشد آنگاه $P<Q$ ولی $P$ پیش از رسیدن به $(r+1)$ اُمین نوار انتخاب می‌شود.)
احتمال اینکه بزرگترین عدد، $Q$ ، روی نوار $(r+1)$ اُم (یا هر نوار مشخص دیگری) باشد $\frac{1}{100}$ است. احتمال یافتن نواری که عدد $Q$ روی آن است، به فرض اینکه نوار $(r+1)$ اُم باشد، $\frac{k}{r}$ است. پس روی هم رفته احتمال بردن بازی با انتخاب نواری که بزرگترین عدد ( $Q$ ) روی آن است به فرض اینکه نوار شامل $Q$ نوار $r+1$ اُم باشد و ما $r$ نوار اول را کنار بگذاریم و نوار $(r+1)$ اُم را انتخاب کنیم برابر است با $$ P_r= \frac{1}{100} \times \frac{k}{r} $$
مقادیر مجاز برای $r$ عبارتند از $r=k,k+1,...99$. پس احتمال بردن بازی با راهکار مشخص شده برابر است با
$$ P= \sum_{r=k}^{99}P_r$$
$$=\frac{k}{100} \sum_{r=k}^{99} {\frac{1}{r}} $$
کرانتس عبارت بالا را ساده و ساده تر می‌کند و می‌رسد به (برای دیدن اینکه چگونه این کار را می‌کند رجوع کنید به کتاب فنون مسئله حل کردن):
$$ P \approx \frac{k}{100} \ln (\frac{99}{k-1}) $$
بعد هم می‌گوید چون مثلاً حسابان بلد نیستیم، تابع $$ P(x) = \frac{x}{100} \ln (\frac{99}{x-1}) $$ را به کمک نرم‌افزار های جبری رسم می‌کنیم و مقدار بیشینه‌اش را پیدا می‌کنیم!
بیشینه در $x= \frac{100}{e}$ اتفاق می‌افتد که نزدیک ترین عدد صحیح به آن $37$ است. پس بازیکن باید $37$ نوار اول را بیرون بیاورد و سپس بزرگترین آنها را در نظر بگیرد و از نوار $38$ به بعد اولین نواری را که عددی بزرگتر از بزرگترین عدد $37$ نوار اول دارد انتخاب کند!
من مخالفم ...
اما راه حل کرانتس فقط به درد یک مسئله ریاضیات نظری می‌خورد! در زندگی من هیچ کاربردی ندارد. چرا؟
- لزوماُ بهترین انتخاب، انتخاب بهترین نیست. یک لحظه با خودتان تصور کنید:
۳۶ نوار اول را در آورده‌اید و با مبالغ ۱ تا ۳۶ دلار روبرو شده‌اید. نوار ۳۷اُم را بیرون می‌کشید: یک میلیارد دلار! چه پیشنهاد وسوسه کننده‌ای...
حالا اگر همین پیشنهاد به کرانتس بشود او رهایش می‌کند و به امید مبلغ بهتری نوار سی و هشتم را بیرون می‌کشد؟ آدم باید خیلی نادان باشد ...
یا بر عکس تصور کنید:
۳۷ نوار اول همه مبالغی زیر یک دلار بوده اند. نوار سی و هشتم را می‌کشید بیرون: یک دلار!
کرانتس همین یک دلار را می‌گیرد و بازی را تمام می‌کند؟
- این سبک راه‌حل های احتمالاتی به درد وقتی می‌خورد که قرار باشد این بازی را تعداد خیلی زیادی دفعه انجام دهید. برای یک بازی که فقط یک بار می‌خواهید آن را بازی کنید باید هوشمندی بیشتری به خرج دهید!
وقتی کرانتس عصبانی می‌شود...
با خودم تصور می‌کنم زمانی که کرانتس این نوشته را بخواند حتماً عصبانی می‌شود و فریاد می‌کشد:
مگر من کلاس مشاوره قبل از ازدواج گذاشته‌ام؟ من یک ریاضی دان هستم! تو اگر ریاضی نمی‌فهمی به جای خواندن کتاب‌های من از مشاوران پیش از ازدواج بهره ببر!
حق می‌گوید؛ جوابی برای گفتن ندارم.
کمی عذرخواهی
تابع $P(x)$ را به یاد بیاورید. به کمک نرم‌افزارهای جبری محاسبه کردیم که این تابع در $ x= \frac{100}{e} $ بیشترین مقدار خود را می‌گیرد. این بیشینه مقدار چه عددی است؟
$$ 0.374 $$ یعنی اگر شما این بازی را با استراتژی کرانتس بازی کنید به احتمال $37$ درصد بازی را خواهید برد. به یاد بیاورید که بُرد در نگاه کرانتس به معنای گرفتن بیشترین پول بود و شما به احتمال $37$ درصد بیشترین پول را خواهید گرفت.
اگرچه هنوز هم معتقد هستم که استراتژی کرانتس در جهان واقعی به درد نمی‌خورد اما $37$ درصد واقعاً عالی است. شایستهٔ تقدیر است...
نوشته شده در دوشنبه ۳۰ بهمن ۱۴۰۲
حرفی؟ سخنی؟
دوست خوبم سلام! پیام شما در این صفحه منتشر نمی‌شه برای همین اگه دوست داری جواب پیامی که برام می‌نویسی رو بگیری حواست باشه که ایمیل معتبری وارد کنی. تنها راه ارتباطی من با شما همین ایمیلیه که اینجا وارد می‌کنی. پیشاپیش ممنونم که نظرت رو می‌گی.