SABB گفت
در شوامبرانیا n شهر وجود دارد و هر دو شهر با یک جاده به هم وصل اند. این جاده ها یکدیگر را قطع نمی کنند. در صورت لزوم برخی از آن ها از طریق پل از رو یا زیر برخی دیگر رد می شوند. جادوگر بدجنس (!) جاده ها را طوری یک طرفه اعلام کرده است که اگر کسی از شهر بیرون برود دیگر قادر نیست به آن برگردد.
الف) ثابت کنید میتوان چنین کاری کرد.
ب) ثابت کنید شهری وجود دارد که میتوان از آن به هر شهر دیگر رفت و شهری وجود دارد که نمی توان از آن خارج شد.
ج) ثابت کنید یک راه و فقط یک راه وجود دارد که از همه شهر ها میگذرد.
د) ثابت کنید جادوگر به !n حالت می تواند به هدفش برسد.
(تورنمنت شهرها - 1983)
قسمت الف ـ همه ی جاده های شهر ۱ را به سمت خارج از شهر جهت می دهیم و بعد همه ی جاده های شهر ۲ که باقی مانده اند را به خارج می زنیم و همینطور ادامه می دهیم. این یک روش برای انجام این کار است پس می توان چنین کاری کرد
قسمت ب ـ می دانیم که گراف دور جهتدار ندارد. فرض کنیم هر شهری حداقل یک ورودی داشته باشد. ــ یعنی یک جاده به سمت داخل شهر آمده باشد ــ در این صورت طولانی ترین مسیر جهتدار گراف را در نظر می گیریم. شهر ابتدایی این مسیر باید یک ورودی داشته باشد اگر جاده ای که به این شهر وارد شده از یکی از شهرهای خارج از مسیر آمده باشد با ماکسیمال بودن مسیر در تناقض است و اگر از داخل آن آمده باشد با بی دور بودن گراف تناقض ایجاد می کند پس حتما شهری هست که هیچ ورودی ندارد پس جاده های این شهر به همه ی شهر ها می روند و از آن می شود به هر شهری رفت. قسمت دوم هم همینطوری اثبات می شه فقط به جای ابتدا به انتهای مسیر توجه می کنیم
قسمت ج - ثابت می کنم فقط همونطوری که تو قسمت الف گفتم می تونیم این کار رو بکنیم. اول ثابت می کنم به ازای هر درجه ی خروجی معتبر یک شهر با آن درجه ی خروجی وجود دارد. ثابت کردیم شهری وجود دارد که درجه ی خروجی آن n-1 است اگر این شهر و همه ی جاده هایش را کنار بگذاریم به فرض استقرا می رسیم. ــ حوصله ی توضیح دادن ندارم بدیهیه دیگه ــ پس شهر با هر درجه ای وجود داره. یعنی مثل قسمت الف! حالا یک راه را در نظر بگیرید که از همه ی شهرها بگذرد این راه باید در شهری با درجه ی خروجی صفر تمام شود. اگر این شهر را کنار بگذاریم درجه ی خروجی یک شهر دیگر صفر می شود و با ادامه ی این روند مسیر به صورت یکتا تعیین می شود.
قسمت د - با توجه به قسمتهای الف و ج بدیهی است.
