سوال آنایز ترکیبی - انتخابی Imc
- ارسال ها
- 93
- لایک ها
- 40
- امتیاز
- 0
پاسخ : سوال آنایز ترکیبی - انتخابی Imc
مرسی منم طبیعتا مثل همه جوابم ۲ به توان ۲۵ بود منتها بعدش شک کردم ممکنه حالتی پیش بیاد که خونه اول از سمت راست تو سطر پایین پایین دچار مشکل بشه یعنی مثلا ستونش به غیر از خودش فرد تا مهره باشن ولی ردیفش به غیر از خودش زوج تا باشند که اینجوری اصلا نمیشه تعیینش کرد
ولی حالا از جوابم مطمئن شدم
بازم مرسی
مرسی منم طبیعتا مثل همه جوابم ۲ به توان ۲۵ بود منتها بعدش شک کردم ممکنه حالتی پیش بیاد که خونه اول از سمت راست تو سطر پایین پایین دچار مشکل بشه یعنی مثلا ستونش به غیر از خودش فرد تا مهره باشن ولی ردیفش به غیر از خودش زوج تا باشند که اینجوری اصلا نمیشه تعیینش کرد
ولی حالا از جوابم مطمئن شدم
بازم مرسی
- ارسال ها
- 75
- لایک ها
- 67
- امتیاز
- 0
پاسخ : سوال آنایز ترکیبی - انتخابی Imc
این سوال برای حالت کلی n*n یه اثبات خوب و جمع و جور داره.
برای اینکه اثبات کنیم اگر یک زیر مجموعه n-1 در n-1 رو رنگ کنیم بقیه جدول به طور یکتا تعیین میشه باید دو تا چیز رو ثابت کنیم:
اثبات اولی کاری نداره. اگر تعداد سیاه های یک ستون یا سطر فرد باشه آخرین خونه ستون سیاه و در غیر این صورت نمیشه. خونه راست پایین هم اگر تعداد سیاه های سطر و ستون فرد باشه سیاه میشه و در غیر این صورت نمیشه.
برای اثبات دومی از ناوردایی استفاده می کنیم. در واقع اینجا باید اثبات کنیم که تعداد سیاه ها در سطر آخر به جز خونه پایین راست و در ستون آخر به جز خونه پایین راست یا در هر دو زوجه یا در هر دو فرد. می دونیم که در ابتدا مجموع خونه های سیاه در قسمت باقیمانده از جدول که در اون جدول n-1 در n-1 نیست صفر تاست. حالا ما در هر مرحله که یک خونه از اون جدول رو رنگ کنیم یکی از این حالتا پیش میاد:
بدیهیه که با این حرکت در نهایت مجموع سیاه ها در خونه های آخر سطر ها و ستون ها بر 2 بخش پذیره. هر گاه مجموع دو عدد هم زوج باشه قطعا یا هر دو زوجن یا هر دو فرد. اگر هر دو فرد بودن خونه راست پایین رو سیاه می کنیم و هر دو زوج میشن و شرط مسئله برقرار میشه و اگر هر دو زوج بودن که بهش دست نمی زنیم و می ذاریم سفید بمونه.
این سوال برای حالت کلی n*n یه اثبات خوب و جمع و جور داره.
برای اینکه اثبات کنیم اگر یک زیر مجموعه n-1 در n-1 رو رنگ کنیم بقیه جدول به طور یکتا تعیین میشه باید دو تا چیز رو ثابت کنیم:
- اینکه حالتی وجود نداره که ما چند حالت رنگ آمیزی برای بقیه داشته باشیم
- اینکه حالتی وجود نداره که هیچ رنگ آمیزی معتبری برای بقیه نداشته باشیم
اثبات اولی کاری نداره. اگر تعداد سیاه های یک ستون یا سطر فرد باشه آخرین خونه ستون سیاه و در غیر این صورت نمیشه. خونه راست پایین هم اگر تعداد سیاه های سطر و ستون فرد باشه سیاه میشه و در غیر این صورت نمیشه.
برای اثبات دومی از ناوردایی استفاده می کنیم. در واقع اینجا باید اثبات کنیم که تعداد سیاه ها در سطر آخر به جز خونه پایین راست و در ستون آخر به جز خونه پایین راست یا در هر دو زوجه یا در هر دو فرد. می دونیم که در ابتدا مجموع خونه های سیاه در قسمت باقیمانده از جدول که در اون جدول n-1 در n-1 نیست صفر تاست. حالا ما در هر مرحله که یک خونه از اون جدول رو رنگ کنیم یکی از این حالتا پیش میاد:
- اگر خونه آخر اون سطر و ستون سفید باشه سیاه میشن هر دو. یعنی تعداد خونه های سیاه باقیمونده جدول به علاوه 2 میشه.
- اگر یکی از خونه های آخر سطر و ستون سیاه باشه و اون یکی سفید، اونی که سیاه بوده سفید میشه و اونی که سفید بوده سیاه میشه. پس مجموع سیاه های قسمت باقیمونده از جدول تغییر نمی کنه.
- اگر هر دو خونه آخر سطر و ستون سیاه باشن، هر دو سفید میشن. پس مجموع سیاه های خونه های باقیمونده منهای 2 میشه.
بدیهیه که با این حرکت در نهایت مجموع سیاه ها در خونه های آخر سطر ها و ستون ها بر 2 بخش پذیره. هر گاه مجموع دو عدد هم زوج باشه قطعا یا هر دو زوجن یا هر دو فرد. اگر هر دو فرد بودن خونه راست پایین رو سیاه می کنیم و هر دو زوج میشن و شرط مسئله برقرار میشه و اگر هر دو زوج بودن که بهش دست نمی زنیم و می ذاریم سفید بمونه.