یک سوال ناب از ترکیبیات

[combinatorics]

برای هر n تعداد روش های افراز n سکه ی یکسان در تعدادی جعبه ی متمایز را بیابید؛ به گونه‌ای که هر جعبه، حداقل 2 سکه داشته باشد.

 

[goodarz]

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

این نمیشه؟؟:

 

[combinatorics]

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

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

 

[goodarz]

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

خب واضحه جوابو از کجا آوردم! برحسب این که تعداد جعبه ها چندتا باشه حالت بندی کردم, اگه تعداد جعبه ها یکی باشه میشه جمعوند اول,اگه دوتا دومی.....

 

[emad.shahbazy]

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

این خیلی راحته!اگه تعداد جعبه هارو x بگیریم.جوب . جواب معادبه زیر میشهx1 +x2+x3+ ... + xx = n -2xکه میشه x-1 از n-x+1

 

[combinatorics]

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

ببخشید
جوابت درسته
ولی اگه دقت کنی جوابت برابر با عدد فیبوناچی n-1ام است.
حالا بیش تر فکر کنید و سعی کنید با یک راه حل زیبا مستقیم به عدد فیبوناچی برسید.
راستی سوالای روسیه به زبان فارسی را در combinatorics.vcp.ir می توانید ببینید.

 

[goodarz]

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

با تابع مولد که بدیهیه.....راه حل ترکیبیاتیشم با استفاده از فرش کردن یه مستطیل (n-2)x1 با دومینو ها و تک مربعی هاست.

پ.ن: اگه راه حل تابع مولدشو میخواین میتونین صفحه 12 جزوه تابع مولد سایت imomath رو ببینید...

 

[math]

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

از روابط بازگشتیاشتفاده میکنیم رابطش هم این میشه

که اگر ادامه بدیم به

 

[combinatorics]

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

مثل این که کسی نمی خواد این سوال را با راه حل اصلی حل کنه
پس خودم حلشو می گم
ابتدا مسأله را به حالتی تبدیل می‌کنیم که در هر دسته 1 سکه هم بتواند قرار بگیرد.
عبارت زیر را در نظر بگیرید:
1+1+1+...+1
که در آن تعداد 1 ها n تاست.
بودن یا نبودن هر +، 2 حالت دارد. پس بودن یا نبودن کل +ها 2 به توان n - 1 حالت دارد. هر توزیع را به یکی از این حالت ها تناظر می دهیم و هر یک از این حالت ها را هم به همان توزیع تناظر می دهیم. پس با یک تناظر یک به یک تعداد 2 به توانn-1 می شود.
حالا مسئله ی اصلی را هم به همین شکل حل می کنیم. تنها تفاوت در این جا است که دو + کناری نمی توانند باشند و هیچ دو به + دیگری نباید مجاور باشند. این هم تعداد حالات رشته های دودویی به طول n-3 است که هیچ دو 1 مجاوری ندارند. پس جواب برابر با عدد فیبوناچی n-1ام است.

 

[math]

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

مثل این که کسی نمی خواد این سوال را با راه حل اصلی حل کنه
پس خودم حلشو می گم
ابتدا مسأله را به حالتی تبدیل می‌کنیم که در هر دسته 1 سکه هم بتواند قرار بگیرد.
عبارت زیر را در نظر بگیرید:
1+1+1+...+1
که در آن تعداد 1 ها n تاست.
بودن یا نبودن هر +، 2 حالت دارد. پس بودن یا نبودن کل +ها 2 به توان n - 1 حالت دارد. هر توزیع را به یکی از این حالت ها تناظر می دهیم و هر یک از این حالت ها را هم به همان توزیع تناظر می دهیم. پس با یک تناظر یک به یک تعداد 2 به توانn-1 می شود.
حالا مسئله ی اصلی را هم به همین شکل حل می کنیم. تنها تفاوت در این جا است که دو + کناری نمی توانند باشند و هیچ دو به + دیگری نباید مجاور باشند. این هم تعداد حالات رشته های دودویی به طول n-3 است که هیچ دو 1 مجاوری ندارند. پس جواب برابر با عدد فیبوناچی n-1ام است.

وقتی یک سوال چه توی کنکور وچه توی المپیاد میدن مهم اینه که حل بشه نه این که با راه حل مرد نظر حل بشه فقط حل بشه.