سوال جالب ترکیبیات
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
پاسخ
به استقرا روی تعداد ستونها حکم را ثابت می کنیم. پایه های استقرا (
ستون و
ستون) بدیهی هستند. فرض کنیم به ازای هر m دلخواه و تعداد
ستون بتوان این کار را انجام داد. جدولی با
ستون در نظر می گیریم که 3 خانه از آن حذف شده اند.به دو ستون اول و دو ستون آخر توجه می کنیم. اگر در حداقل یکی از آنها هیچ خانه ی حذف شده ای نباشد که حکم تبدیل به فرض می شود ، در غیر این صورت حتما یکی از اینها (مجموعه های دو تایی ستونها) شامل دقیقا یک خانه ی حذف شده است. بدون لطمه به کلیت مسئله فرض کنیم دو ستون اول شامل دقیقا یک خانه ی حذف شده هستند. اگر این خانه در ستون اول بود ، دومینو ها را به این شکل می چینیم تا به فرض استقرا برسیم :[center:343633c2e7]
[/center:343633c2e7][center:343633c2e7](قرمز خانه ی حذف شده را نشان می دهد و آبی ها محل قرار گرفتن دومینو ها را نشان می دهند.)[/center:343633c2e7]
[/center:343633c2e7][center:343633c2e7]
به استقرا روی تعداد ستونها حکم را ثابت می کنیم. پایه های استقرا (
اما اگر در ستون دوم باشد به یکی از دو حالت زیر عمل می کنیم:
[center:343633c2e7]
پس حکم ثابت است.
[/center:343633c2e7]