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