به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
0 امتیاز
277 بازدید
در دبیرستان توسط mansour (771 امتیاز)

در ضیافتی که ۲۰۰۰ نفر در آن شرکت دارند، بین هر چهار نفر دست کم یک نفر سه تای دیگر را می‌شناسد. سه نفر هستند که هیچ یک، دیگری را نمی‌شناسد. ثابت کنید که ۱۹۹۷ نفر بقیه، همه مهمان‌های دیگر را می‌شناسند.(فرض کنید که" آشنایی" رابطه‌ای متقارن باشد یعنی اگرB, Aرا بشناسد, B نیز A را بشناسد اگر آشنایی لزوماً متقابل نباشد راه حل چیست؟) راه حل با استدلال تناقض.

1 پاسخ

+1 امتیاز
توسط حسن کفاش امیری (3,252 امتیاز)
انتخاب شده توسط mansour
 
بهترین پاسخ

حالت متقارن فرض می کنیم a و b و C همدیگر را نمی شناسنددر این صورت هر نفر دیگه مانندd با آن ها آشناست (باتوجه به فرض مسئله)

حال کافی است نشان دهیم هر دو نفر دیگه بجز سه نفراولیه، همدیگر را می شناسند فرض می کنیم دو نفر مانند e و f همدیگر نشناسند در این صورت در جمع چهار نفره a و b وe وf هیچ شخصی نیست که سه نفر دیگر بشناسد این هم تناقض است

بنابراین هر نفر از 1997 نفره همدیگر را می شناسند و آن سه نفر اولیه را هم می شناسند حکم برقرار است.

حالت نامتقارن این حالت نادرست است، مثال فرض کنید سه نفر اولیه هیچ کسی را نمی شناسند و بقیه هر سه نفر اولیه می شناسند و همچنین فرض کنید که 1997 نفر در یک صف پست سر هم می باشند که هر نفر از آنها همه افراد جلویی خود را می شناسند شرط مسئله بر قرار است اما حکم فقط برای نفر آخر صف بر قرار است.

این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...