Processing math: 94%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:تئوری:سوال ۱

سوال ۱

فرض کنید v{0,1}n و A{0,1}n تعریف می‌کنیم که vA اگر و تنها اگر به ازای هر زیرمجموعه‌ی k تایی از مولفه‌ها، برداری مثل uA وجود داشته باشد که در آن مولفه‌ها دقیقا مثل v باشد ونیز uv باشد.

یک مجموعه‌ی A{0,1}n را k-بسته می‌نامیم، در صورتی که به ازای هر vA داشته باشیم: vA

  1. ثابت کنید اگر k2 باشد و دو عضو A در بیش از nk+1 مولفه فرق داشته باشند، آن‌گاه A‌ یک مجموعه‌ی k-بسته است.
  2. ثابت کنید تعداد مجموعه‌های k-بسته حداکثر 2^{2^k \binom{n}{k}} است.

ابزار صفحه