چند تا سوال ترکیبیات

[mfm12]

سلام دوستان چندتایی سوال از ترکیبیات گذاشتم امیدوارم خوشتون بیاد.
1.در یک شبکه m*n به چند طریق می توان از نقطه پایین و سمت چپ به نقطه بالا و سمت راست رسید به شرطی که تنها مجاز به حرکت در سه جهت بالا،پایین و راست باشیم؟ (مجاز نیستیم از خطی دو بار عبور کنیم)
2.به چند طریق می توان r شیء متمایز را در n جعبه یکسان قرار داد به طوری که هیچ جعبه ای خالی نباشد؟
3.به چند طریق می توان 8 جایزه متمایز را بین 4 نفر تقسیم کرد به طوری که به هر یک حداقل یک جایزه برسد؟
4.یک دنباله 15 حرفی از حروف الفبای انگلیسی انتخاب شده است. (دنباله می تواند شامل حروف تکراری باشد) احتمال این که کلمه «combination» در آن ظاهر شود چقدر است؟
5.حداکثر چند مستطیل 4*1 را می توان در یک مربع 6*6 جا داد به طوری که هیچ دوتایی روی هم قرار نگیرند؟
6.حداقل چند عدد از مجموعه {30،...،1،2} باید حذف کرد،به نحوی که تفاضل هیچ دو عدد باقیمانده ای برابر 10 نشود؟

 

[ehsan-mokhtarian]

سوال 6:
10 تا:11و12و13و...و20 این اعداد را انتخاب کردم چون با حذف آن هم اعداد با اختلاف 10 کم تر از آن ها بتوانند بیایند و هم اعداد با اختلاف 10 بیشتر از آن

 

[AidinT]

1-

2-
r> n
می شه به این تبدیلش کرد:

بقیش رو هم اگه دوستان نگفتن بعداً می گم! فعلاً باید برم

 

[AidinT]

4-
اشتباه فکر کردم

 

[AidinT]

5- فکر می کنم هشت تا! مربع 6*6 رو با مربع های 2*2 رنگ می کنیم. حالا 5 تا مربع سیاه و 4 تا مربع سفید داریم(یا برعکس). هر مستطیل 4*1 که روی مربع بذاریم، 4 تا مربع 1*1 رو می پوشونه که 2 تاش سفید و دوتاش سیاست. پس تعداد سیاه ها و سفید ها باید با هم برابر باشه. ما 20 تا خونه ی سیاه و 16 تا خونه ی سفید داریم. max تعداد مستطیل ها رو x در نظر می گیریم. می گیم اگه 2x تا خونه ی سفید رو بپوشونه 2x تا خونه ی سیاه رو هم می پوشونه! می دونیم حداکثر 16 تا خونه ی سفید داریم که در عوضش می شه 16 تا خونه ی سیاه رو پوشوند. اما 20 تا خونه ی سیاه داریم و 20 تا خونه ی سفید نداریم. پس در نتیجه حداکثر 2x برابر 16 هست. پس x حداکثر هشته!

 

[AidinT]

راه حل من واسه سوال 6:
مجموعه ی اعداد 1 تا 30 رو به مجموعه اعدادی 3 عضوی به صورت زیر تعریف می کنیم.

r اعداد 1 تا 10 می تونه باشه در نتیجه 10 تا گروه با این ویژگی داریم. حالا از هرکدوم از این گروه ها باید اعدادی رو حذف کنیم. می گیم که اگه r رو حذف کنیم می تونیم r+10 رو نگه داریم و r+20 رو برداریم. یعنی با حذف r ها دو تا عدد از هر گروه حذف می شن. ولی با حذف r+10، می تونیم r+20 و r رو نگه داریم و این یعنی از هرگروه یک عضو رو حذف کنیم. حالا می دونیم که در حالت دوم تعداد کمتری رو حذف می کنیم. یعنی مینیموم تعداد حذفی هارو داریم. پس باید از ر گروه یکی رو حذف کنیم یعنی r+10 ها رو حذف کنیم. پس تعداد مینیموم حذفی ها می شه 10 تا!

 

[ehsan-mokhtarian]

می شه سوال 1 را بیشتر توضیح بدین

 

[ehsan-mokhtarian]

سوال 4:
به نظر من جواب این می شه:

چون این کلمه 11 حرف داره و در 5 قسمت مختلف کلمه می تواند بیاید و بقیه حروف (4 تا) هر کدام 26 حالت دارند

 

[AidinT]

می شه سوال 1 را بیشتر توضیح بدین

در هر مرحله باید از یک خط افقی عبور کنیم. پس هر مرحله n+1 انتخاب داریم. چون n+1 خط افقی و m مرحله داریم می شه:

 

[AidinT]

سوال 4:
به نظر من جواب این می شه:

چون این کلمه 11 حرف داره و در 5 قسمت مختلف کلمه می تواند بیاید و بقیه حروف (4 تا) هر کدام 26 حالت دارند

حالت تکراری داره دوست من! اگه دقت کنی می بینی که اگه جای دوتا o عوض شه، تغییری در ساختار کلمه بوجود نمیاد ولی عوض شدن جاشون یه جایگشت دیگه از ایناست. بعد اینکه چرا نوشتی 26 به توان 5؟

 

[ehsan-mokhtarian]

می شه سوال 1 را بیشتر توضیح بدین

در هر مرحله باید از یک خط افقی عبور کنیم. پس هر مرحله n+1 انتخاب داریم. چون n+1 خط افقی و m مرحله داریم می شه:

چرا باید در هر مرحله از یک خط افقی عبور کنیم؟

 

[ehsan-mokhtarian]

سوال 4:
به نظر من جواب این می شه:

چون این کلمه 11 حرف داره و در 5 قسمت مختلف کلمه می تواند بیاید و بقیه حروف (4 تا) هر کدام 26 حالت دارند

حالت تکراری داره دوست من! اگه دقت کنی می بینی که اگه جای دوتا o عوض شه، تغییری در ساختار کلمه بوجود نمیاد ولی عوض شدن جاشون یه جایگشت دیگه از ایناست. بعد اینکه چرا نوشتی 26 به توان 5؟

جای دوتا o ؟ این دیگه چیه؟
این کلمه در 5 جایه مختلف می تونه بیاد و بعد * 26^4 (اشتباه نوشتم 5)

 

[AidinT]

می شه سوال 1 را بیشتر توضیح بدین

در هر مرحله باید از یک خط افقی عبور کنیم. پس هر مرحله n+1 انتخاب داریم. چون n+1 خط افقی و m مرحله داریم می شه:

چرا باید در هر مرحله از یک خط افقی عبور کنیم؟

چون در هر مرحله می تونیم بالا یا پایین بریم، یعنی تعداد n+1 انتخاب در هر مرحله داریم(n+1 حالت برای حرکت داریم، اگه چندین بار حرکت بر روی یک خط افقی مجاز بود مطمئناً بی نهایت راه برای رسیدین به اون خط وجود داشت و چون اینطور نیست، فقط یک راه یکتا از یه خط افقی به یه خط افقی دیگه با فاصله ی یک مرحله وجود داره. در نتیجه برای n+1 خط، n+1 مسیر یکتا در هر مرحله وجود داره.) پس بعد از m مرحله و رسیدن به مرحله ی آخر

راه واسه انتخاب داریم. حالا توی مرحله ی آخر هر خطی انتخاب بشه برای رسیدن به نقطه ی بالا ، یک راه یکتا وجود داره!

 

[AidinT]

اشتباه شد

 

[ehsan-mokhtarian]

سوال 4:
به نظر من جواب این می شه:

چون این کلمه 11 حرف داره و در 5 قسمت مختلف کلمه می تواند بیاید و بقیه حروف (4 تا) هر کدام 26 حالت دارند

حالت تکراری داره دوست من! اگه دقت کنی می بینی که اگه جای دوتا o عوض شه، تغییری در ساختار کلمه بوجود نمیاد ولی عوض شدن جاشون یه جایگشت دیگه از ایناست. بعد اینکه چرا نوشتی 26 به توان 5؟

جای دوتا o ؟ این دیگه چیه؟
این کلمه در 5 جایه مختلف می تونه بیاد و بعد * 26^4 (اشتباه نوشتم 5)

combination حروف تکراری داره! در نتیجه یه جایگشت از این کلمه وجود نداره. توی

جایگشت، combination هشت بار تکرار می شه! بجای o اول، یک بار حرف x و به جای o دوم (که فرقی با o اول نداره) یک بار x رو قرار می دیم حالا جایگشت های 15 حرفی زیر رو ببین:

(A1 و ... بقیه ی حروف هستند) الان اینجا توی این حالت، دوتا جایگشت مختلف داریم که هر دو ساخته می شن ولی می دونیم هر دو با هم یکسانن! اینم حالت تکراریش!
می دونیم برای حروف تکراری به تعدادشون جایگشت تکراری داریم. پس چون دوتا o ، دوتا i و دوتا n داریم

جایگشت تکراری برای هر حالت خواهیم داشت.
پس احتمال می شه:

این چیه دیگه؟؟؟؟؟؟؟؟؟؟!!!!!!!!!!!!!
کلمه باید پشت سر هم بیاد... نمی لونی به جای oرا با x عوض کنی
من فکر کنم سوال درست متوجه نشدی...

 

[Sepehrmousavi]

جواب سوال 4 :

به وضوح معلوم است که جواب این میشود. اصلا هم ربطی به حالت تکراری و غیر تکراری ندارد چون هیچ جایگشت 15 حرفی ای در تعداد شمرده شده ، 2 بار شمرده نمی شود!

 

[AidinT]

بله من اشتباه کردم