المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۳

سوال ۳

در یک جدول منظور از خانه‌ي $(i>0,j>0)(i,j)$ خانه‌ای است که در سطر $i$ ام و ستون $j$ام قرار دارد. یک زیر مجموعه $S$ از خانه‌های جدول را یک «مجموعه زیبا» گوییم٬ اگر به ازای هر خانه‌ي $(a,b)$ متعلق به $S$، تمام خانه‌های $(x,y)$ که $x\leq a$ و $y\leq b$ نیز در $S$ باشند.

کدام یک از گزینه‌های زیر درست است؟

  1. خانه‌ی $(1,1)$ عضو هر مجموعه‌ي زیبا هست
  2. اعضای هر مجموعه‌ی ناتهی زیبا تشکیل یک مستطیل می‌دهند که خانه‌ی $(1,1)$ را در بر می‌گیرد
  3. هر اجتماعی از تعدادی مستطیل که همگی شامل $(1,1)$ باشند٬ یک مجموعه‌ی ناتهی زیباست
  4. ۱ و ۳
  5. ۲ و ۳

پاسخ

گزینه (۳) درست است.

برای گزینه‌ی ۱ مثال نقض تهی وجود دارد. برای گزینه‌ی ۲ مثال نقض مانند شکل زیر وجود دارد.


ابزار صفحه