دیرالسلطان (۲۰ نمره)
دیر السلطان شکلی است که از سه دایره‌ی هم‌مرکز و $n$ قطاع تشکیل شده است. $(n \ge 3)$ برای مثال شکل زیر، یک دیر السلطان به ازای $(n=6)$ است:
به این ترتیب یک دیرالسلطان $3n$ خانه دارد. دو خانه از یک دیرالسلطان را مجاور می گوییم اگر بیش از یک نقطه مرزی مشترک داشته باشند. برای مثال در شکل زیر، خانه ۱ با خانه های ۲ و ۳ مجاور است، ولی با خانه ۴ مجاور نیست:
آبولف و ایلیچ در حال بازی بر روی یک دیرالسلطان به ازای
$(n=1398)$
هستند. در هر مرحله آبولف یک قطاع را انتخاب می کند، طوری که آن قطاع حداقل یک خانه رنگ نشده داشته باشد. سپس ایلیچ یکی از خانه های رنگ نشده آن قطاع را انتخاب می کند. در مراحل زوج خانه انتخاب شده را آبی و در مراحل فرد خانه انتخاب شده را قرمز می کنیم. پس از آن که تمام خانه ها رنگ زده شد، بازی خاتمه می یابد.
در انتها به ازای هر دو خانه مجاور ناهمرنگ، ایلیچ باید یک واحد به ابولف پول بدهد. اگر هر دو نفر به روش بهینه بازی کنند، ایلیچ چه مقدار پول خواهد داد؟
پاسخ
ثابت می کنیم پاسخ برابر ۳*۱۳۹۸=۴۱۹۴ است.
ابتدا روشی برای سلطال ارائه می کنیم که مستقل از بازی ایلیچ بتواند دست کم ۴۱۹۴ واحد پول بگیرد. قطاع‌ها را به ترتیب با ۱ تا ۱۳۹۸ شماره‌گذاری می کنیم. سلطان در مراحل زوج، قطاع های زوج و در مراحل فرد قطاع های فرد را انتخاب می کند. مستقل از نحوه بازی ایلیچ، در پایان بازی هر قطاع با شماره زوج، به طور کامل آبی و هر قطاع با شماره فرد به طور کامل قرمز خواهد شد و ایلیج ۴۱۹۴ واحد پول خواهد داد.
حال روشی برای ایلیچ ارائه می کنیم که مستقل از حریف، حداکثر ۴۱۹۴ واحد پول بدهد. ایلیچ در مراح زوج، نزدیک ترین خانه ممکن به مرکز دایره و در مراحل فرد، دورترین خانه ممکن را انتخاب می کند. در این صورت در هر قطاع با حرکت از مرکز به سمت محیط، ابتدا خانه های آبی و سپس خانه های قرمز دیده خواهند شد. مقادیر زیر را برای قطاع C در نظر بگیرید:
- f(C) : تعداد زوج خانه های مجاور ناهمرنگ که هر دو خانه در C هستند.
- g(C) : تعداد زوج خانه های مجاور ناهمرنگ که یکی در C و دیگری در قطاع بعدی در جهت ساعتگرد باشد.
مقدار پولی که ایلیچ باید بدهد برابر است با جمع $f(C)+g(C)$ به ازای تمام قطاع ها. واضح است که $f(C) \le 1$ و $g(C) \le 3$ ثابت می کنیم که $f(C)+g(C) \le 3$ و حکم مساله که ایلیچ حداکثر ۴۱۹۴ واحد پول می دهد ثابت می شود. برای ثابت کردن آن نابرابری، از برهان خلف استفاده می کنیم. فرض کنید نا برابری غلط باشد، آن گاه f(C)=1 پس قطاع دو رنگ است و g(C)=3 پس قطاع ساعتگرد بعدی دقیقا برعکس این قطاع می شود. اما طبق استراتژی ایلیچ این ممکن نیست.