سوال)

5 نفر با وزن‌های 80 و 80 و 40 و 30 و 20 کیلوگرم در یک طرف رودخانه ایستاده‌اند و قایقی دارند که ظرفیت آن 80 کیلوگرم است. آیا آنها می‌توانند با استفاده از این قایق به سوی دیگر رودخانه بروند؟ (در هر بار رد شدن قایق از رودخانه باید حداقل یک نفر برای هدایت آن در قایق باشد.)

پاسخ)

الگوریتم حرکت به صورت زیر می‌باشد ( در ابتدا فرض می‌کنیم همه در سمت چپ رودخانه باشند) :

20 و 30 با هم به سمت راست رفته و 30 پیاده شده و 20 بر می‌گردد.
20 و 40 با هم به سمت راست رفته و 40 پیاده شده و 20 بر می‌گردد.
20 در سمت چپ پیاده شده و 80 به سمت راست رفته پیاده شده و 30 سوار می‌شود.
30 به سمت چپ امده , پیاده می‌شود و 80 سوار شده به سمت راست ‌می‌رود.
80 در سمت راست پیاده شده و 40 سوار شده به سمت چپ می‌آید.
40 نفر 20 را سوار کرده , به سمت راست آورده , آن را پیاده می‌کند و به سمت چپ بر می‌گردد و نفر 30 را سوار کرده و با هم به سمت راست رفته و در آنجا پیاده می‌شوند.