المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۲

۳۰ دانش‌آموز در یک کلاس حضور دارند که همه‌ی آن‌ها افرادی راست‌گو هستند. می‌دانیم یکی از آن‌ها المپیادی است ولی او را نمی‌شناسیم. می‌خواهیم با پرسیدن $k$ سؤال، فرد مزبور را بیابیم. در هر سؤال می‌توانیم یکی از دانش آموزان را انتخاب کنیم و به او اسم چند نفر از دانش آموزان را بگوییم و از او بپرسیم که آیا فرد المپیادی، یکی از آن چند نفر است یا خیر؟ او هم فقط به این سؤال جواب «بله» یا «خیر»می‌دهد. $k$ حداقل چه قدر باشد که با پرسیدن $k$ سؤال همواره مطمئن باشیم می‌توانیم فرد موردنظر را بشناسیم؟

  1. ۳
  2. ۵
  3. ۷
  4. ۱۰
  5. ۱۵

پاسخ

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

به هر دانش‌آموز یک کد از ۱ تا ۳۰ داده و شماره او را در مبنای ۲ در نظر می‌گیریم. معلوم است که در آن مبنا شماره هر فرد حداکثر پنج رقمی است. بنابراین پنج لیست به نام‌های $A$،$B$،$C$،$D$ و $E$ در نظر گرفته و هریک از آن‌ها را متناظر به یکی از ارقام پنج‌گانه اعداد در مبنای ۲ قرار می‌دهیم. در جایگاه‌هایی که رقم ۱ باشد در لیست متناظر اسم فرد را می‌نویسیم و در غیر این صورت اسم او را در آن لیست نمی‌نویسیم. به عنوان مثال اسم نفر یازدهم در لیست‌های $A$،$B$ و $D$ نوشته شده ولی در لیست‌های پنج‌گانه را به یک نفر نشان می‌دهیم و او اطلاع می‌دهد که فرد المپیادی در کدام یک از لیست‌های پنج‌گانه قرار دارد که به این ترتیب شماره آن فرد شناسایی خواهد شد.


ابزار صفحه