دو عدد تخم‌مرغ و یک ساختمان صد طبقه در اختیار شما قرار می دهند. قرار است که تخم مرغ ها را از طبقات مختلف به پایین پرتاب کنیم . خوشتان آمد ؟ عجله نکنید این قدرها هم که به نظر می آید آسان نیست .
هر دو تخم مرغ کاملا مشابه هم هستند ولی مشخص نیست که تخم مرغ های ما تا کجا مقاومت می کنند و با پرتاب از کدام طبقه می شکنند . پس هدف ما پیدا کردن بالاترین طبقه ای است که اگر تخم مرغ از آنجا پرتاب شود با برخورد به زمین نمی شکند. اگر تخم مرغی پرتاب شد و با برخورد با زمین نشکست ، میتوان دوباره آن را پرتاب کرد. اما در صورتی که تخم مرغ شکست دیگر کار ما با آن تمام است.
سوال این است: با چه استراتژی ای می توانیم با کمترین پرتاب تخم مرغ پاسخ دقیق را پیدا کنیم؟
فراموش نکنید که : شما می‌توانید در طول انجام این آزمایش هر دو تخم‌مرغ را بشکنید. ( خسیس نباشید 🙂 )
دقت کنید که : با توجه به اینکه معمای فوق ریاضی است، پاسخ دارای راه‌حل می‌باشد. پس همانند تست هوش ها یا معماهای منطقی به دنبال تناقض یا نکته انحرافی نباشید!!
بد نیست که قبل از رسیدن به جواب قدری درباره ی حالات دیگر مساله فکر کنیم.
فرض کنید که یک تخم مرغ داریم
با این که معمای اصلی شامل این مورد نمی شود، اما بیایید فرض کنیم که فقط یک تخم مرغ داریم.
همین که تخم مرغ ما شکست، کار تمام است . تخم مرغ دیگری نداریم. پس ما چاره ای نداریم جز این که از طبقه 1 شروع کنیم. اگر نجات پیدا کرد که چه خوب، ادامه می دهیم و می رویم طبقه دو و امتحان میکنیم. بعد طبقه 3 و … همینطور ادامه می دهیم تا بالای برج. به محض این که تخم مرغ شکست، به جواب مسئله خواهیم رسید. به طور مثال اگر تخم مرغ ما در طبقه 64 شکست، پس حتما می تواند از پرتاب از طبقه 63 جان سالم بدر ببرد. هیچ راه حل دیگری برای حالت یک تخم مرغی نیست. البته می توانیم طبقات را یکی در میان بالا برویم ولی در آن صورت اگر تخم مرغ در طبقه 28 شکست ، حاضر هستید که تضمین کنید تخم مرغ در پرتاب از طبقه 27 سالم می ماند یا نه ؟
در نظر داشته باشید که همیشه ممکن است تخم مرغ تا خود طبقه صدم سالم بماند و این یک جواب کاملا منطقی و قابل قبول برای مساله ی حاضر است.
فرض کنید تعداد کافی تخم مرغ داریم
حال اگر تعداد زیادی تخم مرغ ( یا حداقل به تعداد کافی ) در اختیارمان باشد چه استراتژی ای را انتخاب کنیم؟ در این مورد میخواهیم از ابزار مورد علاقه برنامه نویسان استفاده کنیم : درخت باینری
ابتدا به طبقه 50 میرویم و تخم مرغ را پرتاب میکنیم. چه بشکند یا نه فورا مساله ما نصف میشود. اگر شکست میدانیم جواب ما در نیمه پایینی ( طبقات 1 تا 49 ) است و اگر نشکست در نیمه بالایی ( طبقات 51 الی 100 ). در هر پرتاب جواب هایمان را نصف میکنیم تا به جواب مساله برسیم.
ریاضیدان های حاضر در جمع تماشاچیان سریع فریاد میزنند که جواب لازم برای تعداد پرتاب ها برابر است با n در صورتی که که 2 به توان n عددی باشد که کمی بزرگتر از تعداد طبقات ساختمان ما باشد .
خب متاسفانه عدد 100 برابر با هیچ کدام از توان های عدد 2 نیست . پس 100 را به سمت بالا گرد میکنیم. تا به نزدیک ترین توان عدد 2 برسیم . یعنی 128 . پس n برای این مساله خاص ما 7 می شود.
یعنی با استفاده از 7 پرتاب میتوانیم تا ساختمان 128 طبقه را هم حل کنیم. با 8 پرتاب حتی یک ساختمان 256 طبقه را نیز می توان حل کرد.
طبق جوابی که بدست آوردیم تعداد تخم مرغ های شکسته میتواند متفاوت باشد. ممکن است هر 7 تخم مرغ بشکنند ( اگرجواب طبقه اول باشد در هر پرتاب یک تخم مرغ میشکند ) و ممکن است هیچ تخم مرغی نشکند ( در صورتی که جواب طبقه 100 باشد ، تخم مرغ از هر پرتابی جان سالم بدر میبرد )
و حالا دوباره دو تا تخم مرغ داریم
خیلی خب ، برمیگردیم به مساله اصلی که دو تخم مرغ بود. همانطور که در بالا مشاهده کردیم در بدترین حالت با استفاده از روش درخت باینری ممکن است تا هفت تخم مرغ فدای این آزمایش بشود. پس حالا که فقط دو تخم مرغ داریم دیگر آن روش به کارمان نمی آید .
تصور زیادی لازم ندارید تا متوجه بشوید روش باینری اصلا مناسب ما نیست. یک مثال برایتان میزنم. ابتدا تخم مرغ را در طبقه 50 پرتاب میکنیم و مشاهده میکنیم میشکند. جواب مساله ما نصف میشود ولی باید از طبقه 1 شروع به پرتاب کنیم. در بدترین حالت اگر جواب ما طبقه 49 باشد ، نیاز به 49 پرتاب دیگر داریم که با پرتاب قبلی میشود 50 پرتاب. فکر کنم که روشی باشد که بتوانیم بهتر از این ها کار کنیم . بد نیست که کمی دلمان باری تخم مرغ های بیچاره بسوزد …
یک روش این است که پرتاب اولمان را در طبقات ضریب 10 انجام بدهیم ( مثلا در طبقه ی 30 بشکند ) و بعد با تخم مرغ بعدی جواب دقیق را از بین پیدا کنیم ( مثلا طبقات 21 تا 29 را با تخم مرغ دوم امتحان کنیم) .
اگر پرتابهایمان را ده طبقه ای انجام دهیم چه میشود؟ ابتدا از طبقه 10 پرتاب میکنیم، اگر نشکست میرویم سراغ طبقه 20، سپس 30 و همینگونه ادامه میدهیم تا تخم مرغ بشکند. به محض اینکه تخم مرغ شکست میدانیم پاسخ باید میان 9 طبقه زیرین باشد. پس 9 طبقه پایین میرویم و طبقات را یکی یکی بالا میاییم تا جواب را پیدا کنیم.
این روش قطعا یک پیشرفت است، ولی بدترین حالت این استراتژی چیست ؟ تصور کنید که طبقات را ده تایی بالا میرویم و اولین تخم مرغ در طبقه 100 میشکند. تا اینجای کار 10 پرتاب انجام دادیم. اکنون میدانیم جواب ما بین طبقات 91 تا 99 است و یکی یکی از آن ها بالا میرویم. در بدترین حالت ممکن است جوا ما طبقه 99 باشد که در این صورت 9 پرتاب برای فهمیدن آن لازم داریم که با پرتاب های قبلی در مجموع میشود 19 پرتاب.
یک پیشرفت عالی . اما …
آیا میتوانیم بهتر عمل کنیم؟
با تفکر در مورد استراتژی 10 طبقه ای به این نتیجه میرسیم با اینکه درست است که در بدترین حالت 19 پرتاب داریم اما ممکن است در بعضی حالات تخم مرغ در همان طبقه 10 بشکند که در این صورت فقط 10 پرتاب به صورت ماکزیمم نیاز داریم. در واقع ما برای همه ی پاسخ های مسئله به تعداد یکسانی پرتاب نیاز نداریم !
با علم به این مورد ، چه می شود اگر به جای طبقه دهم، به طور مثال، از طبقه یازدهم شروع کنیم؟ در صورتی که تخم مرغ شکست باید به جای 9 طبقه ، جوابمان را میان 10 طبقه جستجو کنیم، اما اگر نشکست یک طبقه بیشتر از دور خارج کرده ایم.
خیلی خب حالا اگر از طبقه 12 شروع کنیم چه میشود؟ دقیقا بحث بالا را تکرار میکنیم. به این صورت که اگر شکست جواب بین 11 طبقه پایین آن است و اگر نه خب طبیعتا طبقات بیشتری را از مساله پاک کردیم و این به نفع ما است و باز به سراغ 12 طبقه بعدی میرویم و … یک لحظه دست نگه دارید !!! ….
اگر ابتدا از طبقه 12 شروع کنیم , بعد 24 ، بعد 36 ، بعد 48 ، 60 ، 72 ، 84 و بالاخره در طبقه 96 تخم مرغ بشکند، ما تا به حال 8 پرتاب را انجام دادیم و هنوز یازده طبقه را داریم که باید با تخم مرغ دوم چک کنیم که در بدترین حالت میشود یازده پرتاب و باز هم برمیگردیم به بدترین حالت سناریوی قبلی با 19 پرتاب !!!
ایراد این است که جواب هایی که طبقات پایینی باشند را میتوانیم سریع تر به دست بیاوریم ولی مشکل ما طبقات بالایی است. پس باید با استراتژی ای پیش بریم که اوضاع را برای شرایط مختلف یکسان کند.
در واقع مشکل اصلی روش ده طبقه این است که اوضاع پاسخی که مربوط به طبقات پایین تر باشد به طرز غیرمنصفانه ای با پاسخی که مربوط به طبقات انتهایی باشد فرق می کند . یعنی فرض کنیم که پاسخ ما طبقه ی 25 باشد . ما شروع می کنیم و تخم مرغ اول را آزمایش می کنیم . طبقه 10 … طبقه 20 … طبقه ی 30
و تخم مرغ اول در پرتاب سوم می شکند . حالا تخم مرغ دوم را امتحان می کنیم . 21 … 22 … 23 … 24 … 25 … بله تخم مرغ دوم هم شکست . یعنی ما برای پاسخی که مربوط به طبقه ی 24 باشد ( سه + پنج پرتاب نیاز داشتیم )
اما حالا پاسخی که مربوط به طبقه ی 80 است را امتحان می کنیم .
تخم مرغ اول 10 … 20 … 30 … 40… 50 … 60 … 70 … 80 … 90 … و تخم مرغ اول ما در پرتاب «هشتم» شکست . که حالا به طرز « ناعادلانه ای » اوضاع را از حالت قبل سخت تر کرد . حالا هر چقدر هم که در پرتاب تخم مرغ دوم شانس بیاوریم باز هم با شرایط وخیم تری روبرو هستیم .
با فرض این که طبقه ی 80 ( یعنی بهترین حالت) پاسخ باشد ، باز هم ما به ( هشت + یک ) پرتاب نیاز داریم که همچنان از حالت قبل بدتر است!!!
کاهش «ماکزیمم پشیمانی»
چیزی که ما نیاز داریم پاسخی است که حداکثر پشیمانی را به حداقل برساند. مثال های بالا به ما نشان داد که باید به سمت پاسخی برویم که برای پاسخ های احتمالی گوناگون راه حلی با عمق یکسان ( تعداد پرتاب تخم مرغ یکسان ) دهد.
امیدوارم اکنون متوجه شده باشید در صورتی که جواب ما در طبقات پایین باشد آزادی عمل بیشتری در بالا رفتن داریم ، ولی هرچه به بالای ساختمان نزدیک تر شویم ، پرتاب های بیشتری را برای رسیدن به آن مصرف کرده ایم، پس با پرتاب های تک طبقه ای جواب ما عدد بزرگتری می شود.
بیاید با هم کمی ریاضی کار کنیم.
تصور کنید ابتدا تخم مرغ را از طبقه n پرتاب میکنیم. اگر شکست باید n-1 طبقه قبلی را یکی یکی چک کنیم.
اگر نشکست ، به جای آنکه n طبقه بالا برویم ، باید n-1 طبقه بالا برویم. ( چرا؟ چون هنگامی که به حالت تک طبقه سویچ میکنیم یک پرتاب کمتر داریم. ) پس پرتاب بعدی ما میشود طبقه n + ( n – 1 ) به همین صورت اگر تخم مرغ ما نشکست دفعه بعد n-2 طبقه بالا میرویم و به طبقه (n) + ( n-1 ) + ( n-2 ) و سپس (n ) + ( n-1 ) + ( n-2 ) + ( n-3 ) و الی آخر
همینطور هر دفعه یکی از مبنای بالا رفتنمان کم میکنیم تا این که فقط یک طبقه برای بالا رفتن بماند. حالا جواب معادله زیر را برای 100 طبقه باید بیابیم.
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
این جمع ، همانطور که اکثر شما به یاد دارید ، ما را به سمت اعداد مثلثاتی هدایت می کند ( که منطقی به نظر می رسد ، زیرا از مبنای بالا رفتن هر بار یک واحد کم می کنیم ) و همچنین فرمول بالا را با ساده سازی میتوانیم اینگونه بنویسیم :
n (n+1) / 2 >= 100
این یک معادله درجه دوم است که ریشه مثبت آن می شود 13.651 ( که باید آن را گرد کنیم و جواب ما می شود 14 ، با فیلم جان مالکویچ سر و کار نداریم که !!! )
راه حل حالت دو تخم مرغی
اکنون ما تمامی اطلاعات لازم برای محاسبه راه حل بهینه برای دو تخم مرغ را داریم.
ابتدا از طبقه 14 شروع میکنیم ، اگر تخم مرغ جان سالم بدر برد 13 طبقه بالا میرویم و به طبقه 27 میرویم. سپس 12 طبقه بالا میرویم و به طبقه 39 میرسیم و همینطور الی آخر …
راه حل بهینه ی ما انجام پرتاب ها ، طبق جدول زیر است. هنگامیکه اولین تخم مرغ شکست به یک طبقه بالاتر از مرحله قبلی آن میرویم و طبقات را تک تک بالا میرویم تا جواب مساله بعدی را پیدا کنیم.
بیشترین تعداد پرتاب در این روش، برابر 14 است که حاصل مجموع تعداد پرتاب های مرحله تخم مرغ اول ( طبق مراحل موجود در جدول ) و مرحله تخم مرغ دوم ( تک تک طبقات ) است.
تازه حالت سه تخم مرغی را هم بلدیم
چرا با دو تخم مرغ مساله را تمام کنیم ؟ راه حل بهینه با وجود سه تخم مرغ چیست ؟ ( جرات دارید بگویید چهار ؟ پنج ؟ )
اوضاع با وجود سه تخم مرغ اندکی پیچیده میشود. ولی با یک تنفس عمیق و اندکی صبر میبینیم که مبانی کاهش ماکزیمم پشیمانی در اینجا هم کارساز است. ما نیاز داریم به گونه ای پرتاب تخم مرغ اولمان را انجام دهیم که در هر دو صورت شکستن یا نشکستن ، به گونه ای در مساله ما اثرگذار شود که ما را به همان حالت دو تخم مرغ برگرداند که در این صورت ما کاهش ماکزیمم پشیمانی را در آن فرا گرفته ایم.
خیلی خب ، محکم سر جایتان بنشینید ، شروع میکنیم …
اینجا دو راه حل داریم:
1- من ساعت ها و صفحه ها در این باره با انواع و اقسام فرمول ها این بحث را برایتان مفصل شرح دهم.
2- به جای گم شدن میان انبوهی از محاسبات و استدلالها ، به محاسبات من اعتماد کنید و جدول زیر را مشاهده کنید. شما کلیت موضوع را با توضیح مختصر من متوجه شده اید.
حضار یک صدا درخواست راه حل 2 را دارند. ما نیز اطاعت میکنیم.
http://3feed.ir
