المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۶:سوال ۴

رشته‌ها

یک رشته، یک دنباله‌ی متناهی از صفر و یک است. $A$ یک مجموعه‌ی متناهی از رشته‌هاست که برای هر دو رشته‌ی دل‌خواه $ \alpha$ و $ \beta$ از آن داریم $\alpha \beta=\beta \alpha$. (منظور از $\alpha \beta$ رشته‌ای است که از کنار گذاشتن دو رشته‌ی $\alpha$ و $\beta$ به‌دست می‌آید. برای مثال اگر $\alpha=011$ و $\beta=10$ باشد، آن‌گاه $\alpha \beta=01110$ خواهد بود.)

ثابت کنید که رشته‌ای مانند $w$ وجود دارد که هر رشته‌ی دل‌خواه $A$ را می‌توان از کنار هم گذاشتن تعدادی $w$ به‌دست آورد.

پاسخ

در صورتی که رشته‌ی $\beta$ از کنار هم گذاشتن تعدادی رشته‌ی $\alpha$ تولید شود، $\alpha$ را یک سازه‌ی $\beta$ می‌نامیم. طول رشته‌ی $\alpha$ را با $|\alpha|$ نشان می‌دهیم. برای حل مسئله، ابتدا دو لم زیر را ثابت می‌کنیم:

لم ۱: اگر $\alpha \beta=\beta \alpha$ آن‌گاه $\alpha$ و $\beta$ یک سازه‌ی مشترک دارند.

اثبات: حکم را با استقرا روی $|\alpha \beta|$ ثابت می‌کنیم. اگر $|\alpha \beta|=|\alpha||\beta|=2$ باشد، حکم واضح است.

فرض می‌کنیم که برای هر $\alpha'$ و $\beta'$ که $\alpha' \beta'=\beta' \alpha'$ و $|\alpha' \beta'|<|\alpha \beta|$ حکم برقرار باشد و حکم را برای $\alpha$ و $\beta$ به این صورت ثابت می‌کنیم: اگر فرض کنیم $|\beta|<|\alpha|$، چون $\alpha \beta=\beta \alpha=A$ است، در نتیجه $|\alpha|$ رقم اول $A$ از طرفی $|\alpha|$ و از طرف دیگر همان $\alpha$ رقم اول $\beta$ است. بنابراین $\beta=\alpha \beta'$ است. پس $\alpha \alpha \beta'= \alpha \beta=\beta \alpha=\alpha \beta'\alpha$ و در نتیجه $\alpha \beta'=\beta' \alpha$ است. حال با توجه به این که $|\alpha \beta'|$ از $|\alpha \beta|$ کم‌تر است، با استفاده از فرض استقرا نتیجه می‌گیریم که $\alpha$ و $\beta'$ سازه‌ی مشترک دارند که این سازه‌ی مشترک چون هم $\alpha$ و هم $\beta'$ را می‌سازد، پس $\beta=\alpha \beta'$ را نیز می‌سازد.

در صورتی که $|\alpha|<|\beta|$ باشد نیز به همین صورت می‌توان استدلال کرد. همچنین اگر $|\alpha|=|\beta|$ باشد، $\alpha$ و $\beta$ باهم برابرند و در نتیجه سازه‌ی مشترک دارند.

لم ۲: اگر $\alpha$ و $\beta$ دو سازه‌ی مشترک $A$ باشند، آن‌گاه $\alpha$ و $\beta$ سازه‌ی مشترک دارند.

اثبات: چون $\alpha$ و $\beta$ سازه‌های $A$ هستند، برای هر $k$ داریم:

$$\overbrace{ AA…A }^{k}=\alpha … \alpha= \beta … \beta=X$$

$d$ را برابر بزرگ‌ترین مقسوم علیه مشترک $|\beta|$ و $|\alpha|$ می‌گیریم. فرض می‌کنیم:

$$X=w_1w_2 … w_n \quad\quad\quad\quad\quad\quad n=\frac{k|\alpha||\beta|}{d} \quad\quad\quad\quad\quad\quad |w_i|=d$$

از طرفی چون $X=\alpha … \alpha$ است، داریم $w_i=w_{i+\frac{l|\alpha|}{d}}$ و چون $X= \beta … \beta$ است، داریم $w_i=w_{i+\frac{l|\beta|}{d}}$ (برای هر $l$). از طرف دیگر با توجه به تعریف $d$، $l_1$ و $l_2$ وجود دارند که $l_1|\alpha|-l_2|\beta|=d$ و در نتیجه $\frac{l_1|\alpha|}{d}=\frac{l_2|\beta|}{d}+1$. بنابراین برای هر $i$ داریم:

$$w_i=w_{i+\frac{l_1|\alpha|}{d}}=w_{i+1+\frac{l_2|\beta|}{d}}=w_{i+1} \Rightarrow w_1=w_2=…$$

پس $w=w_i$ یک سازه‌ی مشترک برای $\beta$ و $\alpha$ است.

نتیجه‌ی لم۲: اگر $\alpha_1,…,\alpha_n$ سازه‌های $A$ باشند، آن‌گاه $\alpha_i$ ها سازه‌ی مشترکی دارند.

اثبات نتیجه‌ی فوق واضح است.

اثبات مسئله: یک عضو از $A$ را به دل‌خواه انتخاب می‌کنیم و آن را $\alpha$ می‌نامیم. برای هر $\beta_i \in A$، بنا به فرض داریم $\alpha \beta_i=\beta_i\alpha$ و در نتیجه بنا به لم ۱ نتیجه می‌شود که $\alpha$ و $\beta_i$ سازه‌ی مشترکی دارند که آن را $w_i$ می‌نامیم. حال همه‌ی $w_i$ ها را در نظر می‌گیریم. بنا به نتیجه‌ی لم ۲ این رشته‌ها دارای یک سازه‌ی مشترک هستند که آن را $w$ می‌نامیم. چون $w$ سازه‌ی $w_i$ و $w_i$ سازه‌ی $\beta _i$ است، پس $w$ سازه‌ی مشترک همه‌ی $\beta_i$ هاست و بنابراین حکم ثابت می‌شود.


ابزار صفحه