۸ نفر با هم یک بازی می کنند به این صورت که هر نفر در ابتدا یک کلمه انتخاب می کند. سپس در هر مرحله این ۸نفر به ۴ گروه ۲تایی تقسیم می شوند و در هر گروه ۲نفره، هر کس تمام کلماتی را که می داند به نفر مقابل اش می گوید. بازی زمانی تمام می شود که هر یک از این ۸ نفر هر ۸ کلمهی اولیه را بداند.
ما می دانیم که حمید فقط در مرحلهی اول راست می گوید و در باقی مراحل نمی توان روی حرفش حساب کرد. حداقل چند مرحله لازم است تا مطمئن شویم هر ۸ نفر٬ ۸ کلمهی اولیه را می دانند؟
پاسخ
گزینهی ۳ درست است.
در چهار مرحله با حرکات زیر میتوان به هدف سوال رسید. فرض کنید که حمید نفر اول است.
مرحلهی اول: $(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)$
از طرفی با سه حرکت نمیتوان به نتیجه رسید. زیرا پس از مرحلهی اول هرکس حداکثر دو خبر دارد. پساز مرحلهی دوم هرکس حداکثر ۴خبر دارد به جز کسی که با حمید جفت شده است که حداکثر دو خبر دارد. او در مرحلهی بعدی حداکثر ۴ خبر جدید میگیرد و بنابراین بعداز سه مرحله حداکثر ۶ خبر خواهد داشت.