مسابقه‌ی تصادفی

 
 
 باز هم ندا كوچولو! (مسابقه‌ي شماره‌ي 79)
باز هم ندا كوچولو! (مسابقه‌ي شماره‌ي 79)مسابقه كامپيوتر
روابط بازگشتي ... سؤال همراه با جواب

باز هم ندا كوچولو!






اشاره

آن‌چه با عنوان «چكيده» در اول مسابقه‌ها و زنگ‌تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.




چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي – دانش
    
- «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها و روش‌شناسي»
 اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    
- «فهميدن» > «ترجمه» > «تفسير»
    
- «فهميدن» > «ترجمه» > «كاربستن»
    
- «فهميدن» > «ترجمه» > «تركيب» < «توليد يك نقشه يا مجموعه‌ اقدام‌هاي پيشنهادي»
    
- «فهميدن» > «ترجمه» > «تركيب» < «استنتاج مجموعه‌اي از روابط انتزاعي»
 نتايج مورد نظر 
    
- آشنايي با احتمال
    
- آشنايي با روابط بازگشتي
    
- روش حل مسأله با استفاده از احتمال و روابط بازگشتي
 محتواي آموزشي
    
- احتمال
    
- روابط بازگشتي.




مقدمه
اصطلاح «اميد رياضي» (Expected Value) در «نظريه‌ي احتمال» (Probability Theory) كاربرد زيادي داشته و در مورد يك متغير گسسته‌ي تصادفي به‌كار مي‌رود و عبارت است از مجموع حاصل‌ضرب‌هاي هر نتيجه‌ي ممكن در مقدار نتيجه‌ي مذكور.

به‌عنوان مثال:
«اميد رياضي» (Expected Value) ظاهر شدن يك عدد در يك تاس شش‌وجهي از رابطه‌ي ذيل به‌دست مي‌آيد:








سؤال
«ندا كوچولو» شش طناب دارد. وي دو انتها از 12 انتهاي آزاد طناب‌ها را به‌صورت تصادفي انتخاب كرده آن‌ها را به‌هم گره زده 10 انتهاي آزاد ديگر را رها مي‌كند.

وي شش طناب دارد. دو انتها از 12 انتهاي آزاد طناب‌ها را به‌صورت تصادفي انتخاب كرده آن‌ها را به‌هم گره زده 10 انتهاي آزاد ديگر را رها مي‌كند.

وي مجدداً دو انتهاي آزاد را به‌صورت تصادفي انتخاب كرده و به يكديگر گره مي‌زند و به‌همين ترتيب ادامه مي‌دهد تا اين‌كه انتهايي آزاد باقي نماند.

با استدلال مقدار «اميد رياضي» مربوط به تعداد حلقه‌هاي طناب ايجاد شده توسط «ندا كوچولو» را تا پايان يافتن كامل عمليات گره زدن حساب كنيد.

ياداوري - انتخاب انتهاي آزاد براي گره زدن ممكن است از دو انتهاي يك طناب نيز انجام شود.




راهنمايي

ساده‌ترين راه‌حل آن است كه از توسعه‌ي «فرمول برگشتي» براي تعداد مورد انتظار حلقه‌ها - كه با طناب شروع مي‌شود – استفاده كرد. اما به هر حال ممكن است براي پيدا كردن «اميد رياضي» مربوط به تعداد حلقه‌هاي طناب ايجاد شده براي شمارش همه‌ي حلقه‌هاي امكان‌پذير به‌كار رود




جواب
راه‌حل اول

اجازه بدهيد  «اميد رياضي» در مورد تعداد حلقه‌ها براي اين فرايند با  طناب در شروع باشد. از لم ذيل براي حل مسأله استفاده مي‌كنيم:






(رابطه‌ي 1)

براي اثبات رابطه‌ي 1، فرايند را با  طناب شروع مي‌كنيم. بعد از انتخاب يك سر آزاد،  سر آزاد باقي مي‌ماند كه احتمال  براي انتهاي ديگر همان طناب در انتخاب دوم وجود خواهد داشت. اگر چنين امري واقع شود يك حلقه قبلاً تشكيل شده و به  طناب نيز دست نزده‌ايم. بنابراين «اميد رياضي» در مورد تعداد حلقه‌هاي تشكيل شده از رابطه‌ي ذيل به‌دست خواهد آمد:





(رابطه‌ي 2)

بدين‌ترتيب احتمالي برابر  براي انتخاب يك انتهاي يك طناب متفاوت با رها كردن  طناب (يكي بزرگ‌تر و  طناب كوچك‌تر) وجود خواهد داشت.

بنابراين مقدار «اميد رياضي» در مورد تعداد حلقه‌ها  خواهد بود. با تركيب دو احتمال رابطه‌ي ذيل به‌دست خواهد آمد:











(رابطه‌ي 3)

واضح است كه رابطه‌ي ذيل برقرار است:





(رابطه‌ي 4)
















(رابطه‌ي 5)

بنابراين اگر «صادق» داراي شش طناب باشد كه با انتخاب تصادفي دو سر آزاد در يك زمان به يكديگر گره بزند «اميد رياضي» در مورد تعداد حلقه‌هايي كه در پايان ايجاد خواهد كرد برابر  خواهد بود.





راه‌حل دوم
ابتدا در نظر بگيريد مي‌خواهيم تعداد راه‌هاي متفاوت براي گره زدن  طناب به يكديگر را محاسبه مي‌كنيم:

- اولين گره با رها كردن  انتهاي طناب‌ها با  روش مي‌تواند انجام مي‌شود.

- گره بعدي مي‌تواند با  روش، گره بعدي با  روش و ... انتخاب شود.

 

ترتيب گره‌ها اهميتي ندارد اما به هر حال بايد حاصل‌ضرب اين ضرايب چندجمله‌اي را بر تقسيم كنيم. بنابراين تعداد راه‌ها از رابطه‌ي ذيل به‌دست خواهد آمد:














(رابطه‌ي 6)

اكنون تعداد راه‌هاي گره زدن  طناب به يكديگر براي ايجاد حلقه را در نظر مي‌گيريم. طناب‌ها مي‌توانند پي در پي به يكديگر با ترتيبي دلخواه گره زده شوند به‌گونه‌اي كه  راه براي ترتيب انجام آن وجود داشته باشد.

اولين انتهاي اولين طناب مي‌تواند به هر انتهاي دومين طناب گره زده شود و سر باقي‌مانده‌ي دومين طناب به انتهاي سومين طناب و به‌همين ترتيب ادامه مي‌دهيم.

 راه براي انجام اين امر وجود دارد بنابراين كل تعداد راه‌ها براي گره زدن  طناب به يكديگر در يك «حلقه‌ي تك» از رابطه‌ي ذيل به‌دست خواهد آمد:





(رابطه‌‌ي 7)

نهايتاً مي‌توانيم تعداد كل حلقه‌ها بين همه‌ي گره‌هاي ممكن را بشماريم:

-  راه براي انتخاب يك طناب و  راه براي گره زدن آن به يك حلقه و  راه براي گره زدن بقيه‌ي طناب‌ها به يكديگر وجود دارد.

- به‌طور مشابه،  راه براي انتخاب دو طناب،  راه براي گره زدن آن‌ها به يك حلقه و  راه براي گره زدن چهار طناب‌ ديگر وجود خواهد داشت.

با توسعه‌ي اين فرايند، مي‌توان هر حلقه به هر ميزان بزرگي را شمارش كرد. بدين‌ترتيب تعداد كل حلقه‌ها از رابطه‌ي ذيل به‌دست خواهد آمد:





(رابطه‌ي 8)

از آن‌جايي كه رابطه‌ي ذيل در مورد تعداد گره‌ها صادق است:





(رابطه‌‌ي 9)

مقدار «اميد رياضي» در مورد تعداد حلقه‌ها از رابطه‌ي ذيل محاسبه خواهد شد:





(رابطه‌ي 10)

1387/3/10لينک مستقيم

فرستنده :
مريم علي اكبر پور HyperLink HyperLink 1387/3/14
مـتـن : واضح است در هر مرحله يكي از تعداد طناب ها كم مي شود. حال ممكن است حلقه اي ايجاد شود يا خير.در ضمن در هر حركت تنها يك حلقه ايجاد مي شود.(چون تنها دو سر را گره مي زنيم) حال مي توانيم تعداد حلقه هاي كل را مجموع تعداد حلقه هاي هر مرحله در نظر مي گيريم.
مي دانيم اگر در مرحله ي nام باشيم:
تعداد حلقه هاي ايجاد شده به احتمال n / C(2 * n, 2) يك است و به احتمال 1 - n / C(2 * n, 2) صفر است. ((C(n, m يعني انتخاب m شئ از n شئ. N! / ( m! (n-m)!))
طبق تعريف اميد رياضي جواب مسئله n / C(2 * n, 2) است براي n هاي بين 1 تا 6 است:
با ساده كردن عبارت n / C(2 * n, 2) برابر 1/(2n-1)
پس عدد اميد رياضي تقريباً =1.88
پاسـخ :ايميل فرستنده: Maryam.aliakbarpour@gmail.com
تاريخ ارسال: 1387/3/11

مريم جان!
از اين‌كه چنين با استدلال زيبا به جواب صحيح دست يافتي از تو تشكر مي‌كنيم.
ولي دوست خوبم!
راجع به جمله‌ي ذيل براي ما و دوستان توضيح بده:
«تعداد حلقه هاي ايجاد شده به احتمال n / C(2 * n, 2) يك است و به احتمال 1 - n / C(2 * n, 2) صفر است. ((C(n, m يعني انتخاب m شئ از n شئ. N! / ( m! (n-m)!))»
منتظرجوابت هستيم!
انشءالله موفق باش!

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  8215
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  8215