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

 
 
 بازي با كارت (مسابقه‌ي شماره‌ي 73)
بازي با كارت (مسابقه‌ي شماره‌ي 73)مسابقه كامپيوتر
تركيبيات و استقراي قوي ... سؤال همراه با جواب

بازي با كارت





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



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




 

سؤال
يك دسته شامل 2000 كارت داريم كه روي آن‌ها اعداد 1 تا 2000 نوشته شده است. البته ترتيب قرار گرفتن كارت‌ها به‌ترتيب شماره‌ي اعداد روي آن نيست.

بالاترين كارت دسته‌ي مذكور را برداشته و روي ميز قرار مي‌دهيم. سپس كارت بعدي را برداشته و در زير همه‌ي كارت‌ها قرار مي‌دهيم. پس از آن بالاترين كارت را برداشته و سمت راست روي ميز قرار داده و كارت بعدي را زير همه‌ي كارت‌ها مي‌گذاريم.

همين روند را ادامه مي‌دهيم تا جايي كه همه‌ي كارت‌هاي دسته‌ي مذكور برداشته شده روي ميز قرار گيرد.

اگر كارت‌هاي روي ميز از چپ به راست داراي شماره‌هاي 1، 2، 3، ... و 2000 رديف شده باشند در اين صورت در دسته‌ي كارت‌ها چند كارت روي كارت شماره‌ي 1386 قرار داشته است؟




راهنمايي

الف - اگر يك كارت در دسته‌ي تايي روي هم قرار گرفته باشد اين كارت پس از اضافه كردن  كارت ديگر در دسته‌ي تايي حاصل، دوباره روي همه‌ي كارت‌ها قرار خواهد گرفت.

در نتيجه با 
«استقراي قوي» (Strong Induction) مي‌توان فهميد هرگاه تعداد كارت‌هاي دسته برابر  شود با اين شرط كه عددي طبيعي باشد و داشته باشيم:





در اين صورت، كارت شماره‌ي  روي دسته قرار خواهد گرفت.


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




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

فرض مي‌كنيم مي‌خواهيم عكس روند گفته شده را انجام دهيم يعني از روي وضعيت كارت‌هاي روي ميز در آخرين مرحله، دسته‌ي كارت‌هاي اوليه را ايجاد كنيم:

- ابتدا كارت شماره‌ي 2000 را برمي‌داريم و در دسته‌ي كارت‌ها قرار مي‌دهيم.

- سپس كارت شماره‌ي 1999 را برداشته و روي دسته مي‌گذاريم.

- سپس پايين‌ترين كارت دسته را روي دسته منتقل مي‌كنيم.

- بعد از آن، كارت شماره‌ي 1999 را برداشته روي دسته قرار مي‌دهيم.

- پايين‌ترين كارت را روي همه‌ي كارت‌ها مي‌گذاريم.

- و ...

با كمي دقت درمي‌يابيم اگر يك كارت در دسته‌ي تايي روي هم قرار گرفته باشد اين كارت پس از اضافه كردن  كارت ديگر در دسته‌ي تايي حاصل، دوباره روي همه‌ي كارت‌ها قرار خواهد گرفت.

در نتيجه با «استقراي قوي» (Strong Induction) مي‌توان فهميد هرگاه تعداد كارت‌هاي دسته برابر  شود با اين شرط كه  عددي طبيعي باشد و داشته باشيم:




(رابطه‌ي 1)

در اين صورت، كارت شماره‌ي 1999 روي دسته قرار خواهد گرفت.

با توجه به رابطه‌ي 2 مي‌توان مقدار حداكثر عدد  را يافت:




(رابطه‌ي 2)

بنابراين هنگامي كه تعداد كارت‌هاي دسته برابر  باشد كارت شماره‌ي 1386 براي آخرين بار روي دسته‌ي كارت‌ها قرار خواهد گرفت.

اكنون كارت‌هاي شماره‌ي 1 تا 464 روي ميز باقي مانده‌اند. در اين مرحله، يكي از اين كارت‌ها روي دسته و سپس يك كارت به زير دسته منتقل مي‌شود تا هنگامي كه آخرين كارت را از روي ميز برداشته آن را روي دسته قرار دهيم. بنابراين روي كارت شماره‌ي 1999 دقيقاً  كارت قرار خواهد داشت.





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

اكنون فرض كنيد دسته‌اي از كارت‌ها به‌تعداد  كارت داريم و مي‌خواهيم اين فرايند را روي آن‌ها انجام دهيم. بعد از آن‌كه 48 كارت روي ميز قرار داده و 48 كارت هم از روي دسته به زير دسته منتقل كرديم يك دسته‌ي 2000تايي باقي مي‌ماند. حال كارت‌هاي روي ميز را جمع كرده و اين روند را روي 1387 كارت باقي‌مانده ادامه مي‌دهيم.

در نهايت كارت ماقبل آخر روي ميز، كارتي خواهد بود كه در مكان ام در دسته‌ي 2048تايي كارت‌ها قرار خواهد داشت. اين كارت در دسته‌ي 2000تايي در مكان ام قرار مي‌گيرد يعني روي اين كارت 927 كارت ديگر قرار خواهد داشت..

1387/1/31 لينک مستقيم

فرستنده :
رسول HyperLink HyperLink 1387/2/25
مـتـن : کارتها به صورت 1, 1001, 2, 1002, 3و 1003 ... , 999و 1999, 1000, 2000 چیده شده است یعنی به ترتیب از ابتدا به صورت n و1000+n نوشته شده است.حالا اگه به مثلا 1003 نگاه کنیم میبینیم ششمین کارته یعنی کارته 2nام پس کارت شماره 1386 میشه کارت 772
پاسـخ : ايميل فرستنده: rasoul_fastness@yahoo.com
تاريخ ارسال: 1387/2/16

رسول جان!
ضمن تشكر از شما
راجع به علت جوابت با توجه به‌ فرايندي كه براي گذاشتن كارت‌ها در صورت مسأله گفته شده توضيح بده
براي راهنمايي يه راه اينه كه از فرايند معكوس استفاده كني (يعني از آخر به اول). ابتدا كارت 2000 را برداريم و در دسته‌ي كارت‌ها قرار بديم.
بعد كارت 1999 را برداشته و روي دسته قرار بدي.
بعد پايين‌ترين كارت دسته رو روي همه‌ي كارت‌ها مي‌ذاريم.
و ..
البته راه‌حل‌هاي ديگه‌اي هم وجود داره!
منتظر جوابت هستيم.
انشاءالله موفق باشي!
پايين‌ترين كارت
انشاءالله موفق باشي!

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.