سوالات المپیاد:مرحله ی اول:دوره ی ۱۸:سوال ۳۱
سوال ۳۱
یک جدول از اعداد متمایز داده شده است. در هر سطر٬ دو خانه که حاوی بزرگترین اعداد آن سطر هستند را علامت می‌زنیم. همین کار را برای ستون‌ها انجام می‌دهیم. می‌خواهیم بدانیم در کل جدول٬ حداقل چند خانه علامت زده می‌شوند. اگر جدول ما ۱۰۰×۱۰۰ باشد٬ این «مقدار حداقل» چه‌قدر است؟ در مورد جدول ۱۰۱×۱۰۱ چه‌طور؟
- ۴۰۰ و ۴۰۴
- ۲۰۰ و ۲۰۴
- ۳۰۰ و ۳۰۳
- ۲۰۰ و ۲۰۰
- ۲۰۰ و ۲۰۲
پاسخ
گزینه‌ی (5) درست است.
2nتا از بزرگترین اعدادی که قرار است در جدول قرار داده شود را در خانه‌های علامت‌دار جدول روبه‌رو می‌گذاریم.
از طرفی چون از هر سطر باید 2 خانه شامل بزرگترین اعداد را علامت بزنیم، حتما دست‌کم 2n خانه علامت زده می‌شود. پس 2n خانه لازم و کافی است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
