المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:تئوری:سوال ۲۰

سوال ۲۰

۱) مسئله اول

  • داده‌ها: یک مجموعه از خرابی‌ها به نام $A$ و یک خانواده از زیرمجموعه‌های $A$ بنام $C$ که در واقع مجموعه‌ای از آزمایش‌هاست و یک عدد مثبت طبیعی به‌نام $J$ به‌طوری که $J\leq |C|$.
  • پرسش: آیا یک زیرمجموعه $C'$ از $C$ وجود دارد به‌طوری که $|C'|\leq J$ بوده و برای هر $a_i$ و $a_j$ از مجموعه خرابی‌های $A$ یک آزمایش $c$ از $C'$ وجود داشته باشد به‌طوری که $|\{a_i,a_j\} \cap c|=1$ (در واقع $c$ بین دو خرابی $a_i$ و $a_j$‌ یک تمایز ایجاد می‌کند.)

۲) مسئله دوم

  • داده‌ها: یک مجموعه $M \subseteq W \times X \times Y$ در این‌جا $X$ و $Y$ و $W$ سه مجموعه‌ی متمایز هستند به‌طوری‌که $|X|=|Y|=|W|=q$
  • پرسش: آیا یک زیر مجموعه‌ی $M'$ از $M$ وجود دارد به‌طوری که $|M'|$ بوده و هیچ دو عضو از $M'$ در یک مولفه برابر نباشند.

سعی کنید با ساختن داده‌های جدید از روی مسئله دوم برای مسئله اول مسئله‌ی دوم را حل نمایید.


ابزار صفحه