Processing math: 69%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:ترکیبیات:سوال ۹

سوال ۹

تعداد ‎m‎ رشته ‎Ai (1im)‎ هر کدام به طول ‎n‎ از اعداد ‎۰‎ و ‎۱‎ به ما داده‌ شده‌ است به طوری که در هر رشته دقیقا نصف اعداد ‎۱‎ است و به ازای هر ‎i‎ و ‎j‎ متفاوت می‌دانیم تعداد مکان‌های ‎k‎ که ‎Ai[k]Aj[k]‎ بیشتر مساوی ‎d‎ است.

  1. ثابت کنید ‎m \leq \frac{2^n}{\sum_{i=0}^{\lfloor\frac{d-1}{2}\rfloor}{n\choose i}}
  2. ثابت کنید اگر ‎d=\frac{n}{2}+k‎ که ‎0<k\leq \frac{n}{2}‎ آن‌گاه ‎m\leq \frac{n}{2k}+1‎.

ابزار صفحه