مسابقه شماره ۲۵۱
سوال
در ۳۰ کیسه ۳۲ کارت با شمار‌ه‌های ۱ تا ۳۲
ریخته‌ایم ٫ به طوری که هیچ کیسه‌ای خالی
نیست و نیز اگر کارت i در کیسه k باشد٫ کارت i +
1 در کیسه‌ای با شماره کوچک‌تر از k
نیست. در ابتدا در کیسه‌ها بسته است و وقتی در
یکی را باز می‌کنیم شماره کارت‌های
آن را می‌بینیم. دست کم در چند کیسه را باید باز
کنیم تا حتما بتوانیم کارت ۱۳ را ببینیم ؟
پاسخ
اولا معلوم می‌شود که کارت شماره i نمی‌تواند در کیسه i + 1 یا به بعد باشد زیرا در این
صورت کارت‌های i + 1 و بزرگتر نیز در هیچ یک از کیسه‌های i و قبل از i قرار نخواهد گرفت
که در چنین صورتی کیسه‌ای از کیسه‌های از ۱ تا i خالی می‌ماند. به همین دلیل کارت
شماره i در کیسه‌های i - 3 و به قبل نیز نمی‌تواند باشد. بنابراین کارت شماره ۱۳ در یکی
از کیسه‌های ۱۱ ٫ ۱۲ و یا ۱۳ قرار دارد. ابتدا کیسه ۱۲ را نگاه می‌کنیم که اگر کارت ۱۳ در
آن بود ٫ آن کارت پیدا شده است و اگر کارت ۱۲ در آن بود آنگاه کارت ۱۳ در کیسه ۱۳ قرار
دارد و اگر کارت ۱۴ در آن باشد آنگاه کارت ۱۳ در کیسه ۱۱ قرار خواهد داشت.