سوال ۷
بازی سه‌نفره‌ی «عددسازی» به این صورت انجام می‌شود: سه نفر دور یک میز گرد می‌نشینند و به هریک از آن‌ها یک کارت داده می‌شود که روی آن ۰۱ و یا ۱۰ نوشته شده است. در ابتدا بازی‌کنی که از دیگران بزرگ‌تر است یک رقم دل‌خواه ۰ یا ۱ روی میز می‌نویسد و سپس به ترتیب ساعت‌گرد نوبت عوض می‌شود. هر کس در نوبت خود آخرین رقمی که روی میز نوشته شده را بررسی می‌کند. اگر ۰ بود رقم سمت راست کارتش و اگر ۱ بود رقم سمت چپ کارتش را در سمت راست عدد روی میز می‌نویسد. بازی آن‌قدر ادامه پیدا می‌کند تا کوچک‌ترین بازی‌کن خسته شود. تعیین کنید در بازی عددسازی چند تا از اعداد زیر ممکن است تولید شوند؟
۰۱۱۰۱۱۰۱۱۰۱۱۰
۰۰۱۱۰۰۱۱۰۰
۰۰۱۱۱۰۰۱۱۱۰۰
۰۱۱۱۰۰۰۱۱۱۰
۰۰۰۰۱۱۱۱۰۰۰۰
- ۱
- ۲
- ۳
- ۴
- ۵
پاسخ
گزینه (۲) درست است.
فرض می‌کنیم ابتدا $a$، سپس $b$ و در نهایت نیز $c$ به همین ترتیب بازی راانجام دهند. با بررسی ارقام دوم٬ سوم و چهارم از سمت دنباله‌های داده شده٬ کارت افراد $b$، $a$ و $c$ در هر یک از پنج دنباله داده شده به ترتیب از چپ به راست به صورت (۱۰٬۱۰٬۱۰) ٬ (۱۰٬۱۰٬۰۱) ٬ (۱۰٬۰۱٬۱۰) ٬ (۱۰٬۰۱٬۱۰) و (۰۱٬۱۰٬۰۱) در می‌آید که در ادامه بازی دنباله‌های دوم و پنجم از سمت چپ با کارت‌های به‌دست آمده سازگاری دارند ولی مابقی دنباله‌های این سازگاری را ندارند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
