المپدیا

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

ابزار کاربر

ابزار سایت


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

صنودوقچه‌های پر رمز و راز

$n$ صندوقچه‌ی جادویی با شماره‌های ۱ تا $n$ داریم. زیر هر صندوقچه٬ یک عدد بین ۱ تا $n$ نوشته شده است (ممکن است اعداد نوشته شده در زیر چند صندوقچه با هم یکسان باشند). توجه کنید ما نمی‌توانیم اعداد نوشته‌شده در زیر صندوقچه‌ها را بخوانیم.

در هر صندوقچه تعدادی یاقوت سرخ وجود دارد. ابتدا در همه‌ی صندوقچه‌ها بسته است٬ ولی می‌توان هربار در ِ یک صندوقچه را باز کرد٬ تعداد یاقوت‌های درون آن را شمرد و درِ آن را بست. نکته‌ی اسرارآمیز این صندوقچه‌ها آن است که به محض بستن درِ یک صندوقچه تمامی یاقوت‌های درون آن به صندوقچه‌ای منتقل می‌شوند که شماره‌ی آن٬ زیر این صندوقچه نوشته شده است.

به عنوان مثال٬ به جدول زیر توجه کنید:

اگر در ابتدا درِ صندوقچه‌ شماره‌ی ۳ را باز کنیم٬ ۳ یاقوت می‌بینیم ولی به محض بستن درِ آن٬ این صندوقچه خالی شده و تمام یاقوت‌های آن به صندوقچه‌ی شماره ۱ منتقل می‌شود. حال اگر درِ صندوقچه‌ی شماره ۲ را باز کنیم٬ ۸ یاقوت می‌بینیم ولی با بستن در ٬ چون زیر این صندوقچه عدد ۲ نوشته شده است ۸ یاقوت در همین صندوقچه باقی می‌مانند. سپس اگر درِ صندوقچه‌ی شماره‌ی ۱ را باز کنیم٬ ۹ یاقوت می‌بینیم (۶ یاقوت از قبل و ۳ یاقوت از صندوقچه‌ی شماره‌ی ۳). با بستن درِ آن٬ این صندوقچه هم خالی می‌شودو اکنون در صندوقچه‌ی شماره‌ی ۲ ٬ ۱۷ یاقوت موجود است. اگر دوباره درِ صندوقچه‌ی شماره‌ی ۱ را باز کنیم یاقوتی نمی‌بینیم.

توجه کنید که مجاز نیستیم هم‌زمان درِ چند صندوقچه‌ را باز کنیم یا به یاقوت‌ها دست بزنیم؛ فقط می‌توانیم در یک صندوقچه‌ی دل‌خواه را باز کنیم٬ یاقوت‌های درون آن را بشماریم و درِ آن را ببندیم.

ثابت کنید با انجام عمل فوق (به تعداد دل‌خواه) می‌توان از تعداد کل یاقوت‌ها مطلع شد.


ابزار صفحه