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