شبكه‌ي رشد > المپياد كامپيوتر > مسابقه

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

دانش‌آموزان راستگو

مسابقه شماره ۲۴۸

سوال

۳۰ دانش‌آموز در یک کلاس حضور دارند که همه آنها افرادی راست‌گو هستند. می‌دانیم یکی از آنها المپیادی است ولی او را نمی٬شناسیم.

می‌خواهیم با پرسیدن k سوال ٫ فرد مزبور را بیابیم. در هر سوال می‌توانیم یکی از دانش‌آموزان را انتخاب می‌کنیم و به او اسم چند نفر از دانش‌آموزان را بگوییم و از او بپرسیم که آیا فرد المپیادی ٫ یکی از آن چند نفر است یا خیر ؟

او هم فقط به این سوال جواب بله یا خیر می‌دهد. k حداقل چقدر باشد که با پرسیدن k سوال همواره مطمپن باشیم می‌توانیم فرد مورد نظر را بشناسیم.

پاسخ

به هر دانش‌آموز یک کد از ۱ تا ۳۰ داده و شماره او را در مبنای ۲ در نظر می‌گیریم.

معلوم است که در آن مبنا شماره هر فرد حداکثر پنج رقمی است. بنابراین پنج لیست به نام‌های A ٫ B ٫ C ٫ D و E در نظر گرفته و هر یک از آنها را متناظربه یکی از ارقام پنج گانه اعداد در مبنای ۲ قرار می‌دهیم.

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

1392/11/6

لينک مستقيم

پاسخ دهيد (24)

فرستنده :

hani

1393/1/27

مـتـن :

فرستنده :

ناشناس

1393/1/27

مـتـن :

فرستنده :

khosi

1393/1/27

مـتـن :

فرستنده :

ناشناس

1393/1/27

مـتـن :

حداقل 10سوال

فرستنده :

سیدمحمدباقرحاتم پور

1393/1/27

مـتـن :

29سوال

فرستنده :

ناشناس

1393/1/27

مـتـن :

29 kl

فرستنده :

سارا

1393/1/27

مـتـن :

5 بار

فرستنده :

ناشناس

1393/1/27

مـتـن :

فرستنده :

هفتصدویکساله

1393/1/27

مـتـن :

k=1

فرستنده :

نازنین ستاری

1393/1/27

مـتـن :

با 5 سوال

فرستنده :

مریم

1393/1/27

مـتـن :

چهارسوال

فرستنده :

khosi

1393/1/27

مـتـن :

فرستنده :

کوثر

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 است.

پاسـخ :

فرستنده :

مریم

1393/1/27

مـتـن :

چهارسوال

فرستنده :

علی

1393/1/27

مـتـن :

k=5
می توان با 5 مرحله و حذف نیمی از احتمالات در هر مرحله به جواب رسید

فرستنده :

ناشناس

1393/1/27

مـتـن :

سقف لگاریتم 30 در مبنای 2

فرستنده :

حسین

1393/1/27

مـتـن :

k حداقل باید 5 باشد . در اولین پرسش 15 نفر را انتخاب کرده و این پرسش را میپرسیم . هر جوابی را که معلوم میشود 15 نفر المیپادی نیستند . در پرسش بعدی هر تعدادی نفر از آن 15 نفر باقیمانده انتخاب کنیم ، در بدترین حالت 8 نفر باقی میمانند . چون اگر مثلا a نفر انتخاب کنیم ، یکی از اعداد a و 15-a بزرگتر یا مساوی هشت هستند . حالا ما 8 نفر داریم . با سه پرسش دیگر میتوانیم نفر مورد نظر را پیدا کنیم . در هر پرسش تعداد جوابهای احتمالی نصف میشود .
در حالت کلی اگر کلاس n دانش آموز داشته یاشد به کران بالای lg n پرسش نیاز داریم .

فرستنده :

زهرا حوتی

1393/1/27

مـتـن :

با تشکر .سوال بسیار خوبی بود و مورد توجه من قرار گرفت.

فرستنده :

امیر

1393/1/27

مـتـن :

حداقل 4 بار , بار اول به دو گروه 14 و 15 تایی (به جز خود فرد)تقسیم می کنیم فرد در یکی از این گروه هاست که گروه دیگری حذف می شود!
سپس با توجه به این که فرد در کدام است یکی از دو حالات زیر به وجود می اید.
بار دوم به دو گروه 7و7 یا 7و6 (به جز فردی که پاسخ می دهد)
بار سوم به دو گروه3و3 یا 3و2
بار چهارم دو گروه1و1 به علاوه خود پاسخ دهنده که اگر فرد المپیادی یکی از دو نفر نباشد خود پاسخ دهنده فرد المپیادیست!

فرستنده :

ناشناس

1393/1/27

مـتـن :

فرستنده :

فردین

1393/1/27

مـتـن :

k = 15

فرستنده :

ناشناس

1393/1/27

مـتـن :

فرستنده :

سعید

1393/1/27

مـتـن :

فرستنده :

ناشناس

1393/1/27

مـتـن :

٥ ابتدأ از يك نفر مي پرسيم كه المپيادي در نفرات ١ تا ١٥ هست يا نه.
اگر بله سپس از نفر دوم مي پرسيم كه از نفرات ١ تا ٧ هست با نه و اگر خير از نغر دوم مي پرسيم كه از نفرات ١٥ تا ٢٢ است يا نه و به همين ترتيب آدامه مي دهيم

	نظر شما پس از تاييد در سايت قرار داده خواهد شد

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





تایید انصراف

بازديدها

	كاربران غيرعضو آنلاين: 19
	كاربران عضو آنلاين: 0
	کل كاربران آنلاين: 19

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

فهرست: