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

 
 
 ظرف‌های گردو
ظرف‌های گردومسابقه كامپيوتر
مسابقه شمار ۱۹۰

سوال )سوال

 

            99 ظرف با تعدادی گردو در هر یک موجود است. این ظرف‌ها روی یک میز در یک ردیف قرار گرفته‌اند. هر بار

می‌توانیم 2 ظرف کنار هم را انتخاب کنیم و از هر کدام 1 گردو برداریم (هر دو باید حداقل 1 گردو داشته باشند.), یا به هر کدام 1 گردو اضافه کنیم. دو وضعیت از ظرف‌ها را قابل تبدیل به هم می‌نامیم اگر بتوان با شروع از هر کدام و با چند بار انجام این دو حرکت , به دیگری رسید. چند زوج متمایز از چهار وضعیت a,b,c وd به قابل تبدیلند؟

 


پاسخ

 

در هر مرحله دو گردو به کل گردوها اضافه و یا دو گردو از کل گردوها کم می‌شود , بنابراین اگر کل گردوها فرد باشد در نهایت نیز فرد , و اگر کل گردوها زوج باشد در نهایت نیز کل گردوها زوج خواهد بود. مجموع کل گردوها در حالا a,b,c وd به ترتیب فرد , زوج , فرد و زوج می‌باشد , بنابراین a به b, a به d , c به b و c به d قابل تبدیل نیستند. و اما a به c و نیز b به d قابل تبدیلند که نحوه‌ی  تبدیل هر یک به شکل زیر می‌باشد :

 

نحوه‌ی تبدیل a به c : اولی را رد کرده و پس از آن هر زوج متوالی را انتخاب کرده و گردو به آنها اضافه می‌کنیم.

  • اولی,دومی و سومی را رد کرده و پس از آن هر زوج متوالی را انتخاب کرده و گردو به آنها اضافه می‌کنیم.
  • اولی,دومی,سومی,چهارمی و پنجمی را رد کرده و پس از آن هر زوج متوالی را انتخاب کرده و گردو به آنها اضافه می‌کنیم.

اگر الگوریتم فوق را ادامه دهیم به حالت c خواهیم رسید.

 

نحوه‌ی تبدیل  b به d : زوج‌های (2 , 1),(4 , 3),...,(50 , 49),(51 , 50),(53 , 52),...,(99 , 98) را انتخاب کرده و به هر یک از اعضای 25 زوج اول یک گردو اضافه و از هر یک از اعضای 25 زوج دیگر یک گردو بر می‌داریم که به دنباله‌ی زیر خواهیم رسید:

 

2 , 3 , 4 , 5 , ... , 49 , 50 , 50 , 50 , 51 , ... , 95 , 96 , 97 , 98

 

  • زوج‌های (3 , 2 ) , (5 , 4) , ... , (49 , 48) را انتخاب کرده و به هر یک از اعضای آن زوج‌ها یک گردو اضافه و زوج‌های

(52 , 51),(54 , 53),...,(98 , 99) را انتخاب کرده و از هر یک از اعضای آن یک گردو بر می‌داریم که به دنباله‌ی زیر خواهیم رسید,

 

3 , 4 , 5 , ... , 49 , 50 , 50 , 50 , 50 , 50 , 51 , ... , 95 , 96 , 97

 

با تکرار الگوریتم  فوق پس از مدتی به دنباله‌ی متقارن زیر می‌رسیم:

 

50 , 51 , 50 , ... , 50 , 51 , 50 , 51 , 50 , 50 , 50  , 51 , 50 , 51 , 50 , ... , 50 , 51 , 50

 

باز با تکرار آن الگوریتم به دنباله‌ی d خواهیم رسید.

1391/4/6لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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