Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

۱) مسئله اول

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

۲) مسئله دوم

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

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


ابزار صفحه