المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۱

در ۳۰ کیسه ۳۲ کارت با شماره‌های ۱ تا ۳۲ ریخته‌ایم، به‌طوری‌ که هیچ کیسه‌ای خالی نیست و نیز اگر کارت $i$ در کیسه‌ی $k$ باشد، کارت $i + 1$ در کیسه‌ای با شماره‌ی کوچک‌تر از $k$ نیست. در ابتدا درِ کیسه‌ها بسته است و وقتی در یکی را باز می‌کنیم شماره‌ی کارت‌های آن را می‌بینیم. دست‌کم درِ چند کیسه را باید باز کنیم تا حتماً بتوانیم کارت ۱۳ را ببینیم؟

  1. ۲
  2. ۵
  3. ۶
  4. ۱۳
  5. ۳۲

پاسخ

گزینه (۱) درست است.

اولا معلوم می‌شود که کارت شماره $i$ نمی‌تواند در کیسه $i+1$ یا به بعد باشد زیرا در این صورت کارت‌های $i+1$ و بزرگ‌تر نیز در هیچ یک از کیسه‌های $i$ و قبل از $i$ قرار نخواهد گرفت که در چنین صورتی کیسه‌ای از کیسه‌های ۱ تا $i$ خالی می‌ماند. به همین دلیل کارت شماره $i$ در کیسه‌های $i-3$ و به قبل نیز نمی‌تواند باشد. بنابراین کارت شماره ۱۳ در یکی از کیسه‌های ۱۲٬۱۱ و یا ۱۳ قرار دارد. ابتدا کیسه ۱۲ را نگاه می‌کنیم که اگر کارت ۱۳ در آن بود٬ آن کارت پیدا شده است و اگر کارت ۱۲ در آن بود آن‌گاه کارت ۱۳ در کیسه‌ی ۱۳ قرار دارد و اگر کارت ۱۴ در آن باشد آن‌گاه کارت ۱۳ در کیسه ۱۱ قرار خواهد داشت.


ابزار صفحه