المپیاد سوالات ترکیبیات و مباحث ویژه !

[senatoor]

پاسخ : سوالات ترکیبیات

یه سوال آسون شمارشی(لطفا توضیح هم بدین) :

به چند طریق میتوان یک مهره اسب سفید و یک مهره اسب سیاه را در یک جدول 8x8 (هشت در هشت) قرار داد به طوری که یکدیگر را تهدید کنند؟

قبول داری دوتا اسب فقط میتونن به صورت L هم دیگه رو تهدید کنن؟حالا شکل L چیه؟ببین تو هر مستطیل دو در سه انتخاب کنی دقیقا 4 تا حالت داره برا تهدید اینم که درکش اسونه؟
خب حالا ما تعداد مستطیل های دو در سه رو میشماریم ضرب در چهار میکنیم
تعداد مستطیل های سه در دو هم که کاری نداره شمردنش میشه 6*7*2 حالا حاصل اینو که میشه 84 رو ضرب در چهار میکنیم تمام
حالا جواب رو ببین درسته شاید سوتی هم داده باشم وسطش

 

[مهدی]

پاسخ : مسابقه ترکیبیات

نیما که هستش
رضا هم که سر می‌زنه
علیرضا هم که هستش
مهسا و ملیکا رو هم نمیدونم،
میگم اگر موافقید هر روز یک سوال بزاریم برای فکر کردن، جوابش مهم نیست،هر کس حواست میتونه پ.خ بده و بگیره جوابش رو اما بعد از این که فکر کرد رو سوال
اولین سوال رو خودم می‌ذارم.
سوال فاینال مبحث گراف
اندازه ی بزرگترین مجموعه مستقل راسی در گراف ساده G کوچک تر از n√ می‌باشد.
ثابت کنید تعداد یال های G از Ω(n√n) است

 

[Dark Eagle]

پاسخ : مسابقه ترکیبیات

توران (طوران) ... نمیدونم کدومش درسته

کایت : گراف 4 راسی کامل یه یال کم ! (6n راسی)

ثابت کنید تعداد یال های یک گراف بدون کایت بین 9n^2 و 12n^2 است ...

 

[مهسا.ق]

پاسخ : مسابقه ترکیبیات

توران (طوران) ... نمیدونم کدومش درسته

کایت : گراف 4 راسی بدون کامل یه یال کم !

ثابت کنید تعداد یال های یک گراف بدون کایت بین 9n^2 و 12n^2 است ...

حداقل وقتی سوال رو از آزمون گراف امسال می گی سوالو درست بگو
چیزی که از سوال جا افتاده اینه که گراف 6n راسی هست!

 

[فات]

پاسخ : مسابقه ترکیبیات

به چند طریق میتوان n عامل را در یک ضرب غیرشرکت پذیر پرانتز گذاری کرد؟

 

[Anita H]

پاسخ : مسابقه ترکیبیات

به چند طریق میتوان n عامل را در یک ضرب غیرشرکت پذیر پرانتز گذاری کرد؟

قبل از همه چیز تعریف میکنیم Fn یعنی تعداد راه های پرانتزگذاری یک عبارت که شامل n متغیر هست. واضحه که F1=1 و F2=1 و F3=2
خب، میدونیم شکل عبارت برای n متغیر، به این شکل هست:
(a1*a2*…*ak)*(ak+1*ak+2*…*an)
یعنی کل عبارت به دو تا پرانتز تقسیم میشه که هر کدوم از اون دو تا پرانتز به یه سری پرانتز دیگه تقسیم شدن!
حالا عبارت داخل هر کدوم از اون دو تا پرانتز رو میشه به Fk و Fn-k طریق پرانتزگذاری کرد. یعنی کل عبارت رو میشه به Fk*Fn-k طریق علامت گذاری کرد(اصل ضرب)
+میدونیم k همواره از محدوده ی اعداد صحیح 1 تا n انتخاب میشه، پس بنابر اصل جمع داریم:

و طبق تعریف میدونیم که (Fn+1=C(2n, n)/(n+1
(ر.ک. به ترکیبیات علیپور/روابط بازگشتی/اعداد کاتالان)

 

[Dark Eagle]

پاسخ : مسابقه ترکیبیات

حداقل وقتی سوال رو از آزمون گراف امسال می گی سوالو درست بگو
چیزی که از سوال جا افتاده اینه که گراف 6n راسی هست!

یه جورایی نصفش غلط بود ... درستش کردم ...

 

[مهدی]

پاسخ : مسابقه ترکیبیات

ريدي دوست من :)
من ميگم هي غلطه سوال بعد ميگي همينو تو امتحان دادن


اين سوال خيلي سواله شاخيه خوب روش فكر كنيد
يه دايره داريم سطحش به 49 بخش تقسيم شده به طوري كه هيچ سه بخشي نقطه مشترك ندارن . " نقشه " به دست اومده رو با 3 رنگ رنگ ميكنيم
به طوري كه هر دو بخش مجاور رنگاشون يكي نباشن . مرز دو بخش رو هم با هر دو رنگ در نظر ميگيريم
ثابت كنيد ك روي محيط دايره ميشه دو تا نقطه پيدا كرد كه دو سر يه قطر باشن در ضمن يك رنگ باشن

 

[TheBest444]

پاسخ : سوالات ترکیبیات

مینا 3 دختر دارد و هر دخترش 2 دختر دارند و هر یک از آن ها 1 دختر دارند. به چند طریق میتوان تعدادی از بین این 16 نفر انتخاب کرد به طوری که در مجموعه ی بدست آمده هیچ زنی به همراه دختر خود حضور نداشته باشد؟

 

[Anita H]

پاسخ : سوالات ترکیبیات

مینا 3 دختر دارد و هر دخترش 2 دختر دارند و هر یک از آن ها 1 دختر دارند. به چند طریق میتوان تعدادی از بین این 16 نفر انتخاب کرد به طوری که در مجموعه ی بدست آمده هیچ زنی به همراه دختر خود حضور نداشته باشد؟

باسه حل این سوال بروت فورس(کلمه ی بهتری به ذهنم نرسید) زدم، اگه راه بهتری هست بگید
اول این شکل رو برای متناظر کردن این مسأله به یه مسأله ی رنگ آمیزی رئوس درخت در نظر بگیر.
میخوایم بعضی از رئوس این درخت رو علامت گذاری کنیم به طوری که هیچ دو راس مجاوری وجود نداشته باشن که جفتشون علامت گذاری شده باشند.

حالا تعریف میکنیم F1 یعنی تعداد راه های علامت گذاری رئوس این شکل (جواب مسأله)
F2 یعنی تعداد راه های علامت گذاری رئوس این شکل:

F3 یعنی تعداد راه های علامت گذاری رئوس این شکل:

F4 یعنی تعداد راه های علامت گذاری رئوس این شکل:

واضحه که F4=2 و F3=3
حالا میخوایم F2 رو پیدا کنیم. میگیم فرض کنید رأس بالای شکل(ریشه ی درخت) انتخاب شده باشه، اون وقت واضحه که دو تا فرزند اون رأس نباید انتخاب بشن، بقیه ی درخت رو هم میشه به F4*F4=2*2=4 طریق علامت گذاری کرد. حالا فرض کنید رأس بالای شکل(ریشه ی درخت) انتخاب نشده باشه، بقیه ی شکل رو به F3*F3=3*3=9 طریق میشه علامت گذاری کرد. در نتیجه F2=13
الآن دیگه میخوایم F1 یعنی جواب اصلی مسأله رو پیدا کنیم. فرض کنید راس بالایی شکل که همانا مینا باشه علامت گذاری شده باشه، سه تا بچه ی مینا نباید انتخاب شده باشند. مینا 6 تا نوه داره، پس بقیه ی درخت رو به F3^6=3^6=729 طریق میشه علامت گذاری کرد. حالا فرض کنید مینا انتخاب نشه، با توجه به این که مینا 3 تا بچه داره، بقیه ی درخت رو به F2^3=13^3=2197 طریق میشه علامت گذاری کرد. پس F1=729+2197=2926