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

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

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

kavian77

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

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

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

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

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

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

daneshvar.amrollahi

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

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


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

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

The Smith

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,061
امتیاز
3,545
نام مرکز سمپاد
سلام ایران‌زمین
پاسخ : سوالات ترکیبیات

به نقل از daneshvar.a :
میدونم که جواب درستش اینه ولی نمی دونم چحوری بدست می آد:


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

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

فات

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,467
امتیاز
5,381
نام مرکز سمپاد
فرزانگان
شهر
نیشابور
سال فارغ التحصیلی
1395
دانشگاه
علامه طباطبایی
رشته دانشگاه
اقتصاد نظری
پاسخ : مسابقه ترکیبیات

.
 

فات

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,467
امتیاز
5,381
نام مرکز سمپاد
فرزانگان
شهر
نیشابور
سال فارغ التحصیلی
1395
دانشگاه
علامه طباطبایی
رشته دانشگاه
اقتصاد نظری
پاسخ : سوالات ترکیبیات

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

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوالات ترکیبیات

به نقل از ـفــاتـــــ :
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

کاربر فوق‌فعال
ارسال‌ها
89
امتیاز
73
نام مرکز سمپاد
حلی3_علامه طباطبایی ادونس
شهر
طهران
رشته دانشگاه
فیزیک نوین _ علوم کامپیوتر
پاسخ : سوالات ترکیبیات

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

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

senatoor

کاربر فعال
ارسال‌ها
51
امتیاز
205
پاسخ : سوالات ترکیبیات

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

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

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,384
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : مسابقه ترکیبیات

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

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
660
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : مسابقه ترکیبیات

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

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

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

مهسا.ق

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,098
امتیاز
3,216
نام مرکز سمپاد
دبیرستان فرزانگان 1
شهر
تهران
مدال المپیاد
برنز کامپیوتر ۱۳۹۳
دانشگاه
دانشگاه تهران
رشته دانشگاه
نرم افزار
پاسخ : مسابقه ترکیبیات

به نقل از ๖ۣۜTango :
توران (طوران) ... نمیدونم کدومش درسته :-"

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

ثابت کنید تعداد یال های یک گراف بدون کایت بین 9n^2 و 12n^2 است ...
حداقل وقتی سوال رو از آزمون گراف امسال می گی سوالو درست بگو :-"
چیزی که از سوال جا افتاده اینه که گراف 6n راسی هست!
 

فات

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,467
امتیاز
5,381
نام مرکز سمپاد
فرزانگان
شهر
نیشابور
سال فارغ التحصیلی
1395
دانشگاه
علامه طباطبایی
رشته دانشگاه
اقتصاد نظری
پاسخ : مسابقه ترکیبیات

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

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

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

4.png


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

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
660
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : مسابقه ترکیبیات

به نقل از مهسا.ق :
حداقل وقتی سوال رو از آزمون گراف امسال می گی سوالو درست بگو :-"
چیزی که از سوال جا افتاده اینه که گراف 6n راسی هست!
یه جورایی نصفش غلط بود :-" ... درستش کردم ...
 

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,384
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : مسابقه ترکیبیات

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


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

TheBest444

کاربر فوق‌فعال
ارسال‌ها
89
امتیاز
73
نام مرکز سمپاد
حلی3_علامه طباطبایی ادونس
شهر
طهران
رشته دانشگاه
فیزیک نوین _ علوم کامپیوتر
پاسخ : سوالات ترکیبیات

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

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوالات ترکیبیات

به نقل از TheBest444 :
مینا 3 دختر دارد و هر دخترش 2 دختر دارند و هر یک از آن ها 1 دختر دارند. به چند طریق میتوان تعدادی از بین این 16 نفر انتخاب کرد به طوری که در مجموعه ی بدست آمده هیچ زنی به همراه دختر خود حضور نداشته باشد؟
باسه حل این سوال بروت فورس(کلمه ی بهتری به ذهنم نرسید) زدم، اگه راه بهتری هست بگید
اول این شکل رو برای متناظر کردن این مسأله به یه مسأله ی رنگ آمیزی رئوس درخت در نظر بگیر.
میخوایم بعضی از رئوس این درخت رو علامت گذاری کنیم به طوری که هیچ دو راس مجاوری وجود نداشته باشن که جفتشون علامت گذاری شده باشند.
1.png

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

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

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


واضحه که 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
 
بالا