المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

می‌توان یک دنباله از اعداد را این‌گونه تغییر داد که ‎۳‎ عدد پشت‌سرهم $b،a$ و ‎$c$‎ از دنباله را پاک‌ کرد و به جای آن‌ها عدد ‎$a+c-b$‎ را در همان مکان قرارداد. مثلاً رشته‌ی ‎$(1,2,8,4,7)$‎ را می‌توان به ‎$(1,-2,7)$‎ و همچنین ‎$(1,-2,7)$‎ را به ‎$(10)$‎ تبدیل کرد. چند دنباله از دنباله‌های زیر را می‌توان به ‎$(0)$‎ تبدیل کرد؟

$$(7,7,7,6,6,6,5,5,5,5)$$

$$(2,4,-1,7,8,4,9,3,1)$$

$$(1,1,1,1,1,1,1,1,2)$$

$$(4,4,3,7,1,9,8,5,6)$$

$$(8,7,5,7,3,6,7,7,4)$$

  1. ۰
  2. ۱
  3. ۲
  4. ۳
  5. ۵

پاسخ

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

اولا در هر مرحله دو عضو از اعضای دنباله کم می‌شود٬ بنابراین برای آن که در انتهای کار فقط یک عدد باقی بماند لازم است تعداد اعضای دنباله فرد باشد. ثانیا می‌دانیم زوجیت عدد $a+b+c$ با زوجیت عدد $a+c-b$ یکی است٬ بنابراین برای آن که در انتهای کار عددی زوج باقی بماند لازم است مجموع اعداد زوج باشد. ثالثا با تکرار عمل اشاره شده صرف نظر از آن‌که $b،a$ و ‎$c$‎ کدام سه عدد متوالی باشند عدد نهایی برای دنباله‌ی $x_1,x_2,x_3,...,x_9$، عدد $x_1-x_2+x_3-x_4+...-x_8+x_9$ می‌باشد.

تنهادنباله‌ای از دنباله‌های داده شده که در هر سه شرط فوق صدق می‌کند دنباله‌ی زیر می‌باشد:

$$(8,7,5,7,3,6,7,7,4)$$


ابزار صفحه