سوالی از پانزدهمین المپیاد کامپیوتر

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#1
[center:cebb292553]
[/center:cebb292553]
[center:cebb292553]به چند طریق می توان آجر های شکل زیر را با 3 رنگ رنگ آمیزی کرد به طوری که هیچ دو آجر مجاوری هم رنگ نباشند؟[/center:cebb292553]
[center:cebb292553]
[/center:cebb292553][center:cebb292553]اگر تا یک هفته جوابی نگیرم گزینه هاشو می ذارم[/center:cebb292553][center:cebb292553]خیلی آسونه مگه نه؟[/center:cebb292553][center:cebb292553]
[/center:cebb292553]
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#3
mohammad_72 گفت
آره! خيلي آسونه!
فقط 6 حالت
من فکر می کنم بهتره برای هر سوالی غیر از جواب نهایی حل کوتاهی هم بیان کنیم:
کافیست دو تا از آجرهای گوشه ای را رنگ آمیزی کنید!!
 

SHIRY

New Member
ارسال ها
22
لایک ها
0
امتیاز
0
#4
حداقل سوال سخت بزار.جواب میشود 3!(6)
اگر میتوانی این سوال را حل کن.

" تعداد زیر مجموعه ای مجموعه ی (1.2.3.4.5.6.7) که مجموع اعضای هر یک از انها بر 3 بخش پذیر باشد چندتاست؟(مجموع اعضای مجموعه ی تهی صفر است)
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#5
جواب

44تا؟
اتفاقا این یکی از سوالاتیه که من یادم رفته بود بپرسم
بچه ها اگه میشه ایده حل این سوالات رو به من بگید
من غیر از شمردن همه حالات یک راه دیگه بلدم که زود به جواب نمی رسه
اگه ایده بهتری ندادید ، اونو می نویسم
من خیلی دنبال ایده این سوالم
لطف کنید بگید چه جوری حل می کنید
 

Olympiad

New Member
ارسال ها
1,268
لایک ها
134
امتیاز
0
#6
اعداد 1 تا 7 را 3 دسته تقسيم ميكنيم . يعني دسته ي 3k+1 , 3k+2 , 3k ====>>>> A={3,6,9 , B={1,4,7 , C={2,5
و بعد حالاتي كه از هر مجموعه چند عضو انتخاب شوند در نظر ميگيريم و حساب ودر آخر جمع ميكنيم
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#7
اینجوری که کلی طول میکشه
(البته خودمم همین کارو کردم)
ولی حتما باید راه آسونتری داشته باشه
[FLASH=425,350]http://www.youtube.com/v/XXXXXXX[/FLASH]
 

mohammad_72

New Member
ارسال ها
302
لایک ها
5
امتیاز
0
#8
فکر نکنم راه حل آسونتری داشته باشه.
البته این راه حل هم اونجور که آقای گوهرشادی نوشتن طولانی نیستا.
اگه a+b+c بر 3 بخشپذیر باشه یا a , b , c هیچ دوتاشون همنهشت نیستن یا
هر سه با هم همنهشتن که خیلی راحت حساب میشه.
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#9
وقتی مجموعه 7 عضویه ، مجبور میشی 1 عضوی تا 7 عضوی را جدا حساب کنی
شما فقط حالت 3 عضوی را در نظر گرفتی که آسان است.
 
ارسال ها
6
لایک ها
1
امتیاز
0
#10
تازه این که چیزه نیست
اگه به جای 7-1000 باشه می خواین چه کار کنین

از قدیم گفتن واسه هر مسئله راه حل خودشو پیدا کنین
اینجا می تونی سه دسته ی جدا نسبت به باقیمانده بگیری و بازگشتی و استقرایی حلش کنی
واسه نمونه چتوره همین 1000 رو حلش کنیم
 

mohammad_72

New Member
ارسال ها
302
لایک ها
5
امتیاز
0
#11
راست میگینا! اصلا حواسم نبود فکر کردم فقط زیرمجموعه های 3 عضوی رو میگه!
میشه سه تا تابع f0(n) و f1(n) و f2(n) رو اینجوری تعریف کرد که f0(n) یعنی تعداد زیرمجموعه های
مجموعه ی {n, ..., 1} که باقیمونده ی جمعشون بر 3 برابره با 0 و f1 و f2 رو هم شبیه همین تعریف میکنیم
اونوقت راحت میشه ثابت کرد (f0(n+3) = 4f0(n) + 2f1(n) + 2f2(n) = 2f0(n) + 2^(n+1
اگه بتونیم جمله ی عمومی این رابطه بازگشتی رو پیدا کنیم حله.
 

mohammad_72

New Member
ارسال ها
302
لایک ها
5
امتیاز
0
#12
دنباله بازگشتی هم آسونه. بدست میاد:
f0(3k) = 2^(k+1) * (2^(2k-1)+1)/3
f0(3k+1) = 2^k * (2^(2k+1)+1)/3
f0(3k+2) = 2f0(3k+1) = 2^(k+1) * (2^(2k+1)+1)/3
اگه سوتی محاسباتی نداشته باشم!
 

SHIRY

New Member
ارسال ها
22
لایک ها
0
امتیاز
0
#13
خیلی ممنون که حل کردین.ولی بچه ها من برای این سوال:که

مجموعه ی اعداد 1تا 10 چند زیر مجموعه ی دارد که مجموع اعضای ان زوج باشد

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

mohammad_72

New Member
ارسال ها
302
لایک ها
5
امتیاز
0
#14
از قیافه ی جواب به نظر نمیرسه راه حل سریعی داشته باشه !
 
بالا