المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۸:سوال ۱

وزنه‌ها

$n$ عدد وزنه‌ی متفاوت با وزن‌های $2^0$,$2^1$,…, تا $2^{n-1}$ (از هرکدام یک عدد)٬ و یک ترازوی دو کفه‌ای در اختیار داریم. وزن هر وزنه بر روی آن نوشته شده است. در ابتدای کار٬ هیچ وزنه‌ای بر روی ترازو قرار ندارد. در هر حرکت یکی از وزنه‌هایی که روی ترازو نیست را برداشته و روی یکی از کفه‌های ترازو قرار می‌دهیم؛ پس از این کار٬ اگر کفه‌ی سمت چپ ترازو پایین‌تر بود (سنگین‌تر بود)٬ حرف $L$ و اگر کفه‌ی سمت راست ترازو پایین‌تر بود٬ حرف $R$ را روی کاغذ می‌نویسیم. (می‌توان نشان داد که کفه‌ها هیچ وقت مساوی نمی‌شوند!) این کار را به همین ترتیب ادامه می‌دهیم. دقت کنید حروف را به ترتیب پشت سر هم می‌نویسیم. هم‌چنین توجه کنید که هرگز حق نداریم که وزنه‌ای را از روی یک کفه برداریم. با این حساب وقتی وزنه‌ای روی یک کفه قرار گرفت تا پایان کار همان‌جا باقی می‌ماند.

در پایان‌ کار٬ یعنی زمانی که همه‌ی وزنه‌ها روی ترازو قرار گرفتند٬ یک رشته به طول $n$ از حروف $L$ و $R$ ایجاد می‌شود. ثابت کنید که به ازای هر شته به طول $n$ از $L$ و $R$٬ می‌توان وزنه‌ها را به ترتیبی روی ترازو قرار داد که رشته مورد نظر ساخته شود.


ابزار صفحه