المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۳۲

سوال ۳۲

۶ نفر دور یک میز نشسته‌اند. ابتدا هر کس دقیقاً یکی از چشمان خود را می‌بندد. اگر کسی چشم راست خود را ببندد، همه‌ی سایر افراد به جز دو نفر سمت راستش را می‌تواند ببیند، و به طور مشابه، اگر چشم چپ خود را ببندد، دیگر افراد به جز دو نفر سمت چپش را می‌بیند.

میزان«هم‌بینی» افراد دور یک میز، برابر تعداد جفت افرادی است که بتوانند همدیگر را ببینند. در بین تمامیِ حالت‌های چشم‌بستنِ این ۶ نفر، حدّاکثر میزان «هم‌بینی» چقدر است؟

  1. ۴
  2. ۶
  3. ۷
  4. ۸
  5. ۱۰

پاسخ

گزینه‌ی (۳) درست است.

در صورتی که افراد دور دایره را شماره‌گذاری کنیم، در صورتی که نفر اول و نفر چهارم چشم راست و بقیه چشم چپ خود را ببندند، 7 جفت آدم یکدیگر را می‌بینند.

حال ثابت می‌کنیم این تعداد بیش‌ترین تعداد جفت آدم ممکن است. در کل تعداد هم‌بینی‌های ممکن$15$=$\binom{6}{2}$ تاست. از طرفی می‌دانیم از این تعداد حداقل $\frac{2 ×6}{2}$ هم‌بینی به دلیل ندیدن افراد مجاور حذف خواهد شد. در نتیجه حداکثر $9$ هم‌بینی می‌ماند. همچنین سه نفر مجاور که‌هم‌بینی ندارند را در نظر بگیرید، نفر سمت چپ چشم سمت راست خود را بسته است و نفر سمت راست چشم سمت چپ خود. این ناهم‌بینی‌ها در کسر فوق محاسبه شده‌اند ولی نفر وسط به هر طریقی که چشم خود را ببندد یکی دیگر به جز دو نفر مجاور خود را نخواهد دید در نتیجه یک واحد به کسر بالا اضافه خواهد شد. به ازای هر سه نفر که هم‌بینی ندارند و مجاور هستند یکی به کسر فوق اضافه می‌شود چون تعداد افراد $6$ است در کل $8$ هم‌بینی از بین می‌روند. در نتیجه بیش‌تر از $7$ هم‌بینی امکان‌پذیر نیست.


ابزار صفحه