فرد عجیب

[Goharshady]

در یک اجتماع n نفره ، فرد عجیب فردی است که هیچ کس او را نشناسد ولی او همه را بشناسد. یک اجتماع n نفره در نظر بگیرید ، در هر مرحله می توانید دو تا از اعضای این مجموعه را انتخاب کنید و از اولی بپرسید که دومی را می شناسد یا نه.
برای اجتماعی 128 نفره با کمتر از 400 سوال فرد عجیب را در صورت وجود پیدا کنید.

 

[abdi]

دو نفر را انتخاب مي‌كنيم. اگر اولي، دومي را بشناسد، در اين صورت دومي عجيب نيست و اگر اولي، دومي را نشناسد، پس اولي عجيب نيست. پس در هر پرسش 1 نفر حذف مي‌شود. در اين صورت كل پرسش‌ها برابر است با 127=1+2+4+8+16+32+64

 

[Goharshady]

متاسفانه پاسخ شما صحیح نیست ولی خیلی نزدیک شده اید ، کمی دقت کنید.

 

[abdi]

متاسفانه پاسخ شما صحیح نیست ولی خیلی نزدیک شده اید ، کمی دقت کنید.

ببخشید می‌شه یه‌مقدار توضیح بدید؟ آخه من اشکالی تو جوابم پیدا نکردم

 

[Goharshady]

گفته فرد عجیب را در صورت وجود بیابید. شما فرض کرده اید که فرد عجیب وجود دارد!

 

[Goharshady]

. در اين صورت كل پرسش‌ها برابر است با 127=1+2+4+8+16+32+64

لازم نیست این جمع را انجام دهید
در هر مرحله یک نفر کنار می رود پس 127 پرسش می خواهد
ولی این در صورتی است که فرد عجیب وجود داشته باشد.

 

[abdi]

گفته فرد عجیب را در صورت وجود بیابید. شما فرض کرده اید که فرد عجیب وجود دارد!

من فرض نکردم فرد عجیب وجود دارد. فقط گفتم اگر این اتفاق بیفتد، آنگاه فلان نفر فرد نمی‌تواند فرد عجیب باشد. طبیعتاً در پایان با توجه به نتایج پرسش‌ها معلوم می‌شود که اصلاً فرد عجیب داریم یا نه.

 

[Goharshady]

متاسفانه معلوم نمی شود!
چون ممکن است یکی از کسانی که کنار گذاشته ایم و راجع به فرد آخر از او نپرسیده ایم ، فرد آخری را بشناسد! همچنین ممکن است یکی از کسانی که راجع به آنها از فرد آخری نپرسیده ایم را فرد آخر نشناسد!

 

[abdi]

متاسفانه معلوم نمی شود!
چون ممکن است یکی از کسانی که کنار گذاشته ایم و راجع به فرد آخر از او نپرسیده ایم ، فرد آخری را بشناسد! همچنین ممکن است یکی از کسانی که راجع به آنها از فرد آخری نپرسیده ایم را فرد آخر نشناسد!

مثل اين‌كه حق با شماست.

حالا مي‌توانيم فرد آخر را با افراد كنارگذاشته‌شده‌اي كه گفتيد، مورد سوال قرار دهيم و بفهميم عجيب هست يا نه. فكر كنم تعداد كل پرسش‌ها كمتر از 400تا خواهد شد.

 

[DPJ]

پاسخ : فرد عجیب

مثل اين*كه حق با شماست.

حالا مي*توانيم فرد آخر را با افراد كنارگذاشته*شده*اي كه گفتيد، مورد سوال قرار دهيم و بفهميم عجيب هست يا نه. فكر كنم تعداد كل پرسش*ها كمتر از 400تا خواهد شد.

با این روش می توانید فرد عجیب در بین n نفر را با 3n-3 پرسش و شاید 3n-4 پرسش بیابید. حال سعی کنید به جای با حداکثر 374 پرسش فرد عجیب در بین 128 نفر را در صورت وجود بیابید.