سوالی از المپیاد baltic
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : سوالی از المپیاد baltic
فراز هایی از اثبات
اول ثابت کنید می توان علامت ها رو یه جور گذاشت که تمام سطر ها یا ستون ها (به تنهایی) برابر شه.حال اول سطر اول بعد ستون اول و به همین ترتیب تا آخرین ستون رو می خوایم مرتب کنیم از این جا به بعدش واقعا محتاج شکل و حالت بندی هستش و از این استفاده میکنه که یه سری حرکت وجود دارد که اگه اونا رو انجام بدیم هیچ فرقی با چیزی که اول ثابت کردیم نداره از این هم استفاده کنید که تا جایی که حداقل 2n/3 تا سطر و2n/3 تا ستون که هرکدوم حداقل n/3 تا علامت داشته باشند رو میشه پیش رفت بعد برای بزرگتر از 2n/3 باید از متناهی بودن وساخت یه گراف استفاده کرد که لوپ داره.
فراز هایی از اثبات
اول ثابت کنید می توان علامت ها رو یه جور گذاشت که تمام سطر ها یا ستون ها (به تنهایی) برابر شه.حال اول سطر اول بعد ستون اول و به همین ترتیب تا آخرین ستون رو می خوایم مرتب کنیم از این جا به بعدش واقعا محتاج شکل و حالت بندی هستش و از این استفاده میکنه که یه سری حرکت وجود دارد که اگه اونا رو انجام بدیم هیچ فرقی با چیزی که اول ثابت کردیم نداره از این هم استفاده کنید که تا جایی که حداقل 2n/3 تا سطر و2n/3 تا ستون که هرکدوم حداقل n/3 تا علامت داشته باشند رو میشه پیش رفت بعد برای بزرگتر از 2n/3 باید از متناهی بودن وساخت یه گراف استفاده کرد که لوپ داره.