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

[Anita H]

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

سلام به همگی
دوستان نیازی نیست انقدر خودتون رو اذیت کنید .
هر پله ی n*n با یک مربع n-1*n-1 و دو مربع 1*1 پر میشه .
در واقع کمینه جواب 3 می شود .
موفق و سلامت باشید
نظر شخصی ام بود اگه اشتباه کردم خوشحال میشم بفرمائید .

پله ی n تایی:

 

[kavian77]

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

پله ی n تایی:

آآآآ ببخشید
بعد از کلی کلنجار با مسئله به این جواب رسیدم.
یکم سخته ولی حوصله کنید بخونیدش .
ببینید با فرض اینکه تعداد کمترین مربع های مورد نیاز برای افراز یک پله ی 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
.
.
.

موفق باشید

 

[Anita H]

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

آآآآ ببخشید
بعد از کلی کلنجار با مسئله به این جواب رسیدم.
یکم سخته ولی حوصله کنید بخونیدش .
ببینید با فرض اینکه تعداد کمترین مربع های مورد نیاز برای افراز یک پله ی 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
.
.
.

موفق باشید

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

یه گراف جهت دار داریم که حداقل درجه راس های اون n / 2 ه. ثابت کنید این گراف یه مسیر به طول ۳ داره .

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

 

[kavian77]

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

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

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

 

[daneshvar.amrollahi]

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

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

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

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

 

[The Smith]

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

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

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

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

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

 

[فات]

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

.

 

[فات]

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

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

 

[Anita H]

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

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

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

 

[TheBest444]

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

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

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

 

[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