المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴۶

۱۳۷۶‎ سنگ‌ریزه و دو بازی‌کن داریم. هر بازی‌کن در نوبت خود می‌تواند ‎۱‎ یا ‎۲‎ یا ‎۴‎ سنگ‌ریزه برای خود بردارد. کسی که آخرین سنگ‌ریزه را بردارد برنده است. آیا فرد اول می‌تواند طوری بازی کند که حتماً برنده شود؟

پاسخ

در حالت کلی اگر تعداد سنگ‌ریزه‌ها مضربی از ۳ باشد نفر دوم و در غیر این صورت نفر اول می‌تواند برنده باشد. اگر تعداد سنگ‌ریزه‌ها $3n$ باشد و نفر اول ۱ یا ۴ سنگ‌ریزه بردارد نفر دوم با برداشتن ۲ سنگ‌ریزه باز تعداد سنگ‌ریزه‌ها را $3k$ نگه داشته و در نهایت برنده می‌شود و اگر نفر اولی ۲ سنگ‌ریزه بردارد نفر دوم با برداشتن ۱ سنگ‌ریزه باز تعداد سنگ‌ریزه‌ها را $3k$ کرده و برنده می‌شود. اگر تعداد سنگ‌ریزه‌ها $3k+r$ (۲ یا ۱$r=$) باشد آن‌‌گاه نفر اول با برداشتن $r$ سنگ‌ریزه تعداد سنگ‌ریزه‌ها را به $3k$ رسانده و ابتکار عمل را به دست می‌گیرد.


ابزار صفحه