وظیفه پازل ماه گذشته برای نجات بود پیشتازان فضا حزب سطح هشت نفره به رهبری سرمایه گذاری افسر ارتباطات ستوان اوهورا (با بازی مرحوم Nichelle نیکولز). خدمه توسط یک نژاد بیگانه، کاتناتی، در سیاره ای در زندان زندانی می شوند سحابی گردنبند. برای فرار، آنها باید احتمال انجام کاری را به حداکثر برسانند که در ابتدا به نظر می رسد فقط احتمال موفقیت ناگواری را ارائه می دهد.
خدمه XNUMX نفره در حالی که به طور موقت در یک اتاق مشترک نگهداری می شوند و در آنجا آزاد هستند تا با هم ارتباط برقرار کنند و استراتژی انجام دهند، از کار مطلع می شوند. بعد از چند ساعت، آنها یکی یکی به اتاقی به نام اتاق رولت هدایت می شوند. این اتاق دارای هشت دکمه است که در یک ردیف چیده شده اند که هر کدام برای پاسخگویی به خدمه متفاوت برنامه ریزی شده اند. برای گمراه کردن خدمه، هر دکمه به طور تصادفی با نام یکی دیگر از خدمه برچسب گذاری می شود. هر یک از خدمه مجاز است حداکثر چهار دکمه را به هر ترتیبی فشار دهد. هر زمان که دکمه ای را فشار دهند، خواهند دید که آن دکمه واقعا متعلق به چه کسی است. در چهار تلاش خود، آنها باید دکمه اختصاص داده شده به آنها را پیدا کنند. برای اینکه خدمه آزاد شوند، همه آنها باید در این کار موفق شوند. اگر حتی یکی از آنها شکست بخورد، همه اعدام خواهند شد. پس از اینکه یکی از خدمه تلاش خود را کامل کرد، آنها باید بدون هیچ راهی برای انتقال اطلاعات به هیچ یک از خدمه خود منزوی شوند.
شانس موفقیت ناچیز به نظر می رسد. اگر اعضای خدمه دکمهها را بهطور تصادفی انتخاب کنند، هر کدام یک شانس 1 در 2 برای یافتن دکمه خود خواهند داشت. شانس موفقیت هر هشت نفر فقط 1 در 256 یا حدود 0.4٪ است.
اما آنها مجبور نیستند دکمه ها را به طور تصادفی فشار دهند. یکی از راههای افزایش احتمال موفقیت میتواند یکنواخت کردن فشار دادن همه دکمهها به نحوی باشد. این ما را به اولین سوال معمایی ما می رساند.
پازل 1
اگر مطمئن شوند که هر دکمه به طور مساوی فشار داده می شود (به جای فشار دادن هر چهار دکمه به طور تصادفی) چقدر می توان احتمال بقای خدمه را افزایش داد؟
راب کورلت و JPayette این را به خوبی پاسخ دادند، همانطور که آنها تمام سوالات دیگر را انجام دادند. در مورد ایده مرکزی گریزان پشت پازل های این ستون، راب کورلت، جی پیت و جونی سپانن آن را به زیبایی توصیف کرد، در حالی که ساشا بوگنون یک راه حل کامپیوتری ارائه کرد.
در اینجا پاسخ راب کورلت است:
یکی از راه های اطمینان از اینکه هر دکمه به تعداد مساوی فشار داده می شود این است که زندانیان را به دو گروه 4 تایی با اندازه مساوی تقسیم کنید.
هر گروه فقط دکمه های مربوط به اعضای گروه خود را فشار می دهد. بنابراین، اگر A، B، C و D همه در یک زیرگروه باشند، فقط دکمههای A، B، C و D را فشار میدهند.
این مشکل را به درخواست احتمال اینکه هر زندانی به گروه صحیح اختصاص داده شود تغییر میدهد، زیرا تضمین میشود که دکمه خود را در چهار یا کمتر فشار میدهند.
تعداد راههای جمعکردن گروه اول (و در نتیجه گروه دوم) با چهار نفر، تعداد راههای انتخاب 4 از 8 است که C(8, 4) = 70 است. بنابراین، تعداد کل راههای تخصیص همه افراد به دو گروه 70 نفر است.
تنها یک تخصیص وجود دارد که به درستی هر زندانی را به گروه مناسب اختصاص می دهد و بنابراین احتمال اینکه همه در گروه مناسب باشند و همه زندانیان زنده بمانند 1/70 است که 3.66 برابر بهتر از 1/256 استراتژی قبلی است. [اما هنوز بسیار کوچک است: فقط 1.4٪ شانس.]
پازل 2
راهی برای بهبود شانس بد اصلی بیش از 90 برابر، به حدود 36.5٪ وجود دارد که معجزه آسا به نظر می رسد! این استراتژی شامل استفاده از حلقهها یا زنجیرهای از حدسها است - از این رو به سحابی گردنبند و کاتناتی اشاره میشود.کاتنا لاتین به معنای زنجیره است). در شکل اصلی استراتژی، هر یک از خدمه با فشار دادن دکمه ای که نام خود را دارد شروع می کند، سپس به دکمه ای می رود که نام یکی از اعضای خدمه را دارد که اولین دکمه واقعاً به آن تعلق داشت، و به همین ترتیب، زنجیره ای از نام ها را ایجاد می کند.
بیایید ببینیم این در عمل چگونه کار می کند. در نمودار، دکمه ها با برچسب آنها به رنگ سفید نشان داده شده اند. حروف آبی رنگ زیر صاحبان واقعی دکمه ها را نشان می دهد. هنگامی که اولین خدمه، A، وارد اتاق رولت می شود، ابتدا دکمه A را فشار می دهد. این دکمه C است، بنابراین او دکمه C را در مرحله بعد فشار می دهد، سپس دکمه E و در نهایت دکمه F، که در واقع دکمه خود A است، بنابراین او با موفقیت آن را در چهار تلاش پیدا کرده است. توجه داشته باشید که دکمه های ACEF یک حلقه بسته از چهار دکمه تشکیل می دهند. هنگامی که اعضای خدمه C، E و F به نوبت میرسند، آنها نیز همان حلقه بسته را دور میزنند، از مکانهای مربوطه خود شروع میکنند و همچنین دکمههای خود را در چهار تلاش پیدا میکنند.
این چیدمان همچنین دارای دو حلقه کوچکتر از دو دکمه است: BD و GH. این چهار خدمه دکمه های خود را در دو بار تلاش پیدا خواهند کرد. بنابراین، با این ترتیب، همه اعضای خدمه موفق خواهند شد و آزادی خود را به دست آورده اند. واضح است که اگر چیدمان فقط شامل حلقه هایی به طول 4 یا کمتر باشد، همه خدمه موفق خواهند شد و آزاد خواهند شد. از طرف دیگر، اگر یک حلقه 5 یا بیشتر وجود داشته باشد، تمام اعضای خدمه در آن حلقه در چهار بار تلاش نمیکنند دکمه خود را پیدا کنند و خدمه اعدام میشوند. برای اینکه احتمال موفقیت را پیدا کنیم، میتوانیم احتمال داشتن یک حلقه 5، 6، 7 یا 8 را پیدا کنیم، آنها را جمع کنیم و آن مجموع را از 1 کم کنیم. دکمه ها، تنها می تواند یک حلقه با 5، 6، 7 یا 8 عضو وجود داشته باشد.
8 تا هستند! روش های مختلف برای چیدمان هشت دکمه اما وقتی حلقه می سازیم، همان حلقه هشت مورد از این ترتیبات را به حساب می آورد (ABCDEFGH همان حلقه BCDEFGHA را تشکیل می دهد که همان CDEFGHAB و غیره است). بنابراین احتمال داشتن یک حلقه به اندازه 8 (8!/8)/8! است که به سادگی 1/8 است. به همین ترتیب، احتمال داشتن حلقه با اندازه 7 1/7، اندازه 6 1/6 و اندازه 5 1/5 است. بنابراین، احتمال موفقیت برای خدمه بی باک ما 1 - (1/5 + 1/6 + 1/7 + 1/8)، یا 36.5٪ است، همانطور که قبلا ذکر شد.
استراتژی فوق برای هر تعداد زندانی کار می کند، و با افزایش آن تعداد، شانس نسبت به رویکرد تصادفی به سرعت افزایش می یابد. برای چهار زندانی حدود هفت برابر، برای شش 24 برابر، برای هشت 93 برابر و شگفتانگیز (3.8 × 10) است.29)- برابر برای 100 زندانی. کلید درک این افزایش عظیم این است که این روش موفقیت یا شکست هر یک از اعضای گروه را به سایرین پیوند می دهد. تا حد زیادی، همه آنها با هم موفق می شوند یا شکست می خورند. احتمال موفقیت این گروه نسبت به یک نفر خیلی کاهش نمی یابد، زیرا با افزایش تعداد زندانیان بدون محدودیت، تنها از 50 درصد برای یک زندانی به 30.69 درصد کاهش می یابد. از سوی دیگر، احتمال موفقیت یک رویکرد تصادفی یا حتی یک رویکرد «فشار دکمههای زوج» به سرعت برای تعداد کمی از زندانیان به صفر نزدیک میشود.
اگر منطق پشت این استراتژی هنوز مبهم به نظر می رسد، در اینجا تجزیه و تحلیل مشکل 100 زندانی در این است. ویدیوی عالی از Veritasium.
پازل 3
این پازل در مورد ستوان اوهورا بود که یک بازی دوران کودکی را به یاد می آورد، که در اصل همان پازل بود، اما برای شش نفر. به عنوان یک اشاره، من پیشنهاد کردم مشکل را برای چهار نفر حل کنید. حالا که فرمول را داریم، به راحتی می توانیم احتمالات را محاسبه کنیم.
برای چهار نفر، احتمال اینکه طولانی ترین حلقه فقط 2 یا 1 باشد: 1 - (1/3 + 1/4) یا 41.7٪ با افزایش هفت برابری نسبت به انتخاب تصادفی است.
برای شش نفر، احتمال اینکه طولانی ترین حلقه 3، 2 یا 1 باشد: 1 − (1/4 + 1/5 + 1/6) یا 38.3٪ با افزایش بیش از 24 برابری نسبت به انتخاب تصادفی.
پازل 4
همانطور که داستان ما ادامه دارد، معلوم می شود که یکی از کاتناتی ها نسبت به آن بیزاری خاصی پیدا کرده است سرمایه گذاری خدمه و از راه دور آنها را زیر نظر دارند. او مشکوک است که آنها بر اساس نمودار اوهورا، استراتژی مؤثری ارائه کرده اند. او مصمم است که نقشه آنها را با لغزیدن به داخل اتاقک و تغییر عمدی ترتیب برچسب دکمه ها قبل از شروع رولت، خنثی کند. آیا او می تواند با موفقیت این نقشه را خنثی کند؟ طرف فرود باید به خصوص مراقب باشد که چه چیزی را پنهان کند؟
در اوایل بحث استراتژی خدمه، چشمان اوهورا ناگهان ریز شد. او علامتی به خدمهاش داد و به صحبت به زبان نیکولزی روی آورد و اعلام کرد: «لطفاً تمام بحثهای بعدی به نیکولزی است.» نیکولزی زبان جدیدی بود که اوهورا در اوایل زندگی حرفهای خود برای دور زدن استفاده از مترجمان جهانی ابداع کرده بود. او ادامه داد: "حتما متوجه آن کاتناتی مشکوک شده اید." او میتواند تلاش کند ما را خراب کند، بنابراین ما باید نقشهمان را اصلاح کنیم. این چیزی است که ما باید انجام دهیم…”
اوهورا طرح جدید را ترسیم کرد تا اینکه راضی شد که همه اعضای خدمهاش آن را به خوبی میدانند. سپس با نگاهی دور در چشمانش فکر کرد: «من نیکولز را به افتخار یک هنرپیشه نمادین قرن بیستم نامیدم. خوشحالم که اصرار کردم که Starfleet آن را در همه کشتیهای ما استاندارد کند.»
او به سمت خدمه برگشت. این همه افسران است. شما می دانید چه باید بکنید!"
ما دقیقا نمی دانیم که اوهورا به تیمش چه گفته است. اما JPayette و Rob Corlett ایده بسیار خوبی داشتند. این هم راب کورلت دوباره:
اگر کاتناتی شرور بشنود که آنها از این استراتژی استفاده می کنند، می تواند نام های نشان داده شده روی نمایشگر را تغییر دهد تا مطمئن شود که یک چرخه بیشتر از 4 وجود دارد.
برای شکستن این، زندانیان باید با یک دستور مخفی موافقت کنند که توالی را تصادفی می کند. آنها این کار را با گفتن چیزی مانند "اگر نام اوهورا را می بینید، به دکمه ای که چکوف مشخص شده است بروید. اگر نام چکوف را مشاهده کردید به دکمه اسمیت و غیره بروید.
به این ترتیب، سفارش مجدد توسط کاتناتی اهمیتی ندارد، زیرا تنها در صورتی کار می کند که بدانید خدمه چگونه به اسامی روی نمایشگرها پاسخ می دهند. آنها باید هر گونه سفارش مجدد را مخفی نگه دارند، در غیر این صورت دوباره ممکن است شکسته شود.
همانطور که دیدیم، اوهورا تضمین کرد که راز محفوظ بماند. هر یک از اعضای خدمه فقط باید از همان دستور مخفیانه استفاده می کردند و اطمینان حاصل می کردند که کاتناتی شیطانی نمی داند چیست. در واقع تغییر ترتیب توسط کاتناتی شیطانی در واقع احتمال موفقیت خدمه را افزایش داد!
این چیزی است که اتفاق افتاد. اوهورا اولین کسی بود که به اتاق رولت برده شد. سه دکمه را فشار داد. هیچکدام مال او نبود آیا او باید غمگین باشد یا خوشحال؟ نفسش را حبس کرد و چهارمش را فشار داد. او دکمه واقعی خود را پیدا کرده بود!
او می دانست که همه آنها نجات خواهند یافت.
پازل 5
با افزایش نامحدود اندازه طرف فرود، حداکثر درصد موفقیت به چه حد نزدیک می شود؟ آیا می توانید توضیح دهید که چرا این روش بسیار کارآمدتر از فشار دادن تصادفی دکمه است؟
JPayette نوشت:
تمام موارد فوق به طور مستقیم به یک خدمه 2 نفره تعمیم می یابدn اعضا حداکثر مجاز به فشار دادن هستند n دکمه ها. از پازل 2 استنباط می کنیم که شانس موفقیت آنها است
1- (مجموع تمام شد k میان n + 1 و 2n از 1 /k).
مجموع را می توان با انتگرال 1/ مقایسه کردx در بازه زمانی [n، 2n]، که به ما امکان می دهد ثابت کنیم که به عنوان n تا بی نهایت رشد می کند، احتمال بالا کاهش می یابد تا به 1-ln(2) ≈ 30.6% خیره کننده همگرا شود. [در واقع 30.69٪ تا دو رقم اعشار.]
راب کورلت افزود:
اگر ادغام را نمی دانید، می توانید به سرعت با محاسبه با استفاده از صفحه گسترده به یک پاسخ تقریبی برسید. من یکبار به 0.307 رسیدم n به حدود 750 رسید که تا 3 رقم اعشار دقیق است.
ما قبلاً در بالا توضیح داده ایم که چرا این روش کار می کند. همه حلقه های بیشتر از 1 توسط چندین خدمه مشترک هستند. بنابراین موفقیت ها و شکست های آنها ارتباط زیادی با هم دارند. این تصویری از اصل "همه برای یکی، و یکی برای همه" است. مستقیماً از دفترچه راهنمای Starfleet!
با تشکر از همه همکاران ما. JPayette و Rob Corlett هر دو پاسخ های ارزشمندی را ارائه کردند که باعث شد این ستون راه حل تقریباً اضافی به نظر برسد. افسوس، من باید به قانون خود مبنی بر انتخاب یک برنده در هر ستون پازل پایبند باشم. جایزه Insights به منظور قدردانی از مشارکت در اینجا و در پازل قبلی به JPayette می رسد. تبریک می گویم! راب کورلت، مشارکت شما فراموش نخواهد شد.
ماه آینده شما را برای اطلاعات آماری جدید می بینم!