المپدیا

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

ابزار کاربر

ابزار سایت


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

رساندن مهره

یک سطر نامتناهی از خانه‌های $1\times1$ با شماره‌های ۲،۱ و … داده شده است. در ابتدا دو مهره در خانه های ۱ و ۲ قرار دارند. درهر مرحله، یکی از دو مهره را به دل‌خواه انتخاب می‌کنیم واگر این مهره در خانه‌ی شماره‌ی $i$ باشد، آن را $i$ خانه‌ی خالی به جلو می‌بریم. یعنی در صورتی که مهره‌ی دیگر در خانه‌های $i+1$ تا $2i$ نباشد، آن را به خانه‌ی $2i$ و در غیر این صورت به خانه‌ی $2i+1$ می‌بریم.

ثابت کنید که برای هر عدد طبیعی $n$ ($n>2$)، می‌توان با انجام تعدادی حرکت یکی از مهره‌ها را به خانه‌ی $n$ام برد.


ابزار صفحه