پنجشنبه ۳۰ فروردين ۱۴۰۳   |  كاربر مهمان   |    
 مسابقه‌ی تصادفی

 
 
 دانش‌آموزان راستگو
دانش‌آموزان راستگو مسابقه كامپيوتر
مسابقه شماره ۲۴۸

 سوال

 
۳۰ دانش‌آموز در یک کلاس حضور دارند که همه آنها افرادی راست‌گو هستند. می‌دانیم یکی از آنها المپیادی است ولی او را نمی٬شناسیم.
 
می‌خواهیم با پرسیدن k سوال ٫ فرد مزبور را بیابیم. در هر سوال می‌توانیم یکی از دانش‌آموزان را انتخاب می‌کنیم و به او اسم چند نفر از دانش‌آموزان را بگوییم و از او بپرسیم که آیا فرد المپیادی ٫ یکی از آن چند نفر است یا خیر ؟
 
او هم فقط به این سوال جواب بله یا خیر می‌دهد. k حداقل چقدر باشد که با پرسیدن k سوال همواره مطمپن باشیم می‌توانیم فرد مورد نظر را بشناسیم.
 
 
 
 
 
پاسخ
 
به هر دانش‌آموز یک کد از ۱ تا ۳۰ داده و شماره او را در مبنای ۲ در نظر می‌گیریم.
معلوم است که در آن مبنا شماره هر فرد حداکثر پنج رقمی است. بنابراین پنج لیست به نام‌های A ٫ B ٫ C ٫ D و E در نظر گرفته و هر یک از آنها را متناظربه یکی از ارقام پنج گانه اعداد در مبنای ۲ قرار می‌دهیم.
در جایگاه‌هایی که رقم ۱ باشد در لیست متناظر اسم فرد را می‌نویسیم و در غیر این صورت اسم او را در آن لیست نمی‌نویسیم. به عنوان مثال اسم نفر یازدهم در لیست‌های A ٫ B و D نوشته شده ولی در لیست‌های C و E نوشته نمی‌شود ٫ زیرا عدد ۱۱ در مبنای ۲ به شکل ۰۱۰۱۱ نوشته می‌شودو لیست‌های پنج‌گانه را به یک نفر نشان می‌دهیم و او اطلاع می‌دهد که فرد المپیادی در کدام یک از لیست‌های پنج گانه قرار دارد که به این ترتیب شماره آن فرد شناسایی خواهد شد.
1392/11/6 لينک مستقيم
فرستنده :
hani HyperLink HyperLink 1393/1/27
مـتـن : 21
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : 35
فرستنده :
khosi HyperLink HyperLink 1393/1/27
مـتـن : 5
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : حداقل 10سوال
فرستنده :
سیدمحمدباقرحاتم پور HyperLink HyperLink 1393/1/27
مـتـن : 29سوال
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : 29 kl
فرستنده :
سارا HyperLink HyperLink 1393/1/27
مـتـن : 5 بار
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : 15
فرستنده :
هفتصدویکساله HyperLink HyperLink 1393/1/27
مـتـن : k=1
فرستنده :
نازنین ستاری HyperLink HyperLink 1393/1/27
مـتـن : با 5 سوال
فرستنده :
مریم HyperLink HyperLink 1393/1/27
مـتـن : چهارسوال
فرستنده :
khosi HyperLink HyperLink 1393/1/27
مـتـن : 5
فرستنده :
کوثر HyperLink HyperLink 1393/1/27
مـتـن : ابتدا دانش آموزان کلاس را به دو قسمت مساوی تقسیم می کنیم یک قسمت را انتخاب می کنیم و نام آنها را می گوییم اگر جواب مثبت بود یعنی در بین گروهی است که انتخابشان کرده ایم و اگر منفی بود خودمان می فهمیم که در گروه دیگر است پس گروهی که دانش آموز المپیادی در آن است را بازهم به دو قسمت تقسیم می کنیم و باز هم به ترتیب قبل عمل می کنیم در کمترین عدد یعنی اگر در گروه با تعداد فرد قرار بگیرد (30-15-7-3-1) کمترین مقدار K برابر4 و در حالتی که در بین گروه با تعداد زوج قرار بگیرد (30-15-7یا8-4-2-1) و یا (30-15-7-3-2-1) کمترین مقدار k برابر 5 است.
پاسـخ :
فرستنده :
مریم HyperLink HyperLink 1393/1/27
مـتـن : چهارسوال
فرستنده :
علی HyperLink HyperLink 1393/1/27
مـتـن : k=5
می توان با 5 مرحله و حذف نیمی از احتمالات در هر مرحله به جواب رسید
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : سقف لگاریتم 30 در مبنای 2
فرستنده :
حسین HyperLink HyperLink 1393/1/27
مـتـن : k حداقل باید 5 باشد . در اولین پرسش 15 نفر را انتخاب کرده و این پرسش را میپرسیم . هر جوابی را که معلوم میشود 15 نفر المیپادی نیستند . در پرسش بعدی هر تعدادی نفر از آن 15 نفر باقیمانده انتخاب کنیم ، در بدترین حالت 8 نفر باقی میمانند . چون اگر مثلا a نفر انتخاب کنیم ، یکی از اعداد a و 15-a بزرگتر یا مساوی هشت هستند . حالا ما 8 نفر داریم . با سه پرسش دیگر میتوانیم نفر مورد نظر را پیدا کنیم . در هر پرسش تعداد جوابهای احتمالی نصف میشود .
در حالت کلی اگر کلاس n دانش آموز داشته یاشد به کران بالای lg n پرسش نیاز داریم .
فرستنده :
زهرا حوتی HyperLink HyperLink 1393/1/27
مـتـن : با تشکر .سوال بسیار خوبی بود و مورد توجه من قرار گرفت.
فرستنده :
امیر HyperLink HyperLink 1393/1/27
مـتـن : حداقل 4 بار , بار اول به دو گروه 14 و 15 تایی (به جز خود فرد)تقسیم می کنیم فرد در یکی از این گروه هاست که گروه دیگری حذف می شود!
سپس با توجه به این که فرد در کدام است یکی از دو حالات زیر به وجود می اید.
بار دوم به دو گروه 7و7 یا 7و6 (به جز فردی که پاسخ می دهد)
بار سوم به دو گروه3و3 یا 3و2
بار چهارم دو گروه1و1 به علاوه خود پاسخ دهنده که اگر فرد المپیادی یکی از دو نفر نباشد خود پاسخ دهنده فرد المپیادیست!
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : 5
فرستنده :
فردین HyperLink HyperLink 1393/1/27
مـتـن : k = 15
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : 5
فرستنده :
سعید HyperLink HyperLink 1393/1/27
مـتـن : 5
فرستنده :
ناشناس HyperLink HyperLink 1393/1/27
مـتـن : ٥ ابتدأ از يك نفر مي پرسيم كه المپيادي در نفرات ١ تا ١٥ هست يا نه.
اگر بله سپس از نفر دوم مي پرسيم كه از نفرات ١ تا ٧ هست با نه و اگر خير از نغر دوم مي پرسيم كه از نفرات ١٥ تا ٢٢ است يا نه و به همين ترتيب آدامه مي دهيم
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 المپیاد کامپیوتر

 

     

 

  

صفحه‌ي اصلي
     

 

راهنماي سايت
     

 

  

آموزش
     

 

بانك سوال
     

 

  

مسابقه
     

 

  

زنگ تفريح
     

 

  

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

 

  

معرفي كتاب
     

 

  

مشاوره
     

 

  

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

 

اخبار

 

فعاليت‌هاي علمي
 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.
 

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)