المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

تعریف می‌کنیم: $P_n=\{(a_1,a_2,...,a_n)|a_i \in \{0,1\} \}$

در ضمن یک زیر مجموعه‌ی خوب از $P_n$ شامل تمام اعضایی از $P_n$ است که در تعدادی از مولفه‌های مشخص شده مقادیر آن‌ها یکسان است.

می‌خواهیم اعضای $P_n$ را با دو رنگ $B$ و $R$ رنگ کنیم، به طوری که اعضای با تعداد زوجی $l$، به رنگ $R$ و باقی به رنگ $B$ در بیایند. درهر مرحله می‌توانیم یک زیر مجموعه‌ی خوب مثل $A$ از $P_n$ را انتخاب کنیم و اعضایی از $A$‌ که هنوز رنگی ندارند را به رنگی یکسان در آوردیم. نشان دهید اگر $n=mk$ این کار در $\sum_{j=0}^k(2^{m-1})^{k-j}=(2^{m-1}+1)^k$ مرحله امکان‌پذیر است.


ابزار صفحه