You are not allowed to perform this action

سؤال ۳۲

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

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

پاسخ

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

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

▸ سوال قبل سوال بعد ◂