تفاوت دو نسخهی متفاوت از صفحه را مشاهده میکنید.
سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۲۷:سوال_یک [2018/04/12 13:37] مهدی بهروزی خواه |
سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۲۷:سوال_یک [2020/07/10 09:00] (فعلی) امیر محمد ایمانی |
||
---|---|---|---|
خط 1: | خط 1: | ||
====== رشته (۲۵ نمره) ====== | ====== رشته (۲۵ نمره) ====== | ||
- | یک رشتهی 𝑛 رقمی از حروف $A$، $B$ و $C$ داریم. در هر مرحله میتوانیم دو حرف __متوالی__ و __متفاوت__ از رشته در نظر بگیریم و آنها را با حرف سوم جایگزین کنیم. منظور از حرف سوم، حرفی از مجموعهی {$A$, $B$, $C$} است که در میان دو حرف گفته شده نیامده است. برای مثال میتوانیم با تغییر حروف چهارم و پنجم (از سمت چپ) رشتهی $ABCBAA$ آن را به $ABCCCA$ تبدیل کنیم. فرض کنید تعداد حروف $A$، $B$ و $C$ در رشتهی گفته شده به ترتیب $a$، $b$ و $c$ باشد. باقیماندهی $a$، $b$ و $c$ در تقسیم بر ۳ را به ترتیب $a_r$، $b_r$ و $c_r$ در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد $a_r$، $b_r$ و $c_r$ برابر باشند، میتوانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم. | + | |
+ | یک رشتهی 𝑛 رقمی از حروف $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$ برابر باشند، میتوانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم. | ||
<پاسخ> | <پاسخ> | ||
+ | |||
</پاسخ> | </پاسخ> | ||
* [[سوال دو|سوال بعد]] | * [[سوال دو|سوال بعد]] | ||