المپدیا

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

ابزار کاربر

ابزار سایت


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

بازی دور میز

$n$ نفر با شماره‌های ۱ تا $n$ $(n>1)$ دور میزی نشسته‌اند و هر کدام $k$‌ مهره در اختیار دارند. از نفر اول بازی زیر را شروع می‌کنیم. نفر اول مهره‌ی خود را به نفر دوم می‌دهد و از این به بعد هر نفر که از نفر قبلی خود یک مهره دریافت کرده باشد دو مهره به نفر بعدی خود می‌دهد و اگر دو مهره دریافت کرده باشد، یک مهره به نفر بعدی می‌دهد. در این بازی منظور از نفر بعدی، نزدیک‌ترین فرد در جهت عقربه‌های ساعت است. به محض آن که فردی مهره‌هایش را از دست بدهد از دور میز کنار می‌رود. مثلا اگر $k=1$ باشد، در ابتدای بازی نفر ۱ و ۲ از دور خارج می‌شوند.

الف) ثابت کنید اگر $k>1$ و $n$ توانی از ۲ باشد، بازی پایان می‌پذیرد.

ب) ثابت کنید اگر $k=1$ باشد، بازی تنها در صورتی پایان می‌یابد که $n-1$ یا $n-2$‌ توانی از ۲ باشد.


ابزار صفحه