مسابقه شمار ۱۹۰
|
سوال )سوال
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 خواهیم رسید.