فلش‌ها
در هر یک از خانه‌های یک جدول $1000 \times 1000$٬ یک فلش رسم شده است. هر فلش یکی از هشت جهت زیر را نشان می‌دهد.
دو خانه از این جدول مجاور به حساب می‌آیند٬ اگر دست کم در یک راس مشترک باشند. (بنابراین هر یک از خانه‌های این جدول حداکثر ۸ خانه‌ی مجاور دارد.) می‌دانیم که جهت فلش‌های کشیده شده در دو خانه‌ی مجاور حداکثر به اندازه‌ی ۴۵ درجه با هم اختلاف دارند. یعنی برای مثال اگر فلش یک خانه به شکل ۱ (مطابق با شکل فوق) باشد٬ فلش هر یک از خانه‌های مجاورش به یکی از سه شکل ٬۲٬۱ یا ۸ است.
الف) از یک خانه‌ی دل‌خواه این جدول شروع به حرکت می‌کنیم و در هر مرحله٬ به یکی از خانه‌های مجاور خانه‌ای که در آن هستیم٬ می‌رویم. با توجه به شرایط مسئله٬ جهت فلش خانه‌ای که به آن می‌رویم نسبت به جهت فلش خانه‌ای که در آن هستیم٬ به اندازه‌ی ۴۵-٬ ٬۰ یا ۴۵ درجه در جهت عقربه‌های ساعت اختلاف دارد. مقدار این اختلاف درجه را یادداشت می‌کنیم. برای مثال٬ اگر شکل زیر نشان‌دهنده‌ی قسمتی از جدول باشد و به ترتیب خانه‌های ۱ تا ۹ را طی کرده و به خانه‌ی ۱ بازگردیم٬ به ترتیب عددهای$ ٬۰٬۰٬-۴۵٬۴۵٬۰٬۰٬۴۵٬-۴۵$ و ۰ را یادداشت خواهیم کرد.
ثابت کنید اگر پس از طی چند مرحله به خانه‌ای که حرکت را از آن‌جا آغاز کرده بودیم برسیم٬ مجموع عددهایی که یادداشت کرده‌ایم٬ برابر با صفر خواهد بود.
پاسخ
به مجموعه ای از فلش ها که هم جهت هستند و از هر کدام توسط مسیری از اعضای مجاور بتوان به دیگری رفت و با اضافه کردن هر فلش دیگر به این مجموعه دیگر این شرط برقرار نباشد یک مولفه می گوییم. ( بین هر دو فلش هم جهت و مجاور یال بگذارید، مولفه های همبندی گراف ساخته شده، همان مولفه های مذکور است. )
کوچک ترین دوری که حکم مساله را نقض می کند را در نظر بگیرید، راس مبدا این دور درون مولفه ای قرار دارد، این دور نمی تواند تماما درون همین مولفه باشد چون اگر این اتفاق بیفتد تمام اعدادی که یادداشت کرده ایم ۰ می شود و بنابراین جمعشان نیز ۰ می شود و با فرض که این دور حکم مساله را نقض می کند در تناقض است.
همچنین می دانیم که فقط هنگام شروع و پایان در مولفه آغاز می رویم چون اگر جایی این وسط به مولفه آغاز برگردیم یکی از این قسمت ها باید جمع نا صفر داشته باشد و کوچک تر نیز هست پس با فرض ما که کوچک ترین دوری که مساله را نقض می کند را انتخاب کرده بودیم در تناقض است.
حال مولفه ای که بلافاصله که از این مولفه خارج می شویم به آن می رویم را در نظر بگیرید و اسمش را مولفه الف بگذارید. آخر کار که دوباره به مولفه شروع بر می گردیم، قبلش حتما به مولفه الف می رویم زیرا مولفه ای وجود ندارد که مجاور مولفه شروع باشد و بتوان بدون رد شدن از مولفه شروع، از مولفه الف به آن رفت. پس ادعای ما درست است اما این ادعا با فرض کوچک ترین بودن در تناقض است. زیرا می توانیم نقطه ای از مولفه الف را به عنوان شروع انتخاب کنیم و از آن دور خود را شروع کنیم
ب) حال می‌خواهیم در این جدول با توجه به جهت فلش‌ها حرکت کنیم؛ به این صورت که از یک خانه‌ی دل‌خواه جدول شروع می‌کنیم و در هر مرحله اگر در خانه‌ی $a$ باشیم٬ به خانه‌ی مجاوری می‌رویم که فلش $a$ به سمت آن اشاره می‌کند. اگر $a$ کنار جدول باشد و فلش آن به سمت خارج از جدول اشاره کند٬ از جدول خارج می‌شویم. ثابت کنید که با این نحوه‌ی حرکت بالاخره از جدول خارج خواهیم شد.
پاسخ
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
