Processing math: 100%

سوال ۱۴

رشته‌ای از حروف الفبای انگلیسی داده شده است. در هر مرحله٬ می‌توان یکی از دو عمل زیر را انجام داد:

دو نمونه در این‌جا ذکر می‌کنیم: با انجام عمل اول می‌توان از SALAM به رشته‌‌ی SALMA رسید. با انجام عمل دوم می‌توان از SALAM به ASLSM و BALAM رسید. در کدام‌یک از گزینه‌های زیر می‌توان با انجام تعدادی از حرکات فوق‌الذکر٬ از رشته‌ی اول به رشته‌ی دوم رسید؟

  1. MASWQ SALAM
  2. ZYXXWWQQP ABCDDDEFF
  3. UDHQOYQOYOOY HHIJJIJJKHOL
  4. UOOQWERPPP IDKLMLJMJM
  5. QWKIOPX IDJKER

پاسخ

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

اگر در رشته‌ای حرفی وجود داشته باشد که nبار تکرار شده باشد٬ آن‌گاه در رشته نهایی نیز باید حرفی وجود داشته باشد که nبار تکرار شده باشد چون هیچ یک از دو عمل یاد شده تکرار حرفی در یک رشته به‌تعداد nبار را تغییر نمی‌دهد. همچنین شرط لازم برای آن‌که رشته‌ای بتواند از روی رشته دیگر به‌وجود آید آن است که تعداد حروف آن‌ها یکسان باشد. بنابراین اگر تعداد حروف تکراری دو رشته را به صورت دنباله‌ای مثلا نزولی بنویسیم باید دنباله‌های متناظر به دو رشته کاملا یکسان باشد. دنباله‌های متناظر به کلمات داده شده در گزینه‌ها به شکل زیر می‌باشند:

{(4,3,2,1,1,1)(4,3,2,1,1,1)=(ج {(3,2,1,1,1,1)(2,2,2,1,1,1)=(ب {(1,1,1,1,1,1)(1,1,1,1,1,1,1)=(الف

{(3,2,2,1,1,1)(3,2,1,1,1,1,1)=(ه {(2,1,1,1)(1,1,1,1,1)=(د