مسابقه‌ی تصادفی

 
 
 دانش آموز المپیادی
دانش آموز المپیادیمسابقه كامپيوتر
مسابقه شماره ۲۳۹

 سوال

30 دانش‌آموز در یک کلاس حضور دارند که همه آنها افرادی راست‌گو هستند. می‌دانیم یکی از آنها المپیادی  است ولی او را نمی‌شناسیم. می‌خواهیم با پرسیدن k سوال , فرد مزبور را بیابیم. در هر سوال می‌توانیم یکی از دانش‌آموزان را انتخاب کنیم و به او اسم چند نفر از دانش‌آموزان را بگوییم و از او بپرسیم که آیا فرد المپیادی , یکی از آن چند نفر است یا خیر؟ او هم فقط به این سوال جواب بله یا خیر می‌دهد. k حداقل چقدر باشد که با پرسیدن k سوال همواره مطمئن باشیم می‌توانیم فرد مورد نظر را بشناسیم.
 

 
پاسخ 
به هر دانش‌آموز یک کد از 1 تا 30 داده و شماره او را در مبنای 2 د ر نظر می‌گیریم. معلوم است که در آن مبنا شماره هر فرد حداکثر پنج رقمی است. بنابراین پنج لیست به نام‌های A,B,C,D و E در نظر گرفته و هر یک از آنها را متناظر به یکی از ارقام پنج‌گانه  اعداد در مبنای 2 قرار می‌دهیم. در جایگاه‌هایی که رقم 1 باشد در لیست متناظر اسم فرد را می‌نویسیم و در غیر اینصورت اسم او را در آن لیست نمی‌نویسیم. به عنوان مثال اسم نفر یازدهم در لیست‌های A,B و D نوشته شده ولی در لیست‌های C و E نوشته نمی‌شود , زیرا عدد 1 در مبنای 2 به شکل 01011 نوشته می‌شود. لیست‌های پنج‌گانه را به یک نفر نشان می‌دهیم و او اطلاع می‌دهد که فرد  المپیادی در کدام ییک از لیست‌های پنج‌گانه قرار دارد که به این ترتیب شماره آن فرد شناسایی خواهد شد.
1392/6/27لينک مستقيم

فرستنده :
علی اصغری HyperLink HyperLink 1393/1/27
مـتـن : به نظرمن با5نفر می توان انجم داد

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  6796
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  6796