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

[Goharshady]

[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]

 

[mohammad_72]

آره! خيلي آسونه!
فقط 6 حالت

 

[Goharshady]

آره! خيلي آسونه!
فقط 6 حالت

من فکر می کنم بهتره برای هر سوالی غیر از جواب نهایی حل کوتاهی هم بیان کنیم:
کافیست دو تا از آجرهای گوشه ای را رنگ آمیزی کنید!!

 

[SHIRY]

حداقل سوال سخت بزار.جواب میشود 3!(6)
اگر میتوانی این سوال را حل کن.

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

 

[Goharshady]

جواب

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

 

[Olympiad]

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

 

[Goharshady]

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

 

[mohammad_72]

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

 

[Goharshady]

وقتی مجموعه 7 عضویه ، مجبور میشی 1 عضوی تا 7 عضوی را جدا حساب کنی
شما فقط حالت 3 عضوی را در نظر گرفتی که آسان است.

 

[Mohammad_Reza]

تازه این که چیزه نیست
اگه به جای 7-1000 باشه می خواین چه کار کنین

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

 

[mohammad_72]

راست میگینا! اصلا حواسم نبود فکر کردم فقط زیرمجموعه های 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]

دنباله بازگشتی هم آسونه. بدست میاد:
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]

خیلی ممنون که حل کردین.ولی بچه ها من برای این سوال:که

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

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

 

[mohammad_72]

از قیافه ی جواب به نظر نمیرسه راه حل سریعی داشته باشه !