Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۷:سوال ۴۰

سوال ۴۰

رشته مخصوص را به صورت زیر تعرف می‌کنیم:

  • a یک رشته‌ی مخصوص است.
  • b یک رشته‌ی مخصوص است.
  • اگر S یک رشته‌ی مخصوص باشد aSa و bSb نیز رشته‌های مخصوص هستند.

کدام یک از خواص زیر در مورد رشته‌های مخصوص درست است؟

  1. هر رشته مخصوص متقارن است.
  2. در هر رشته مخصوص قدر مطلق تفاوت تعداد aها با تعداد bها برابر یک است.
  3. هر رشته مخصوص به شکل WaW یا WbW است به طوری که W رشته مخصوص از a و b باشد.
  4. گزینه‌های ۱ و ۲ و ۳ درست هستند.
  5. گزنه‌های ۱ و ۳ درست هستند.

پاسخ

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

گزینه‌ی ۱ درست است٬ زیرا a و b هر دو متقارن هستند. اگر S متقارن باشد٬ آن‌گاه S=aSa و یا S=bSb نیز متقارن خواهد بود.

گزینه‌ی ۲ نادرست است زیرا aaa رشته‌ی مخصوص است و تفاوت تعداد aها با تعداد bها برابر یک نیست.

گزینه‌ی ۳ نادرست است. به عنوان مثال‌های نقض می‌توان به رشته‌های مخصوص baaab و babab اشاره کرد که هیچ کدام به صورت WaW یا WbW نیستند.

پس معلوم می‌شود که در نهایت گزینه‌ی «۱» درست است.


ابزار صفحه