ماراتن ترکیبیات
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن ترکیبیات
یه درخت داریم دو نفر میخوان با هم بازی کنن اولی در صورتی میبره که همه ی رئوس گراف رنگ شن و دومی در غیر این صورت.
بازی:
6تا رنگ داریم هر بار میونیم یه راس رو رنگ کنیم به طوری که رنگش با همه ی مجاوراش تفاوت داشته باشه
ثابت کنید اولی استراتژی برد دارد.
من وقتی حلش کردم در پوست خودم نمی گنجیدم.:6:شرط میبندم شما هم در پوست خودتون نمی گنجید.:116:
یه درخت داریم دو نفر میخوان با هم بازی کنن اولی در صورتی میبره که همه ی رئوس گراف رنگ شن و دومی در غیر این صورت.
بازی:
6تا رنگ داریم هر بار میونیم یه راس رو رنگ کنیم به طوری که رنگش با همه ی مجاوراش تفاوت داشته باشه
ثابت کنید اولی استراتژی برد دارد.
من وقتی حلش کردم در پوست خودم نمی گنجیدم.:6:شرط میبندم شما هم در پوست خودتون نمی گنجید.:116:
- ارسال ها
- 199
- لایک ها
- 268
- امتیاز
- 0
پاسخ : ماراتن ترکیبیات
مجتبی ببخشید. این سوال رو تقریبا هممون قبلا حل کردیم. اگه میشه تو ماراتن ها سوالاتی بگذارید که احتمال می دهید بقیه ندیده باشند. به نظر من هدف ماراتن ها آشنا شدن با سوالاتی است که فقط عده ی مخصوصی می دانند. مثلا سوالی که فقط معلم خاصی در کلاسش گفته یا سوالی که در یک وبلاگ گمنام گذاشته شده یا سوالی در یک کتاب نایاب و... .
مجتبی ببخشید. این سوال رو تقریبا هممون قبلا حل کردیم. اگه میشه تو ماراتن ها سوالاتی بگذارید که احتمال می دهید بقیه ندیده باشند. به نظر من هدف ماراتن ها آشنا شدن با سوالاتی است که فقط عده ی مخصوصی می دانند. مثلا سوالی که فقط معلم خاصی در کلاسش گفته یا سوالی که در یک وبلاگ گمنام گذاشته شده یا سوالی در یک کتاب نایاب و... .
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن ترکیبیات
امیدوارم این یکی رو تعداد زیادی ندیده باشند.سوال آسونیه ولی با مزه هست.
Suppose that every integer has been given one of the colours red, blue, green or yellow. Let
and
be odd integers so that
. Show that there are two integers of the same colour whose difference has one of the following values:
or
امیدوارم این یکی رو تعداد زیادی ندیده باشند.سوال آسونیه ولی با مزه هست.
Suppose that every integer has been given one of the colours red, blue, green or yellow. Let
سوال ترکیبیات
یک بازی یک نفره روی یک صفحه ی m*n با mn مهره که یک روی آنها سیاه و روی دیگر آنها سفید است ، انجام میشود. در شروع بازی کلیه ی مهره ها را روی صفحه طوری قرار میدهیم که هر مهره در یک خانه قرار گیرد و روی سفید همه ی مهره ها بالا باشد به جز در یکی از خانه های گوشه ای . در هر حرکت میتوانیم یک مهره که روی سیاه آن بالا است را از روی صفحه حذف کنیم و مهره ی کلیه ی خانه های مجاور ضلعی آن را پشت و رو کنیم . (m,n) هایی را بیابید که بتوان همه ی مهره ها را حذف کرد .
یک بازی یک نفره روی یک صفحه ی m*n با mn مهره که یک روی آنها سیاه و روی دیگر آنها سفید است ، انجام میشود. در شروع بازی کلیه ی مهره ها را روی صفحه طوری قرار میدهیم که هر مهره در یک خانه قرار گیرد و روی سفید همه ی مهره ها بالا باشد به جز در یکی از خانه های گوشه ای . در هر حرکت میتوانیم یک مهره که روی سیاه آن بالا است را از روی صفحه حذف کنیم و مهره ی کلیه ی خانه های مجاور ضلعی آن را پشت و رو کنیم . (m,n) هایی را بیابید که بتوان همه ی مهره ها را حذف کرد .
پاسخ : سوال ترکیبیات
واسه اثبات سوال نشان میدهیم که اگر یکی از m و n زوجیت فرد داشته باشند حکم برقار میشود و اگر هر دو زوجیت زوج داشته باشند این کار قابل انجام نیست .
اثبات قسمت اول که با استقرا خیلی راحته کافیه n رو ثابت بگیرید و روی m استقرا بزنید . واسه قسمت دوم هم زوجیت تعداد تغییر های پشت و رو شدن تمام مهره ها را به دو طریق میشماریم از یک طرف به ازای هر دوخانه ی مجاور
دقیقا یکی به خاطر دیگری پشت ورو میشود و چون تعداد زوج های مجاور زوج است پس تعداد پشت رو شدن ها زوج است و از طرف دیگر میدانیم تمام خانه های سفید (دارای مهره ی سفید) برای حذف شدن باید فرد بار پشت رو شوند و خانه ی سیاه گوشه نیز در زوج بار پشت و رو میشود ( پشت رو نمیشود) پس در کل فرد بار پشت و رو میشوند که این تناقض است
واسه اثبات سوال نشان میدهیم که اگر یکی از m و n زوجیت فرد داشته باشند حکم برقار میشود و اگر هر دو زوجیت زوج داشته باشند این کار قابل انجام نیست .
اثبات قسمت اول که با استقرا خیلی راحته کافیه n رو ثابت بگیرید و روی m استقرا بزنید . واسه قسمت دوم هم زوجیت تعداد تغییر های پشت و رو شدن تمام مهره ها را به دو طریق میشماریم از یک طرف به ازای هر دوخانه ی مجاور
دقیقا یکی به خاطر دیگری پشت ورو میشود و چون تعداد زوج های مجاور زوج است پس تعداد پشت رو شدن ها زوج است و از طرف دیگر میدانیم تمام خانه های سفید (دارای مهره ی سفید) برای حذف شدن باید فرد بار پشت رو شوند و خانه ی سیاه گوشه نیز در زوج بار پشت و رو میشود ( پشت رو نمیشود) پس در کل فرد بار پشت و رو میشوند که این تناقض است
سوال ترکیبیات (Canada 2010)
هر راس از یک گراف متناهی میتوانند به یکی از 2 رنگ سفید یا سیاه رنگ آمیزی شوند . در ابتدا رنگ همه ی راس ها سیاه می باشند . در هر مرحله میتوانیم راسی مانند P را انتخاب کنیم و رنگ راس p و همه ی همسایه های P را تغییر دهیم . آیا میتوان رنگ همه ی راس ها را طی چند مرحله از سیاه به سفید تبدیل کنیم ؟
هر راس از یک گراف متناهی میتوانند به یکی از 2 رنگ سفید یا سیاه رنگ آمیزی شوند . در ابتدا رنگ همه ی راس ها سیاه می باشند . در هر مرحله میتوانیم راسی مانند P را انتخاب کنیم و رنگ راس p و همه ی همسایه های P را تغییر دهیم . آیا میتوان رنگ همه ی راس ها را طی چند مرحله از سیاه به سفید تبدیل کنیم ؟
پاسخ : سوال ترکیبیات (Canada 2010)
از استقرا روی تعداد یالها استفاده میکنیم تا ثابت کنیم از هر گرافی میشه به یه گراف رسید که رنگ همه ی راس هاش برعکس گراف اولیه است. (e=0 بدیهیه).
اول از همه برای هر راس با درجه بزرگتر از صفر مثل v میدونیم G-v میتونه با یه روشی مثل (f(v به گرافی تبدیل شه که رنگ همه ی راس ها به جز v تغییر کرده، اگر بعد از این روش رنگ v هم تغییر کرد مساله حله. پس فرض کنیم به ازای هر v روش (f(v رنگ همه ی راس ها به جز v رو تغییر میده.
حالا یه یال e=uv رو میگیریم. میدونیم G-e رو میشه با یه روش رنگ همه ی راس هاش رو تغییر داد. اگه همون روش رو تو G پیاده کنیم، رنگ همه ی راس ها به جز u و v تغییر کرده و خود u و v هم 2 حالت دارن: یا رنگ هر دوشون تغییر کرده که مساله حله، یا رنگ هیچکدوم تغییر نکرده. حالا اگه روش (f(u و روش (f(v رو انجام بدیم مساله حل میشه.
از استقرا روی تعداد یالها استفاده میکنیم تا ثابت کنیم از هر گرافی میشه به یه گراف رسید که رنگ همه ی راس هاش برعکس گراف اولیه است. (e=0 بدیهیه).
اول از همه برای هر راس با درجه بزرگتر از صفر مثل v میدونیم G-v میتونه با یه روشی مثل (f(v به گرافی تبدیل شه که رنگ همه ی راس ها به جز v تغییر کرده، اگر بعد از این روش رنگ v هم تغییر کرد مساله حله. پس فرض کنیم به ازای هر v روش (f(v رنگ همه ی راس ها به جز v رو تغییر میده.
حالا یه یال e=uv رو میگیریم. میدونیم G-e رو میشه با یه روش رنگ همه ی راس هاش رو تغییر داد. اگه همون روش رو تو G پیاده کنیم، رنگ همه ی راس ها به جز u و v تغییر کرده و خود u و v هم 2 حالت دارن: یا رنگ هر دوشون تغییر کرده که مساله حله، یا رنگ هیچکدوم تغییر نکرده. حالا اگه روش (f(u و روش (f(v رو انجام بدیم مساله حل میشه.
