المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۹:سوال ۳۰

سوال ۳۰

۱۷ عدد مطابق شکل زیر در ۱۷ خانه به شماره‌های ۱ تا ۱۷ قرار گرفته‌اند. می‌گوییم عدد موجود در خانه‌ي $j$ «پدر» عدد موجود در خانه‌ی $i$ است٬ اگر $j= \lfloor{\frac i2}\rfloor$ باشد ($\lfloor x \rfloor$ برابر بزرگ‌ترین عدد صحیحی است که از $x$ بزرگ‌تر نیست). روشن است که عدد موجود در خانه‌ی اول بی‌پدر است! اگر هر عدد از پدرش اکیداً کوچک‌تر باشد٬ این پدیده را مینیاتوری می‌نامیم. دقت کنید جدول زیر مینیاتوری است.

ما یکی از این اعداد را تغییر می‌دهیم. می‌خواهیم فقط با استفاده از تعدادی «عمل مجاز» دوباره اعداد را به صورت مینیاتوری درآوریم. عمل مجاز «جابه‌جایی یک عدد با پدرش» است.

اگر عدد ۱۸ (عدد اول) را به ۵ تغییر دهیم چند عمل مجاز لازم است؟

  1. ۲
  2. ۳
  3. ۴
  4. ۵
  5. ۶

پاسخ

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

برای جابه‌جایی هر عدد دو انتخاب داریم (هر پدری دو فرزند دارد). اگر با فرزندی که کوچک‌تر است جابه‌جا کنیم همچنان توازن برقرار نخواهد شد (چون فرزند کوچک‌تر از فرزند بزرگ‌تر، کوچک‌تر است!). در نتیجه همواره باید با فرزند بزرگ‌تر جابه‌جایی صورت بگیرد.

در نتیجه باید در گام اول با ۱۶، سپس با ۱۵ و در نهایت با ۶ جابجا کنیم. پس سه حرکت لازم و کافی است.


ابزار صفحه