المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۱

۸ نفر با هم یک بازی می کنند به این صورت که هر نفر در ابتدا یک کلمه انتخاب می کند. سپس در هر مرحله این ۸نفر به ۴ گروه ۲تایی تقسیم می شوند و در هر گروه ۲نفره، هر کس تمام کلماتی را که می داند به نفر مقابل اش می گوید. بازی زمانی تمام می شود که هر یک از این ۸ نفر هر ۸ کلمه‌ی اولیه را بداند.

ما می دانیم که حمید فقط در مرحله‌ی اول راست می گوید و در باقی مراحل نمی توان روی حرفش حساب کرد. حداقل چند مرحله لازم است تا مطمئن شویم هر ۸ نفر٬ ۸ کلمه‌ی اولیه را می دانند؟

  1. ۵
  2. ۷
  3. ۴
  4. ۶
  5. ۳

پاسخ

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

در چهار مرحله با حرکات زیر می‌توان به هدف سوال رسید. فرض کنید که حمید نفر اول است.

مرحله‌ی اول: $(1,2)(3,4)(5,6)(7,8)$

  • هرکسی از دو خبر آگاه است.

مرحله‌ی دوم: $(1,3)(2,4)(5,7) (6,8)$

  • به جز ۳ همگی از چهار خبر آگاهند.

مرحله‌ی سوم: $(1,5)(2,6)(3,7)(4,8)$

  • به جز ۳ و ۷ و ۵ بقیه از همه‌ی اخبار آگاهند.

مرحله‌ی چهارم: $(1,2)(3,4)(5,6) (7,8)$

  • تمامی افراد از همه‌ی اخبار آگاهند.

از طرفی با سه حرکت نمی‌توان به نتیجه رسید. زیرا پس از مرحله‌ی اول هرکس حداکثر دو خبر دارد. پساز مرحله‌ی دوم هرکس حداکثر ۴خبر دارد به جز کسی که با حمید جفت شده است که حداکثر دو خبر دارد. او در مرحله‌ی بعدی حداکثر ۴ خبر جدید می‌گیرد و بنابراین بعداز سه مرحله حداکثر ۶ خبر خواهد داشت.


ابزار صفحه