فرض کنید $n$ یک عدد طبیعی و $T$ یک جدول $(4n+1) \times (4n+1)$ باشد. برخی از خانه‌های جدول سیاه و بقیه سفید هستند. یک مسیر را مطلوب گوییم، هر گاه از خانه‌ی بالا-چپ جدول شروع شده، در هر مرحله به یک خانه‌ی مجاور(دو خانه را مجاور گوییم، هر گاه یک ضلع مشترک داشته باشند) غیر تکراری (خانه‌ای که قبلن روی آن نرفته‌ایم) برود و کار را در خانه‌ی پایین-راست جدول تمام کند و هم‌چنین تمام خانه‌های مسیر، سفید باشند. به یک جدول نامرد گوییم، هر گاه دست کم یک مسیر مطلوب داشته باشد. کمینه‌ی طول (تعداد خانه‌های) یک مسیر مطلوب را $f(T)$ می‌نامیم. دبیران با درایت ترکیبیات و گراف در عملیاتی سنگین ثابت کردند بیشینه‌ی مقدار $f(T)$ در میان تمام جدول‌های نامرد $(4n+1) \times (4n+1)$ برابر $8n^2+8n+1$ است.

آ) مجموعه‌ی ممکن مقادیر $f(T)$ را به ازای تمام جداول نامرد $(4n+1) \times (4n+1)$ بیابید.

ب) میزان نامطلوبی یک جدول نامرد $(4n+1) \times (4n+1)$ را $f(T) - (8n+1)$ تعریف می‌کنیم( توجه کنید $8n+1$ طول کوتاه‌ترین مسیر ممکن از خانه‌ی بالا-چپ به خانه‌ی پایین-راست است.). فرض کنید $k$ یک عدد صحیح با ویژگی $0 \le k \le 8n^2$ باشد. ثابت کنید می‌توان $g(k)$ خانه از یک جدول $(4n+1) \times (4n+1)$ را سیاه کرد؛ طوری که $g(k) \in O(k)$ بوده و میزان نامطلوبی جدول حداقل $k$ باشد.

• سوال بعد