Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۱

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

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

پاسخ

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

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


ابزار صفحه