مسابقه شماره ۲۰۸
سوال
روباتی روی خطوط یک جدول 3 × 3 با خطوط افقی و عمودی حرکت می‌کند. طی کردن هر پاره خط به طول 1 افقی 1 ثانیه و هر پاره خط به طول 1 عمودی 2 ثانیه طول می‌کشد. می‌خواهیم روبات را به گونه‌ای برنامه‌ریزی کنیم که از یک نقطه شروع کند , از روی تمامی پاره خط‌های جدول عبور کند (می‌تواند از مسیرهای تکراری هم عبور کند) و به جای اولش برگردد. انجام این کار حداقل چند ثانیه طول می‌کشد؟ (مثلا در شکل زیر طی کردن مسیر مشخص شده 5 ثانیه طول می‌کشد.)
پاسخ
تعداد پاره خط‌های افقی 12 و نیز تعداد پاره خط‌های عمودی نیز 12 می‌باشد , بنابراین اگر از هر پاره خطر فقط یک بار عبور کنیم مدت زمان لازم 2 × 12 + 1 × 12 ؛ یعنی 36 ثانیه خواهد بود. اما شرط لازم برای آن که بتوان یک گراف را بدون برداشتن قلم از روی کاغذ و با عبور از هر یال دقیقا یک با چنان رسم کرد که نقطه‌ی پایان همان نقطه‌ی شروع باشد , آن است که درجه‌ی همه رئوس آن زوج باشد که در گراف رسم شده درجه‌ی 8 راس ؛ یعنی رئوس N , L , I , H , E , C , B و O فرد بوده و به ازای هر دو راس فرد که به یکدیگر وصل هستند یک حرکت اضافی لازم است. اگر حرکت به صورت زیر باشد , مدت زمان لازم 42 ثانیه خواهد بود.
A - B - F - G - C - B - C - D - H - G - K - L - H - L - P - O - K - J - N - O - N - M - I - J - F - E - I - E - A