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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

تعریف می‌کنیم: Pn={(a1,a2,...,an)|ai{0,1}}

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

می‌خواهیم اعضای Pn را با دو رنگ B و R رنگ کنیم، به طوری که اعضای با تعداد زوجی l، به رنگ R و باقی به رنگ B در بیایند. درهر مرحله می‌توانیم یک زیر مجموعه‌ی خوب مثل A از Pn را انتخاب کنیم و اعضایی از A‌ که هنوز رنگی ندارند را به رنگی یکسان در آوردیم. نشان دهید اگر n=mk این کار در kj=0(2m1)kj=(2m1+1)k مرحله امکان‌پذیر است.


ابزار صفحه