المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۶:سوال ۲۴

سوال ۲۴

اعداد ۰ تا ۶۴ به جز عدد ۳۲ در خانه‌های یک جدول که دارای ۲ سطر و ۳۲ ستون است به نحوی نوشته‌ شده‌اند که اعداد ۰ تا ۳۱ در سطر پایین قرار دارد و مجموع دو عدد هر ستون نیز برابر ۶۴ است. در هر مرحله می‌توانیم یک ستون را انتخاب کرده و از عدد خانه‌ی بالایی آن ستون، عدد $2^k$($0\le k$) را کم کرده و به عدد پایینی همان ستون اضافه کنیم. هدف این است که پس از تعدادی مرحله به جدولی برسیم که جای اعداد هر ستون آن نسبت به جدول اولیه تعویض شده باشد. برای مثال، در ستونی که اعداد ۴۷ و ۱۷ روبه‌روی هم نوشته شده‌اند، می‌توان پس از ۴ حرکت مطابق شکل زیر جای دو عدد را عوض کرد:

حداقل تعداد مراحل لازم برای تعویض دو عدد تمام ستون‌ها با هم‌دیگر و رسیدن به جدولی که نسبت به جدول ابتدایی قرینه شده باشد، برابر است با:

  1. ۳۳
  2. ۷۹
  3. ۸۰
  4. ۸۱
  5. ۱۹۳

پاسخ

گزینه (۴) درست است.

ابتدا باید اعداد را به مبنای ۲ تبدیل کرده و آن دو را به طوری در دو سطر بنویسیم که ارقام هم‌مرتبه بد زیر هم قرار گیرند. چون مجموع هر دو عدد موجود در یک ستون برابر ۶۴(که در مبنای ۲ به صورت $10^6$ قابل نمایش است) می‌باشد٬ بنابراین دو عدد موجود در یک ستون چنان‌اند که به ازای اولین «۱» از سمت راست د رعدد پایینی٬ رقم متناظرش در عدد بالایی نیز ۱ است. از آن رقم به قبل هر دو رقم متناظرح٬ در آن دو عدد تا جایگاه ششم از سمت راستح٬ باید متفاوت باشد تا مجموع به صورت $10^5$ در بیاید. به عنوان مثال در مورد دو عدد ۴۷ و ۱۷ که در صورت سوال اشاره شده است وضعیت٬ به قرار زیر می‌باشد: \[ \begin{array}{c c c c c c c c} 47 & \rightarrow & 1 & 0 & 1 & 1 & 1 & 1 \\ 17 & \rightarrow & 0 & 1 & 0 & 0 & 0 & 1 \\ جایگاه & \rightarrow & 2^5 & 2^4 & 2^3 & 2^2 & 2^1 & 2^0 \\ \end{array} \]

برای تبدیل اعداد بالایی به پایینی و برعکس٬ کافی است در مورد ستون‌های به شکل«$\begin{array}{c} 1 \\ 0 \\ 2^i \end{array}$» که جایگاه سمت راست آن به شکل«$\begin{array}{c} 0 \\ 1 \end{array}$» نمی‌باشد دقیقا $2^i$ واحد از عدد بالایی برداشته و به عدد پایینی اضافه کنیم و در مورد ستون‌های به شکل «$\begin{array}{c} 1 \\ 0 \\ 2^i \end{array}$» که یک یا چند ستون بلافاصله بعد از آن به شکل «$\begin{array}{c} 0 \\ 1 \end{array}$» می‌باشند٬ کافی است به اندازه $2^j$ از عدد بالایی برداشته و به عدد پایینی اضافه کنیم که $2^j$ جایگاه سمت راست‌ترین ستون به شکل «$\begin{array}{c} 0 \\ 1 \end{array}$» می‌باشد که در آن دو عدد وجود دارد. در مورد اعداد ۴۷ و ۱۷ مقادیر اضافه شده به ترتیب به صورت $2^1 , 2^2 ,2^3 و 2^4$ می‌باشد که از قاعده بالا پیروی می‌کنند.

بنابراین معلوم می‌شود که تعداد اعداد اضافه شده٬ برای تبدیل اعداد بالایی به اعداد پایینی یک واحد کم‌تر از تعداد «۱»های موجود در عدد بالایی می‌باشد.

اعداد ۳۳ تا۶۳ مجموعا ۱۱۱ تا ۱ دارند که اگر به ازای هر یک از عدد «۱» کم کنیم معلوم می‌شود که تعداد مراحل لازم برابر $111-31$ یعنی ۸۰ می‌شود. در مورد ستون مربوطه به دو عدد ۰ و ۶۴ نیز یک مرحله تعویض نیاز است. بنابراین جواب مورد نظر ۸۱ می‌شود.


ابزار صفحه