معمای پل و مشعل

آشنایی با معماهای مشهور و تلاش برای حل آن‌ها یکی از راهکارهای مفید برای تقویت مهارت حل مسأله به شمار می‌رود. اگر مایلید این مهارت کاربردی در برنامه نویسی و طراحی الگوریتم را در خود تقویت کنید یا به عنوان فردی عادی می‌خواهید با یک معمای فکری آشنا شوید و یا برای استخدام در یک شرکت به مصاحبه دعوت شده‌اید بد نیست با معما یا مسأله پل و مشعل یا پل و چراغ قوه (Bridge and torch problem) آشنا شوید.

مسأله پل و مشعل به زبان ساده

تصور کنید چهار نفر می‌خواهند برای رفتن به آن سوی رودخانه از روی یک پل عبور کنند. این افراد را با حروف A, B, C و D نامگذاری می‌کنیم. با این فرض که A در مدت 1 دقیقه، B در 2 دقیقه، C در 5 دقیقه و D در 8 دقیقه می‌تواند از روی پل عبور کند. از آنجایی که شب هنگام است عبور از پل بدون مشعل امکان‌پذیر نیست و این چهار نفر فقط یک مشعل دارند. از طرفی پل در هر لحظه توانایی تحمل حداکثر دو نفر را دارد. وقتی دو نفر با هم از روی پل عبور می‌کنند باید با سرعت فرد کندتر عبور کنند تا بتوانند با هم از نور مشعل استفاده کنند. حال اگر شعله مشعل فقط برای 15 دقیقه دوام بیاورد آیا تمام این چهار نفر می‌توانند از روی پل عبور کنند؟

پاسخ مسأله

برای رسیدن به کمترین زمان ممکن، ابتدا دو نفر سریع‌تر (نفرات A و B) در مدت 2 دقیقه با یکدیگر از روی پل عبور می‌کنند. سپس A به تنهایی همراه با مشعل در مدت 1 دقیقه به نقطه ابتدایی پل برمی‌گردد. او مشعل را به دوستان کندترش (یعنی C و D) در ابتدای پل می‌دهد و آن‌ها هم در مدت 8 دقیقه با مشعل از روی پل عبور می‌کنند. حالا همه به جز A در انتهای پل قرار دارند. در این مرحله B مشعل را به دست گرفته و در مدت 2 دقیقه تنها به ابتدای پل برمی‌گردد. در پایان نیز A و B مجددا در مدت 2 دقیقه به انتهای پل می‌روند. بنابراین هر چهار نفر توانستند ظرف 15 دقیقه به انتهای پل برسند.

در روشی مشابه می‌توانید فردی که به تنهایی برمی‌گردد را در عبور دوم با عبور چهارم جابجا کنید. به عبارت بهتر در مرحله دوم، B به ابتدای پل برگردد و در عبور چهارم نیز A به تنهایی به ابتدای پل برگردد.

به نظر شما استدلال پشت این راه حل چیست؟ خوشحال می‌شویم نظرات خود را در بخش دیدگاه ها با ما در میان بگذارید.