ماراتن مرحله 2

[Olympiad]

سلام دوستان ...

همونطور که میدونید تقریبا 3 ماه ( یا شایدم کمتر !!!!

) به مرحله 2 مونده .....


این تاپیک رو ایجاد کردم که تا مرحله دو در این تاپیک سوال های مرحله 2 و یا بهتره بگم سوال های در سطح مرحله 2 با هم حل کنیم . خوب قوانین هم اینطوریه :

1- همزمان حداکثر 2 سوال حل نشده میتواند وجود داشته باشد

2- بالای سوالهایتان شماره بگذارید

3- دو قانون بالا !!!!!

خوب یکی سوال بذاره.........

ممنون

 

[Aref]

کولیا و پتیا می خواهند 2n+1 گردو(

) را بین خود تقسیم کنند. بدیهی است هر کسی می خواهد بیشترین مقدار ممکن گردو را به دست آورد. فرض کنیم سه روش تقسیم (و در هر روش 3 مرحله) وجود دارد.
مراحل اول و دوم در هر سه روش مشترک هستند.
مرحله ی اول: پتیا همه ی گرد ها را به دو بخش تقسیم می کند به نحوی که هر بخش حداقل دو گردو داشته باشد.

مرحله ی دوم: کولیا هر یک از بخش ها را به دو قسمت تقسیم می کند به نحوی که هر قسمت حداقل یک گردو داشته باشد.

مرحله ی سوم:

در روش اول، کولیا بزرگترین و کوچکترین قسمت را برای خود بر می دارد(و بقیه به پتیا می رسد)؛

در روش دوم، کولیا دو بخش وسط را برمی دارد؛

در روش سوم، کولیا دو بخش وسط و یا بزرگترین و کوچکترین قسمت را بر می دارد، ولی بنابر قرار قبلی، از آنچه انتخاب کرده است یک گردو به پتیا بر میگرداند.

کدام روش برای کولیا مناسب تر و کدام روش نامناسب تر است؟

 

[fereidoon]

بهترین روش,روش اول و بدترین (فک کنم)دومه,راه حلش هم با بررسی حالات مختلف و چگونگی تقسیم کولیاست(اگه می خوایید راه کامل رو بذارم؟!)

 

[Aref]

بهترین روش,روش اول و بدترین (فک کنم)دومه,راه حلش هم با بررسی حالات مختلف و چگونگی تقسیم کولیاست(اگه می خوایید راه کامل رو بذارم؟!)

گند زدی که.

دفعه ی قبلی هم تذکر دادم که راه حل کامل بزارید ولی...

 

[fereidoon]

منظورم این بود اگه درسته راه حل رو بذارم!بذارم؟؟

 

[Aref]

قسمت اولش درسته.

 

[fereidoon]

اها!بدترین حالت جفت حالت های دوم و سوم!!(چه جالب)
فرض کنید که کولیا هر دفعه میاد هر دسته رو به دو دسته ی xوy تقسیم میکنه و هر کدوم از دسته ها که بزرگتر بود(مثلا x)را به دو دسته ی x-1و1 تقسیم میکنه در واقع این بهترین کاریه که کولیا می تونه انجام بده,حالا با این الگوریتم بهترین و بدترین حالات را بررسی می کنیم:
روش1:کولیا میاد x رو طوری انتخاب میکنه که x>n+1 بشه!
روش2:دوباره کولیا بهترین کارش همون الگوریتمه ولی نسبت به حالت اول حداکثر می تونه n گردو بگیره
روش3:اگه x=n+1 و y=n باشه باز حالت بدی واسه کولیا اتفاق میفته و 1 گردو کمتر از په تیا به دست میاره

 

[Aref]

اها!بدترین حالت جفت حالت های دوم و سوم!!(چه جالب)
فرض کنید که کولیا هر دفعه میاد هر دسته رو به دو دسته ی xوy تقسیم میکنه و هر کدوم از دسته ها که بزرگتر بود(مثلا x)را به دو دسته ی x-1و1 تقسیم میکنه در واقع این بهترین کاریه که کولیا می تونه انجام بده,حالا با این الگوریتم بهترین و بدترین حالات را بررسی می کنیم:
روش1:کولیا میاد x رو طوری انتخاب میکنه که x>n+1 بشه!
روش2:دوباره کولیا بهترین کارش همون الگوریتمه ولی نسبت به حالت اول حداکثر می تونه n گردو بگیره
روش3:اگه x=n+1 و y=n باشه باز حالت بدی واسه کولیا اتفاق میفته و 1 گردو کمتر از په تیا به دست میاره

مرسی درسته.
حالا سوال بزار، منتها تر و تمیز!

 

[mahanmath]

[center:c539cab160]2[/center:c539cab160]


[center:c539cab160]فرض کنید عدد خوشه ای‌ G زوج است . ثابت کنید افرازی از راس‌های G موجود است که عدد خوشه ای‌ هر دو دسته برابر باشند . [/center:c539cab160]

 

[sts3662]

با استقرا اثبات میکنیم :
برای پایه که حکم بدیهیست : گراف از دو راس تنها تشکیل میشه .
فرض کنین برای n = 2k حکم درست باشد .
حالا یک گراف داریم که 2k + 2 راس دارد . بزرگترین خوشه اش را در نظر بگیرید .
دوراس از این خوشه بکنید ( همبندی مهم نیست ) ( راس های v و u ).
طبق فرض گراف را دو تکه کنید .
حالا v رو به یکی از دو تکه اضافه کنید . اگه عدد خوشه ایش زیاد نشه که ما برنده ایم وگر نه دو حالت داریم : 1- راسی به جز راسهای خوشه پیدا میکنیم که عدد خوشه ای تکه ی دیگر را زیاد کند . 2- پیدا نمی کنیم !
1- اون راس رو جابجا کرده و ادامه میدهیم ...
2- یکی از راسهای خوشه را به تکه ی دیگر میفرستیم و ادامه میدهیم ...

 

[mahanmath]

با استقرا اثبات میکنیم :
برای پایه که حکم بدیهیست : گراف از چند مسیر دوتایی تشکیل میشه .
فرض کنین برای n = 2k حکم درست باشد .
حالا یک گراف داریم که عدد خوشه ایش 2k + 2 است .
دوراس از این خوشه بکنید ( همبندی مهم نیست ) ( راس های v و u ).
طبق فرض گراف را دو تکه کنید .
حالا v رو به یکی از دو تکه اضافه کنید . اگه عدد خوشه ایش زیاد نشه که ما برنده ایم وگر نه دو حالت داریم : 1- راسی به جز راسهای خوشه پیدا میکنیم که عدد خوشه ای تکه ی دیگر را زیاد کند . 2- پیدا نمی کنیم !
1- اون راس رو جابجا کرده و ادامه میدهیم ...
2- یکی از راسهای خوشه را به تکه ی دیگر میفرستیم و ادامه میدهیم ...

اگه چند تا خوشه ماکزیمم داشتیم چی‌ ؟

 

[sts3662]

[TABLE][TR] [TD]
sts3662 مي نويسد:[/TD][/TR][TR][TD]با استقرا اثبات میکنیم :
برای پایه که حکم بدیهیست : گراف از چند مسیر دوتایی تشکیل میشه .
فرض کنین برای n = 2k حکم درست باشد .
حالا یک گراف داریم که عدد خوشه ایش 2k + 2 است .
دوراس از این خوشه بکنید ( همبندی مهم نیست ) ( راس های v و u ).
طبق فرض گراف را دو تکه کنید .
حالا v رو به یکی از دو تکه اضافه کنید . اگه عدد خوشه ایش زیاد نشه که ما برنده ایم وگر نه دو حالت داریم : 1- راسی به جز راسهای خوشه پیدا میکنیم که عدد خوشه ای تکه ی دیگر را زیاد کند . 2- پیدا نمی کنیم !
1- اون راس رو جابجا کرده و ادامه میدهیم ...
2- یکی از راسهای خوشه را به تکه ی دیگر میفرستیم و ادامه میدهیم ...

[/TD][/TR][/TABLE]


اگه چند تا خوشه ماکزیمم داشتیم چی‌ ؟



جواب :

مهم نیست ! به عددخوشه ای حد اکثر یکی اضافه میشه

 

[mahanmath]

مثل اینکه منظورمو بد رسوندم .

وقتی‌ شما میتونید از فرض استقرأ استفاده کنید که عدد خوشه ای‌ گراف بعد از کندن اون دو راس حداکثر 2k باشه ولی‌ وقتی‌ یه تعداد زیادی خوشه با 2k+2 راس داشته باشیم (که ممکن کلی‌ اشتراک داشته باشن و یا جدا باشن) دیگه نمی‌شه این حرفو زد .

 

[sts3662]

sorrrry

نه من اشتباه نوشته بودم .....

منظورم از n تعداد راسها بود , نه عدد خوشه ای .

بازم ببخشید ...!

همونجا درستش کردم

 

[mahanmath]

sorrrry

نه من اشتباه نوشته بودم .....

منظورم از n تعداد راسها بود , نه عدد خوشه ای .

بازم ببخشید ...!

همونجا درستش کردم

یه سوال بذار .

 

[sts3662]

سوال :

یک جدول m*n داریم .
یالهای آن را با 3 رنگ رنگ کنید طوری که هر مربع 1*1 دویال از یک رنگ و دو یال از رنگ دیگر داشته باشد .
به چند طریق میتوان ؟

 

[sts3662]

[center:68ae71c137]2[/center:68ae71c137]


[center:68ae71c137]فرض کنید عدد خوشه ای‌ G زوج است . ثابت کنید افرازی از راس‌های G موجود است که عدد خوشه ای‌ هر دو دسته برابر باشند . [/center:68ae71c137]

البته سوال باید اصلاح بشه :
عدد خوشه ای زوج و مخالف 0 است .

 

[sts3662]

پس چی شد ؟

 

[sts3662]

یکی این سوالو حل کنه دیگه .
خیلی خیلی راحته ..

 

[sts3662]

مکعب k بعدی (Qk) را با استفاده از ضرب دکارتی تعریف کنید .