سوال ۴۰

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

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

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

پاسخ

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

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

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

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

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

المپدیا