المپدیا

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

ابزار کاربر

ابزار سایت


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

پشت و رو کردن سکه‌ها

$n$ سکه در یک ردیف در کنار هم قرار دارند. بعضی از این سکه‌ها به رو و بعضی به پشت قرار گرفته‌اند. در هر حرکت می‌توانیم یکی از این $n$ سکه را انتخاب کنیم و آن سکه و سکه‌های مجاور سمت راست و سمت چپ آن را هم‌زمان برگردانیم (از رو به پشت یا از پشت به رو). توجه کنید که در صورتی که سکه‌ی انتخاب شده یکی از دو سکه‌ی انتهایی باشد، دو سکه و در غیر این صورت سه سکه برگردانده می‌شود.

الف) ثابت کنید که اگر $n=3k$ یا $n=3k+1$‌ باشد، به هر ترتیبی که سکه‌ها قرار گرفته باشند، با استفاده از چنین حرکت‌هایی می‌توانیم همه‌ی سکه‌ها را به رو برگردانیم. برای مثال اگر $n=4$‌و ترتیب اولیه‌ی سکه‌ها به صورت زیر باشد:

می‌توانیم اول سکه‌ی دوم (از سمت چپ)، سپس سکه‌ی اول و نهایتا سکه‌ی چهارم را انتخاب کنیم تا همه‌ی سکه‌ها به رو برگردانده شوند.

ب) ثابت کنید که برای هر $n$ که به صورت $n=3k+2$ باشد، وضعیت اولیه‌ای وجود دارد که برای آن با استفاده از این حرکت‌ها نمی‌توان این کار را ا نجام داد (یعنی همه‌ی سکه‌ها را به رو برگرداند).


ابزار صفحه