ماراتن ترکیبیات
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
سوال چهلم
[center:f2c6e8cc65]40[/center:f2c6e8cc65]سوال چهلم:
یک گراف دوبخشی داریم.که به دو گروه راسهای بالا و راسهای پایین تقسیم شده است.به هر یک از راسهای بالا عددی نسبت داده ایم. می خواهیم تعدادی از یالها را حذف کنیم به گونه ای که هر یک از رئوس پایینی حداکثر به یک راس متصل باشد و هر یک از رئوس بالایی به اندازه ی عددی که به آن نسبت داده شده است همسایه داشته باشد. ثابت کنید این کار ممکن است اگر و تنها اگر هر زیر مجموعه از رئوس بالایی در ابتدا حداقل به اندازه ی حاصل جمع اعداد نسبت داده شده به اعضایش همسایه (از پایینی ها) داشته باشد.
این مسئله به صورت حرمسرای قضیه ی هال مشهور است.
[center:f2c6e8cc65]40[/center:f2c6e8cc65]سوال چهلم:
یک گراف دوبخشی داریم.که به دو گروه راسهای بالا و راسهای پایین تقسیم شده است.به هر یک از راسهای بالا عددی نسبت داده ایم. می خواهیم تعدادی از یالها را حذف کنیم به گونه ای که هر یک از رئوس پایینی حداکثر به یک راس متصل باشد و هر یک از رئوس بالایی به اندازه ی عددی که به آن نسبت داده شده است همسایه داشته باشد. ثابت کنید این کار ممکن است اگر و تنها اگر هر زیر مجموعه از رئوس بالایی در ابتدا حداقل به اندازه ی حاصل جمع اعداد نسبت داده شده به اعضایش همسایه (از پایینی ها) داشته باشد.
این مسئله به صورت حرمسرای قضیه ی هال مشهور است.
- ارسال ها
- 143
- لایک ها
- 79
- امتیاز
- 0
برای هر راس از دسته بالا به اندازه عدد اون راس , راس های مجازی در نظر بگیر (یعنی اگه راس v روش عدد t نوشته شده بود , v رو حذف کن و t تا راس به جاش بذار که همسایه هاشون همون همسایه های v هستن ) , حالا دقیقا مسئله مون همون مسئله هال می شه (توی یه گراف دو بخشی باید یه تطابق پیدا کنیم که دسته بالا رو بپوشونه که شرط لازم و کافی اش همون شرط هاله)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:4d13c69ff5]41[/center:4d13c69ff5]
نیم یک بازی منصفانه ی دو نفره است که می توان همه ی بازیهای منصفانه را به آن تبدیل کرد.
ابتدا چند دسته لوبیا داریم که هرکدام شامل تعدادی لوبیا هستند. هر کسی در نوبت خودش می تواند هر تعداد لوبیا که می خواهد تنها از یک دسته بردارد. برنده کسی است که آخرین لوبیا را بردارد. مثلا اگر یک دسته لوبیا داشته باشیم ، نفر اول همه ی آنها را بر می دارد و برنده می شود ولی اگر دو دسته داشته باشیم که هر کدام 1 لوبیا داشته باشند ، نفر اول مجبور است یکی از لوبیاها را بردارد و نفر دوم با برداشتن لوبیای دوم برنده می شود.
پیشنهاد می کنم اگه قبلا نیم را ندیده اید خیلی روش فکر کنید. بعد اگه لازم شد استراتژی برد کلی بازی رو می گم. الآن سوال استراتژی برد برای حالتی رو می خواد که کسی که آخرین لوبیا رو برداره می بازه.
ضمنا اگه هیچی لوبیا نداشته باشیم (همون اول) نفر دوم برنده است.
Olympiad گفت
نيم بازي چه قوانيني دارد؟؟!
ابتدا چند دسته لوبیا داریم که هرکدام شامل تعدادی لوبیا هستند. هر کسی در نوبت خودش می تواند هر تعداد لوبیا که می خواهد تنها از یک دسته بردارد. برنده کسی است که آخرین لوبیا را بردارد. مثلا اگر یک دسته لوبیا داشته باشیم ، نفر اول همه ی آنها را بر می دارد و برنده می شود ولی اگر دو دسته داشته باشیم که هر کدام 1 لوبیا داشته باشند ، نفر اول مجبور است یکی از لوبیاها را بردارد و نفر دوم با برداشتن لوبیای دوم برنده می شود.
پیشنهاد می کنم اگه قبلا نیم را ندیده اید خیلی روش فکر کنید. بعد اگه لازم شد استراتژی برد کلی بازی رو می گم. الآن سوال استراتژی برد برای حالتی رو می خواد که کسی که آخرین لوبیا رو برداره می بازه.
ضمنا اگه هیچی لوبیا نداشته باشیم (همون اول) نفر دوم برنده است.
