در یک ماتریس $n\times n$ نواری به شکل زیر را نوار خطر ، و به مربع $(n-1)\times (n-1)$ ای که شامل نوار خطر نیست بچه مربع میگوییم.

به سطر یا ستونی پر میگوییم اگر و تنها اگر یک خانه در این سطر یا ستون برچسب گذاری شده باشد و به سطر یا ستونی خالی میگوییم اگر و تنها اگر هیچ خانه ای در آن نباشد که برچسب گذاری شده باشد.

با استقرا حکم را اثبات میکنیم:

حکم به ازای $n=1$ و $n=2$ بدیهی است. فرض کنید حکم به ازای تمام مقادیر کوچکتر مساوی $n$ صحیح است. یک ماتریس $(n+1)\times (n+1)$ را در نظر بگیرید که $n$ خانه از آن برچسب گذاری شده اند. چون $n$ خانه برچسب گذاری شده اند، پس حداقل یک سطر وجود دارد که هیچ خانه ی برچسب گذاری شده ای ندارد.این سطر را در ابتدا با چند حرکت به سطر افقی نوار خطر انتقال میدهیم. سپس با توجه به فرض استقرا میتوانیم حداقل $n-1$ خانه ی برچسب گذاری شده را به زیر قطر اصلی بچه مربع انتقال دهیم.(چون این چند خانه در بچه مربع قرار داشتند پس هیچ خانه ی برچسب گذاری شده ای وارد سطر خالی افقی نوار خطر نمیشود.). بعد از این حرکت سطر خالی را به بالا ترین سطر ممکن انتقال میدهیم تا تمام این حداقل $n-1$ خانه در زیر قطر اصلی قرار بگیرند. حال اگر هر $n$ راس زیر قطر اصلی باشند، حکم صحیح است. درغیر اینصورت چند نکته ی زیر را میتوانیم در نظر بگیریم:

1. در صورتی که ستون عمودی سمت چپ نوار خطر خالی باشد، میتوانیم سمت چپ ترین ستونی که پر است را به آن انتقال دهیم. در این صورت واضح است هنوز $n-1$ خانه ی برچسب گذاری شده وجود دارد که زیر قطر اصلی است (دقت کنید که سطر اول هم خالی است).

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

حال چون حداقل یک خانه ی برچسب گذاری شده روی ستون سمت چپ است پس حداکثر در مربع سبز $n-1$ خانه ی برچسب گذاری شده وجود دارد. در نتیجه بر اساس استقرا همه ی آنها را میتوان به زیر قطر اصلی مربع سبز که همان قطر اصلی مربع بزرگتر است انتقال داد. پس حکم به ازای تمام مقادیر $n$ درست است.

امیدوارم درست باشه :)