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