با استقرا روی n به اثبات حکم میپردازیم

پایه : پرواضحه!!

حالا یه ستون رو میخوام حذف کنم ؛ کافی است ثابت کنم که تعداد مستطیل های خوبی که حذف میشن از m بیشتر نیست دیگه !!

اونم بدیهی چون هر مستطیل خوب یه خونه سفید پایینش یا بالاش داره دیگه , حالا اگه قراره حذف شه یکی باید داشته باشه و اینم تو این ستونه حالا میتوان تعداد مستطیل های سیاه خوب رو از خانه های سفید شمرد و حکم را اثبات کرد.

جدید : (توضیح)

ثابت کنم اضافه نمیشن :

فرض کنید مستطیل غیر قابل کسترش زیر اضافه شه بعد از حذف سمت راست ترین ستون :

اگه تو ناحیه ی قرمز سفیدی نباشه که هیچی ... این قابل گسترش بوده و قبلا بزگتر بوده و الان فقط کوچکتر شده و اگر هم باشه فقط خونه ی سفیده راستش از بین رفته و با دیوار همسایه شده و هنوز غیر قابل گسترشه ... پس هیچ مستطیل غیرقابل گسترشی اضافه نمیشه !

حالا کافی است بگم مستطیل های خوب(اون غیرقابل گسترش هایی که حذف میشن ) از m(تعداد سطرها) بیشتر نیست !

یه غیرقابل گسترش موقعی خوبه یکی از ستونش اینجا (تو ستون آخر) باشه و سفید بالاش یکتا توی این ستون باشه یا فقط یه سفید پایینش داشته باشه و اونم فقط تو همین ستون باشه و یا هردو دیگه.

حالا ادعا میکنم نمیشه اتفاق زیر بیافته (تمام عرض یه خوب داخل خوبه دیگه باشه ):

چرا !؟چون شکل داخلیه (آبیه) باید بزرگتر باشه :) و وقتی بزگتر باشه این آبیه یه سفید بالا و یه سفید پایینش دم کنجی های بین خودشه و قرمز داره !پس این اصلا خوب نبوده ! (مساوی قرمزه که نمیتونه باشه چون از هر دوسمت بزرگتر میشه .)

حالا ادعا میکنم هر پاره خط به طول یک از شبکه موازی طول(افقی) که بین دوتا خانه ی سیاهه ستون آخر قرار داره فقط میتونه تو محیط یه مستطیل خوب باشه (تو ستون آخر دیگه )

یعنی شکل های زیر نمیشه اتفاق بیافته :

نیمشه آبی و قرمز طولشون برابر باشه (واضحه) پس آبی از یه سمت قابل گسترشه و از سمته دیگر اگر نباشه واضحه ی یه سفید پایینش داره حالا قرمزه از بالا یه سفید داره که تو این سطر نیست (کنج خودشو آبیه ) پس قرمزه اگه بخواهد خوب باشد باید یه سفید از پایین تو ستون اول داشته باشه که اونقت حله دیگه

تو شکل دوم به راحتی میتونیم نشون بدیم که قرمزه قابله گسترشه پس هر خط تو ستون اخر متعلق به یه مستطیل خوبه پس حداکثر m تا خوب داریم .