Processing math: 100%

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

یک رشته‌ی 𝑛 رقمی از حروف A، B و C داریم. در هر مرحله می‌توانیم دو حرف متوالی و متفاوت از رشته در نظر بگیریم و آن‌ها را با حرف سوم جایگزین کنیم. منظور از حرف سوم، حرفی از مجموعه‌ی {A, B, C} است که در میان دو حرف گفته شده نیامده است. برای مثال می‌توانیم با تغییر حروف چهارم و پنجم (از سمت چپ) رشته‌ی ABCBAA آن را به ABCCCA تبدیل کنیم. فرض کنید تعداد حروف A، B و C در رشته‌ی گفته شده به ترتیب a، b و c باشد. باقیمانده‌ی a، b و c در تقسیم بر ۳ را به ترتیب ra، rb و rc در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد ar، br و cr برابر باشند، می‌توانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم.

پاسخ