المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:ترکیبیات:سوال ۱

سوال ۱

مجلس کشور شنگولستان، در پی حرکتی نادر، می‌خواهد وزیر المپیاد کشور را محاکمه کند‎!‎ روش محاکمه به این صورت است که ابتدا اعداد ‎$0‎, ‎1‎, ‎2‎, ‎3‎, ‎\ldots‎, ‎2^{2n}$‎ روی تخته نوشته می‌شود. سپس رئیس مجلس ‎$2^{2n-1}$‎ عدد را از روی تخته پاک می‌کند. در مرحله‌ی بعدی، وزیر ‎$2^{2n-2}$‎ عدد را از روی تخته پاک می‌کند. دوباره مجلس ‎$2^{2n-3}$‎ عدد را از روی تخته پاک می‌کند و بازی همین‌طور ادامه پیدا می‌کند. پس از ‎$2n$‎ حرکت، بازی تمام می‌شود و ‎۲‎ عدد روی تخته باقی می‌ماند. وزیر باید به اندازه‌ی اختلاف ‎۲‎ عدد باقی‌مانده، به مجلس جریمه بپردازد.

رئیس مجلس، خود یک المپیادی قهّار بوده است و صرفن به خاطر مسائل رقابتی دوران جوانی، این محاکمه را به راه انداخته است. وزیر المپیاد کشور نیز، یک المپیادی بسیار باهوش است. بنابراین هر ‎۲‎ فرد، به‌ترین بازی ممکن را انجام می‌دهند. در پایان بازی وزیر چند تومان به مجلس خواهد پرداخت؟


ابزار صفحه