آمار پرسش:
- پرسیده شده: 2022-05-10 03:29:13 -0500
- مشاهده شده: 355 بار
- بروز شده: 2024-02-05 14:01:13 -0500
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
نوشتن اسم زندانیها - سوال دوم تشریحی سال 1401 - دوره 32
در یک زندان، ۳۲ نفر با اسامی متمایز در ۳۲ سلول زندانی هستند. زندانبانِ زندان عوض شده و زندانبان جدید میخواهد لیستی از اسامی ۳۲ زندانی تهیه کند. او برای این کار با زندانیها توافق میکند که این بازی را انجام دهند:
هر روز، ابتدا زندانبان دو سلول را انتخاب میکند؛ سپس با مراجعه به آن دو سلول، زندانیهاى هر کدام از آن دو سلول را میبیند و اگر هر یک از آن ها را قبلا ندیده باشد، اسم آن فرد را هم به لیست خود اضافه میکند. همان شب و دور از چشم زندانبان، یکى از آن دو زندانى سلولش را با یکى از ۳۱ زندانی دیگر عوض میکند. آیا زندانبان در هر شرایطی (به ازای تمام عملکردهای ممکن زندانیها) میتواند در حداکثر ۱۰۲۴ روز، لیستی از اسامی همه ی زندانیها را تهیه کند؟ توضیح: اگر پاسخ شما برای این سوال «بله» است، باید روشی برای زندانبان ارائه کنید که در حداکثر ۱۰۲۴ روز ، لیست اسامی زندانیها را تهیه کند. همچنین اگر پاسخ شما برای این سوال «خیر» است، باید اثبات کنید به ازای هر الگوریتم زندانبان، حالتی وجود دارد که او به هدفش نرسد.
1 پاسخ
خب، ثابت می کنم اگه یه نفر باشه که تا روز i ام دیده نشده، حالتی وجود داره که در روز i+1 هم دیده نشه: فرض کنید فرد A روز i ام دیده نشده. خب برا روز i+1 ام، سه حالت برا سلولی که فرد A در اون هست وجود داره:
- در سلولی که روز i ام بوده باقی بمونه. (یه حالت)
- جاش رو با یکی از دو زندانی ای که در روز i ام دیده شدن (ینی زندانبان در روز i ام به سلولاشون مراجعه کرده) عوض کنه. (دو حالت)
اما طبق فرض سول، زندانبان هر شب فقط دو سلول رو می بینه و چون سلول فرد A سه حالت داره، ممکنه که در سلول سومی باشه که زندانبان بهش مراجعه نمی کنه و ینی حالتی وجود داره که فرد A در روز i+1 ام هم دیده نشه:)
با توجه به اینکه در پایان روز اول، 30 نفر هستن که دیده نشدن و همپنین به استناد استدلالی که ذکر کردم، حالتی هس که فردی باشه که تا روز 1024 ام (یا حتی تا بینهایت!) دیده نشه. تامام 🗿
