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

شروع موضوع توسط mahtab.f ‏2012/7/7 در انجمن المپیاد كامپيوتر

  1. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : مسابقه ترکیبیات

    پله ی n تایی: :D
    [​IMG]
     
  2. kavian77

    kavian77 کاربر جدید

    ارسال‌ها:
    3
    امتیازات:
    +0 / -0
    نام مرکز سمپاد:
    شهید سلطانی 3
    شهر:
    کرج
    پاسخ : مسابقه ترکیبیات

    آآآآ ببخشید
    بعد از کلی کلنجار با مسئله به این جواب رسیدم.
    یکم سخته ولی حوصله کنید بخونیدش .
    ببینید با فرض اینکه تعداد کمترین مربع های مورد نیاز برای افراز یک پله ی n*n برابر است با ، یک بعلاوه ی ، x جلو میریم . (1+x)
    x کدام عدد است ؟
    اگر n زوج بود ، x برابر است با دو بربر تعداد مربع های مورد نیاز برای افراز یک (n/2)*(n/2)ی .
    اگر n فرد بود ، x برابر است با دو برابر تعداد مربع های مورد نیاز برای افراز یک (n-1)/2))*(n-1)/2))
    فک می کنم استقرائ زدم اگه درست فک می کنم پس باید جمله ی "برای افراز یک پله ی 1*1 ، به یک مربع نیاز داریم " ، را پایه ی استقرائ قرار دهیم .
    در نتیجه داریم :
    برای 1*1 -------> 1
    برای 2*2 -------> 3
    برای 3*3 -------> 3
    برای 4*4 -------> 7
    برای 5*5 -------> 7
    برای 6*6 -------> 7
    برای 7*7 -------> 7
    برای 8*8 -------> 15
    برای 9*9 -------> 15
    برای 10*10 -------> 15
    .
    .
    .

    موفق باشید
     
  3. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : مسابقه ترکیبیات

    ممنون که دارید روی سوال فکر میکنید اما تقریبا همه ی اینا رو بچه ها گفتن(آخر سر هم به به سری حالت استثنا رسیدیم و حل این سوال رو به وقتی که یه نفر یه چیز تازه به ذهنش برسه موکول کردیم) و الآن باید روی سوال زیر فکر کنیم.

    @پایینی: باووو چرا ناراحت میشی؟ حالا تو پ.خ بهت میگم (کلا منظوری نداشتم از این پستم نمیدونم چرا اینقدر زود ناراحت شدید)
     
  4. kavian77

    kavian77 کاربر جدید

    ارسال‌ها:
    3
    امتیازات:
    +0 / -0
    نام مرکز سمپاد:
    شهید سلطانی 3
    شهر:
    کرج
    پاسخ : مسابقه ترکیبیات

    دوستان به هیچ وجه علاقه ای به فرستادن اسپم ندارم . ولی بهتر بود با جوابی که 2 ساعت روش فکر شده بهتر از اینها برخورد بشه نه حداقل با شخص من .
    دوست عزیز بهتر نبود بجای اینطوری جواب دادن یه نگاه سطحی به جواب می انداختین ؟
    این جواب رو از تو جیبم که در نیوردم روش فکر کردم بالاخره ما هم تیزهوش و المپیادی هستیم داداش .
    کل پست های قبلی رو هم خونده بودم و متوجه شدم که نباید به حل مسئله بیش از اندازه دامن زد اما خوب گفته بودید اگر کسی فکری به ذهنش رسید ، بگه منم به جوابی (به زعم خودم) درست رسیدم که مثل هر جوابی منتظر یه debug ه .
    امیدوارم دوستان از من نرنجیده باشن اگر اینگونه بوده عذر می خوام و خواهش می کنم یک بار به جواب دقت کنید اگه استثنا پیدا شد من گردنم از مو باریک تر .
    البته این نیست که بخوام از جوابم بیخودی حمایت کنم اما خوب تا زمانی که خلافش ثابت شه حداقل برای من جواب درسته .
    فقط میخواستم مفید بوده باشم
    موفق و سلامت باشید
    متشکر
     
  5. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات ترکیبیات

    میدونم که جواب درستش اینه ولی نمی دونم چحوری بدست می آد:


    [size=12pt]!(n/2)!*(n-n/2)
    [/size]

    استدلال شما هم باز یک کم فکر می کنم روش...
     
  6. The Smith

    The Smith کاربر فوق حرفه ای

    ارسال‌ها:
    1,060
    امتیازات:
    +3,773 / -276
    نام مرکز سمپاد:
    سلام ایران‌زمین
    پاسخ : سوالات ترکیبیات

    این فرمول صریحشه ، من بازگشتی حل کردم :D
     
  7. فات

    فات کاربر خاک انجمن خورده

    ارسال‌ها:
    1,472
    امتیازات:
    +5,613 / -238
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    نیشابور
    دانشگاه:
    علامه طباطبایی
    رشته دانشگاه:
    اقتصاد
    پاسخ : مسابقه ترکیبیات

    .
     
  8. فات

    فات کاربر خاک انجمن خورده

    ارسال‌ها:
    1,472
    امتیازات:
    +5,613 / -238
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    نیشابور
    دانشگاه:
    علامه طباطبایی
    رشته دانشگاه:
    اقتصاد
    پاسخ : سوالات ترکیبیات

    3n+1 شی داریم که n تا یکسان و بقیه متفاوتند.نشان دهید تعداد راه های انتخاب n شی از آنها برابر 22n است.
     
    • لایک لایک x 1
  9. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات ترکیبیات

    فرض کنید بخواهیم k شیء از اشیای متمایز برداریم؛ بدین ترتیب، باید n-k شیء از اشیای یکسان برداریم و برای چنین انتخابی (C(2n+1, k حالت داریم. (چون باید k شیء از 2n+1 شیء متمایز انتخاب کنیم و از طرفی با توجه به این که n شی یکسان هستند، برای انتخاب n-k شء دیگر، 1 حالت داریم)
    میدانیم عدد k یکی از اعداد 0و 1و 2و ... و n-1 و n هست؛ پس بنابر اصل جمع:
    برای مشاهده ی عکس، بیاید این جا (فکر بد نکنید :/ )
    دو خط اول، اتحادهای ترکیبیاتی هستند و خط سوم به بعد هم جواب مسأله هستند
     
    • لایک لایک x 3
  10. TheBest444

    TheBest444 کاربر فوق فعال

    ارسال‌ها:
    89
    امتیازات:
    +70 / -4
    نام مرکز سمپاد:
    حلی3_علامه طباطبایی ادونس
    شهر:
    طهران
    رشته دانشگاه:
    فیزیک نوین _ علوم کامپیوتر
    پاسخ : سوالات ترکیبیات

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

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

    senatoor کاربر فعال

    ارسال‌ها:
    51
    امتیازات:
    +216 / -15
    پاسخ : سوالات ترکیبیات

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

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,596 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : مسابقه ترکیبیات

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

    Dark Eagle کاربر حرفه ای

    ارسال‌ها:
    404
    امتیازات:
    +679 / -34
    نام مرکز سمپاد:
    helli 2
    شهر:
    Tehran
    پاسخ : مسابقه ترکیبیات

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

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

    ثابت کنید تعداد یال های یک گراف بدون کایت بین 9n^2 و 12n^2 است ...
     
    • لایک لایک x 3
  14. مهسا.ق

    مهسا.ق کاربر فوق حرفه ای

    ارسال‌ها:
    1,104
    امتیازات:
    +3,289 / -94
    نام مرکز سمپاد:
    دبیرستان فرزانگان 1
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران
    رشته دانشگاه:
    نرم افزار
    پاسخ : مسابقه ترکیبیات

    حداقل وقتی سوال رو از آزمون گراف امسال می گی سوالو درست بگو :-"
    چیزی که از سوال جا افتاده اینه که گراف 6n راسی هست!
     
    • لایک لایک x 3
  15. فات

    فات کاربر خاک انجمن خورده

    ارسال‌ها:
    1,472
    امتیازات:
    +5,613 / -238
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    نیشابور
    دانشگاه:
    علامه طباطبایی
    رشته دانشگاه:
    اقتصاد
    پاسخ : مسابقه ترکیبیات

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

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : مسابقه ترکیبیات

    قبل از همه چیز تعریف میکنیم 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 انتخاب میشه، پس بنابر اصل جمع داریم:

    [​IMG]

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

    Dark Eagle کاربر حرفه ای

    ارسال‌ها:
    404
    امتیازات:
    +679 / -34
    نام مرکز سمپاد:
    helli 2
    شهر:
    Tehran
    پاسخ : مسابقه ترکیبیات

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

    مهدی کاربر فوق حرفه ای

    ارسال‌ها:
    1,088
    امتیازات:
    +6,596 / -140
    نام مرکز سمپاد:
    علامه‌حلی
    شهر:
    تهران
    دانشگاه:
    دانشگاه تهران. :دی
    رشته دانشگاه:
    آمار. :دی
    پاسخ : مسابقه ترکیبیات

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


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

    TheBest444 کاربر فوق فعال

    ارسال‌ها:
    89
    امتیازات:
    +70 / -4
    نام مرکز سمپاد:
    حلی3_علامه طباطبایی ادونس
    شهر:
    طهران
    رشته دانشگاه:
    فیزیک نوین _ علوم کامپیوتر
    پاسخ : سوالات ترکیبیات

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

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات ترکیبیات

    باسه حل این سوال بروت فورس(کلمه ی بهتری به ذهنم نرسید) زدم، اگه راه بهتری هست بگید
    اول این شکل رو برای متناظر کردن این مسأله به یه مسأله ی رنگ آمیزی رئوس درخت در نظر بگیر.
    میخوایم بعضی از رئوس این درخت رو علامت گذاری کنیم به طوری که هیچ دو راس مجاوری وجود نداشته باشن که جفتشون علامت گذاری شده باشند.
    [​IMG]
    حالا تعریف میکنیم F1 یعنی تعداد راه های علامت گذاری رئوس این شکل (جواب مسأله)
    F2 یعنی تعداد راه های علامت گذاری رئوس این شکل:
    [​IMG]
    F3 یعنی تعداد راه های علامت گذاری رئوس این شکل:
    [​IMG]
    F4 یعنی تعداد راه های علامت گذاری رئوس این شکل:
    [​IMG]

    واضحه که 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
     
    • لایک لایک x 5