Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

رشته‌ها

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

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

پاسخ

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

لم ۱: اگر αβ=βα آن‌گاه α و β یک سازه‌ی مشترک دارند.

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

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

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

لم ۲: اگر α و β دو سازه‌ی مشترک A باشند، آن‌گاه α و β سازه‌ی مشترک دارند.

اثبات: چون α و β سازه‌های A هستند، برای هر k داریم:

kAAA=αα=ββ=X

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

X=w1w2wnn=k|α||β|d|wi|=d

از طرفی چون X=αα است، داریم wi=wi+l|α|d و چون X=ββ است، داریم wi=wi+l|β|d (برای هر l). از طرف دیگر با توجه به تعریف d، l1 و l2 وجود دارند که l1|α|l2|β|=d و در نتیجه l1|α|d=l2|β|d+1. بنابراین برای هر i داریم:

wi=wi+l1|α|d=wi+1+l2|β|d=wi+1w1=w2=

پس w=wi یک سازه‌ی مشترک برای β و α است.

نتیجه‌ی لم۲: اگر α1,,αn سازه‌های A باشند، آن‌گاه αi ها سازه‌ی مشترکی دارند.

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

اثبات مسئله: یک عضو از A را به دل‌خواه انتخاب می‌کنیم و آن را α می‌نامیم. برای هر βiA، بنا به فرض داریم αβi=βiα و در نتیجه بنا به لم ۱ نتیجه می‌شود که α و βi سازه‌ی مشترکی دارند که آن را wi می‌نامیم. حال همه‌ی wi ها را در نظر می‌گیریم. بنا به نتیجه‌ی لم ۲ این رشته‌ها دارای یک سازه‌ی مشترک هستند که آن را w می‌نامیم. چون w سازه‌ی wi و wi سازه‌ی βi است، پس w سازه‌ی مشترک همه‌ی βi هاست و بنابراین حکم ثابت می‌شود.


ابزار صفحه