====== میزان نامطلوبی! ======



فرض کنید
$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$
باشد.

  * [[سوال ۲|سوال بعد]]