المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۷:سوال یک

رشته (۲۵ نمره)

یک رشته‌ی 𝑛 رقمی از حروف $A$، $B$ و $C$ داریم. در هر مرحله می‌توانیم دو حرف متوالی و متفاوت از رشته در نظر بگیریم و آن‌ها را با حرف سوم جایگزین کنیم. منظور از حرف سوم، حرفی از مجموعه‌ی {$A$, $B$, $C$} است که در میان دو حرف گفته شده نیامده است. برای مثال می‌توانیم با تغییر حروف چهارم و پنجم (از سمت چپ) رشته‌ی $ABCBAA$ آن را به $ABCCCA$ تبدیل کنیم. فرض کنید تعداد حروف $A$، $B$ و $C$ در رشته‌ی گفته شده به ترتیب $a$، $b$ و $c$ باشد. باقیمانده‌ی $a$، $b$ و $c$ در تقسیم بر ۳ را به ترتیب $r_a$، $r_b$ و $r_c$ در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد $a_r$، $b_r$ و $c_r$ برابر باشند، می‌توانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم.

پاسخ


ابزار صفحه