المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۶:سوال پنج

صندوقچه‌ها

۵۲۸ صندوقچه با درهای بسته با شماره‌های ۱ تا ۵۲۸ موجود‌اند. افرادی با شماره‌های ۱ تا ۵۲۸ این صندوقچه‌ها را یک‌به‌یک مورد بررسی قرار می‌دهند. در بررسی صندوقچه‌ی $i$ توسط $k$٬ اگر $i$ بر $k$ بخش‌پذیر باشد٬ فرد شماره‌ی $k$ وضعیت درِ صندوقچه‌ی $i$ را تغییر حالت می‌دهد؛ اگر باز بود می‌بندد و اگر بسته بود آن را باز می‌کند.

می‌خواهیم تعدادی از این افراد را انتخاب کنیم تا آن‌ها هر کدام همه‌ی صندوقچه‌ها را بررسی کنند و در انتها فقط درِ صندوقچه‌ی شماره‌ی ۱ باز بماند و بقیه‌ی صندوقچه‌ها بسته باشند. ثابت کنید که دقیقاً یک گروه مشخص از افراد جواب این سوال است. درستی ادعای خود را اثبات نمایید.


ابزار صفحه