دو مربع یا تو گوشه مشترک ان یا توی هم دیگه ان .

حالت دوم یکم برای ما مشکل افرینه پس سعی می کنیم کاری بکنیم که اتفاق نیافته

استقرایی عمل می کنیم فرض می کنیم n-1 تا اوکی شده میریم سر n و فرض می کنیم که n امی از همه کوچیک تره و برای n-1 تای بقیه که حله و اون مربع کوچیکه رو اضافه میکنیم با توجه به گذاره اول مطلب دو حالت داریم اما با انتخاب کوچیک ترین فقط حالت اول مهمه چون حالت دوم هم توی گوشه های مربع کوچیک محاسبه میشه حالا طبق فرض سوال توی هر گوشه ما حداقل k-1 اشتراک داریم پس ما از 4k-4 مجموعه نمیتونیم استفاده بکنیم پس 4k-3 مجموعه برای ما کافیه .

نکته : چرا از بزرگ به کوچیک این کارو کردیم ؟؟؟؟

خوب واسه این یه استقرای باید بزنی استقرا رو بزن روی تعداد مربع ها که می تونی n بگیریش

بدیهی هست به برای n = 1 حکم درسته

حالا فرض میکنیم برای n مربع درسته و نتیجه میگیریم برای n + 1 هم درست میشه

کوچیک ترین مربع رو در نظر بگیر اسمشم بزار t حالا فرض کن وجود نداره 2 حالت داریم

1) k کاهش پیدا میکنه

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

چون 4k - 7 دسته بقیه رو میشه گذاشت t رو حتما تو 4 دسته که خالی مونده میشه گذاشت

2) تو این حالت k ثابت میمونه که این چالش اصلی ماست

میای میگی چون t کوچک ترین ضلع رو داره هیچ مربعی بدون شامل گوشش شدن نمیتونه باهاش اشتراک داشته باشه

از طرفی با هر گوشش بیشتر از k - 1 اشتراک نمیشه داشته باشن چون فرض مسِعله اینو گفته

حالا 4 تا گوشه داره بس میشه گفت حداکثر با 4 * (k-1) یا همون 4k - 4 تا مربع اشتراک داره

چون این عدد از تعداد مجموعه هامون کمتره حتما یک دونه مجموعه هست که با t اعضاش اشتراک ندارن ما هم t رو میزاریم اون تو