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

 
 
 خانه و اعداد
خانه و اعدادمسابقه كامپيوتر
مسابقه شماره ۱۹۲

اعداد 0 تا 64 به جز عدد 32 در خانه‌های یک جدول که دارای 2 سط و 32 ستون است به نحوی نوشته شده‌اند که اعداد 0 تا 31 در سطرپایین قرار دارد و مجموع دو عدد هر ستو نیز برابر 64 است. در هر مرحله می‌توانیم یک ستون رو انتخاب کرده و از عدد خانه بالایی آن ستون, عدد 2k (k≥0)  را کم کرده و به عدد پایینی همان ستون اضافه می‌کنیم. هدف این است که پس از تعدادی مرحله به جدولی برسیم که جایی اعداد هر ستون آن نسبت به جدول اولیه تعویض شده باشد. برای مثال , در ستونی که اعداد 47 و 17 روبه‌روی هم نوشته شده‌اند, می‌توان پس از 4 حرکت مطابق شکل زیر جای دو عدد را عوض کرد:

 


حداقل تعداد مراحل لازم برای تعویض دو عدد تمام ستون‌ها با همدیگر و رسیدن به جدولی که نسبت به جدول ابتدایی قرینه شده باشد, برابر است با:
الف) 33                            ب) 193
  ج) 81                             د) 79
 هـ) 80
 


پاسخ

ابتدا باید اعداد را به مبنای 2 تبدیل کرده و آن دو را به طوری در دو سطر بنویسیم که ارقام هم‌مرتبه در زیر هم قرار گیرند. چون مجموع هر دو عدد موجود در یک ستون برابر 64 (که در مبنای 2 به‌صورت 1000000 قابل نمایش است) می‌باشد, بنابراین دو عدد موجود در یک ستون چنانند که به‌ازای اولین  ((1)) از سمت راست در عدد پایینی , رقم متناظرش در عدد بالایی نیز 1 است. از آن رقم به قبل هر دو رقم متناظر, در آن دو عدد تا جایگاه ششم از سمت راست , باید متفاوت باشد تا مجموع به صورت 100000 در بیاید. به عنوان مثال در مورد دو عدد 47 و 17 که در صورت سوال اشاره شده است وضعیت , به قرار زیر می‌باشد:

 

 


برای تبدیل اعداد بالایی به پایینی و بر عکس , کافی است در مورد ستون‌های به شکل  که جایگاه سمت راست آن به شکل  نمی‌باشد دقیقا 2i  واحد از عدد بالایی برداشته و به عدد پایینی اضافه کنیم و در مورد ستون‌های به شکل   که یک یا چند ستون بلافاصله بعد از آن به شکل می‌باشند, کافی است به اندازه2j  از عدد بالایی برداشته و به عدد پایینی اضافه کنیم که2j  جایگاه سمت راست‌ترین ستون به شکل می‌باشد که در آن دو عدد وجود دارد. در مورد اعداد 47 و 17 مقادیر اضافه شده به ترتیب به صورت 21 , 22 , 23 و 24 می‌باشد که از قاعده بالا پیروی می‌کنند.
اعداد از 33 تا 63 مجموعا 111 تا 1 دارند که اگر به ازای هر یک از اعداد ((1)) کم کنیم معلوم می‌شود که تعداد مراحل لازم برابر 31 – 111 یعنی 80 می‌شود. در مورد ستون مربوطه به دو عدد 0 و 64 نیز یک مرحله تعویض نیاز است. بنابراین جواب مورد نظر 81 می‌شود.

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

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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