مسابقه شماره ۲۳۹
سوال
30 دانش‌آموز در یک کلاس حضور دارند که همه آنها افرادی راست‌گو هستند. می‌دانیم یکی از آنها المپیادی است ولی او را نمی‌شناسیم. می‌خواهیم با پرسیدن k سوال , فرد مزبور را بیابیم. در هر سوال می‌توانیم یکی از دانش‌آموزان را انتخاب کنیم و به او اسم چند نفر از دانش‌آموزان را بگوییم و از او بپرسیم که آیا فرد المپیادی , یکی از آن چند نفر است یا خیر؟ او هم فقط به این سوال جواب بله یا خیر می‌دهد. k حداقل چقدر باشد که با پرسیدن k سوال همواره مطمئن باشیم می‌توانیم فرد مورد نظر را بشناسیم.
پاسخ
به هر دانش‌آموز یک کد از 1 تا 30 داده و شماره او را در مبنای 2 د ر نظر می‌گیریم. معلوم است که در آن مبنا شماره هر فرد حداکثر پنج رقمی است. بنابراین پنج لیست به نام‌های A,B,C,D و E در نظر گرفته و هر یک از آنها را متناظر به یکی از ارقام پنج‌گانه اعداد در مبنای 2 قرار می‌دهیم. در جایگاه‌هایی که رقم 1 باشد در لیست متناظر اسم فرد را می‌نویسیم و در غیر اینصورت اسم او را در آن لیست نمی‌نویسیم. به عنوان مثال اسم نفر یازدهم در لیست‌های A,B و D نوشته شده ولی در لیست‌های C و E نوشته نمی‌شود , زیرا عدد 1 در مبنای 2 به شکل 01011 نوشته می‌شود. لیست‌های پنج‌گانه را به یک نفر نشان می‌دهیم و او اطلاع می‌دهد که فرد المپیادی در کدام ییک از لیست‌های پنج‌گانه قرار دارد که به این ترتیب شماره آن فرد شناسایی خواهد شد.