المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۹

تعداد ‎$m$‎ رشته ‎$A_i$ ($1\leq i\leq m$)‎ هر کدام به طول ‎$n$‎ از اعداد ‎۰‎ و ‎۱‎ به ما داده‌ شده‌ است به طوری که در هر رشته دقیقا نصف اعداد ‎۱‎ است و به ازای هر ‎$i$‎ و ‎$j$‎ متفاوت می‌دانیم تعداد مکان‌های ‎$k$‎ که ‎$A_i[k] \neq A_j[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$‎.

ابزار صفحه