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

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

سوال )سوال

 

            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 لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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