به نام خدا

ایده سوال استقرا روی $k$ه. پایه استقرا از 2ه و یکم اثباتش دردسر داره. می تونین برین از بخش حکم استقرا بخونین.

پایه استقرا: جدولی $4.n$ داریم. ثابت می کنیم می توان 2 ستون از این جدول را رنگ کرد به طوری که از هر یک از 4 سطر حداقل یک عدد 1 رنگ شده باشد.

اگر ستونی با حداقل 3 عدد 1 در جدول وجود داشت، آن ستون را رنگ می کنیم وسپس اگر هنوز سطری وجود داشت که یکی از 1 های آن رنگ نشده بود، ستون دوم را طوری رنگ می کنیم که یکی از 1 های آن سطر نیز رنگ شود.

در غیر این صورت در هر ستون حداکثر 2 عدد 1 وجود دارد:

اگر $n$ فرد باشد، در این صورت در هر سطر حداقل $\frac{n+1}{2}$ و در کل $\frac{n+1}{2}$.4 عدد 1 وجود دارد. یعنی حداقل $2.n+2$ تا. از طرفی می دانیم که تعداد 1 های هر ستون حداکثر 2 تا است و تعداد کل 1 های جدول حداکثر $2.n$ تاست. که این با فرض قبل در تناقض است.

اگر $n$ زوج باشد، در این صورت در هر سطر حداقل $\frac{n}{2}$ عدد 1 و در کل $2.n$ عدد 1 وجود دارد و با توجه به اینکه در هر ستو ن بیش از 2 عدد 1 وجود ندارد پس باید در هر ستون دقیقن 2 عدد 1 وجود داشته باشد.

از هر سطر $\frac{n}{2}$ عدد 1 را انتخاب می کنیم و بقیه را از جدول حذف می کتیم. واضح است در صورت درستی حکم در جدول فعلی، حکم برای جدول قبلی نیز برقرار است.

به دو 1 که در یک ستون باشند، دو 1 مجاور می گوییم. براساس اینکه 1های سطر اول مجاور با 1 های کدام سطر ها هستند حالت بندی می کنیم:

1.فرض کنید 1 های سطر اول همگی با 1 های یک سطر خاص مجاور باشند. بدون تغییر در شرایط مسئله فرض می کنیم این سطر خاص، سطر 2 است. در این صورت با توجه به برابری تعداد 1 های سطر 1 و 2، تمام 1 های سطر 2 نیز با 1 های سطر 1 مجاورند. در این صورت تمام 1 های سطر 3 نیز تنها می توانند با 1 های سطر 4 مجاور باشند. در این حالت یک ستون که شامل 1 هایی از سطر های 1 و 2 است و یک ستون که شامل 1 هایی از ستون های 3 و 4 است را رنگ می کنیم و حکم ثابت می شود.

2.فرض کنید 1 های سطر اول با $c$ تا از 1 های سطر $i$ و $\frac{n}{2}-c$ تا از سطر $j$ مجاور باشند($c \gt 0$). بدون تغییر در شرایط مسئله فرض می کنیم $i=2$ و $j=3$. در این صورت 1 های سطر 4 با یکی از 1 های سطر 2 یا 3 مجاورند. باز هم بدون تغییر در شرایط مسئله فرض کنیم ستونی وجود داشته باشد که شامل 1 های سطر 2 و 4 باشد. در این صورت با رنگ کردن ستونی که شامل 1 های سطر های 2 و 4 و ستونی که شمال سطر های 1 و 3 است، حکم مسئله ثابت می شود.

3.فرض کنید 1 های سطر 1 با 1 های هر سه سطر 2 و 3 و 4 مجاور باشند. در این صورت در یکی از ستون هایی که شامل 1ی از سطر 1 نیست، 1 های دو سطر مجاورند. بدون تغییر در شرایط مسئله فرض کنید این دو سطر 2 و 3 باشند. در این صورت با رنگ کردن ستونی که شامل 1 های سطر های 1 و 4 و ستونی که شامل 1 های سطر های 2 و 3 شرط مسئله برقرار می شود.

پس در هر صورت حکم به ازای $k=2$ و جدول $4.n$برقرار است.

حکم استقرا:فرض کنید حکم به ازای $k=i$ برقرار باشد. می خواهیم ثابت می کنیم می توان $k+1$ ستون از جدول $2^{k+1}.n$را رنگ کرد به طوری که از هر سطر حداقل بک عدد 1 رنگ شود.

در هر سطر حداقل $\lceil \frac{n}{2} \rceil$ عدد 1 و در کل جدول حداقل $2^{k+1}.\lceil \frac{n}{2} \rceil \ge 2^{k}.n$ عدد 1 وجود دارد. بنابراین قطعن ستونی وجود دارد که شامل حداقل $2^{k}$ عدد 1 است. آن را $x$ می نامیم و رنگش می کنیم و $2^k$ تا از سطر هایی را که عدد1ی از آن ها رنگ شده است را از جدول حذف می کنیم. در جدول باقی مانده بنابر فرض استقرا می توان $k$ ستون را رنگ کرد به طوری از هر سطر باقی مانده حداقل یک عدد 1 رنگ شده باشد. این ستون ها با اجتماع با $x$ مجموعه ای از $k+1$ ستون را به وجود می آمورند که با رنگ شدنشان از هر سطر حداقل یک عدد 1 رنگ می شود.

پس حکم ثابت می شود.