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